Сколько возможных URL-адресов вы можете сделать со следующими символами?

Question

Я хочу сделать короткую службу URL для 2 миллионов активов, но я хочу использовать кратчайшее количество возможных символов.

Что такое математическое уравнение, которое мне нужно будет использовать, чтобы понять это? Я знаю, что это имеет какое-то отношение к факториалам, верно?

Answer 1

Это не факторная проблема, а экспоненциальная.

Если x это количество возможных символов, необходимо решить следующее уравнение для y:

x^y = 2000000 

Если вы хотите использовать все номера строчные и альфа [0-9A-Za-z], у вас есть 62 возможных значений. Это означает, что вам нужно решить:

 62^y = 2000000 
y*log(62) = log(2000000) 
     y = log(2000000)/log(62) 
     y = 3.5154313828... 

Конечно, вы не можете иметь 3.5 символов в URL, так что вам нужно будет 4. Если вы хотите изменить набор символов вы используете для вашего URL, просто устраните проблему выше, используя количество значений в вашем наборе.

Примечание Решение этого уравнения предполагает использование URL фиксированной длины. Для URL переменной длины см. Ответ Роба.

Answer 2

Количество возможных коротких URL-адресов = (число возможных различных символов ID), возведенное в силе (Длина ID в URL)

Например, если вы используете только символы нижнего регистра (из которых 26), а ваши URL-адреса выглядят как http://domain.com/XXXXX (для вашего уникального идентификатора из 5 символов), тогда вы можете сделать 26^5 = 11 881 376 коротких URL-адресов.

Если вы использовали буквы верхнего и нижнего регистра, у вас было бы 52, поэтому 52^5 = 380,204,032 возможных коротких URL и т. Д.

Answer 3

Вам нужно ответить на ряд вопросов, например, какие символы вы хотите разрешить в своем наборе.

Все буквы и цифры? основание 36 (5 символов могут вместить 2 мили +)

Различать верхний и нижний регистры? Это приведет вас к базе 62 (4 символа)

Удалить легко ошибочные символы и цифры (например, i/l 0/o)? примерно базовая 32 (также 5 символов)

Answer 4

В соответствии с спецификацией HTTP/URI вы можете дополнительно использовать следующие «безоговорочные символы»: ALPHA/DIGIT/"-"/"."/«_»/«~»

Это добавляет дополнительные 4-х символов в вашей системе счисления и таким образом

Math.log(2000000)/Math.log(66) = 3.4629721616408813 

Хотя это все еще означает, что вы будете в конечном итоге с 4 символов URL пути в максимуме.

Answer 5

@jheddings близок и получил правильный ответ, но математика была не совсем корректной. Не забывайте, что вы не ограничены всеми перестановками символов определенной длины. Вы также можете использовать URL-адреса длиной от 1 до y символов. Поэтому мы хотим получить закрытое значение этой суммы:

x + x^2 + x^3 + ...+ Х^у = 2000000

К счастью, существует замкнутая форма для этой суммы:

х + х^2 + х^3 + ... + х^у = х * (х^у - 1)/(x-1) = 2000000

x - количество возможных символов в нашем диапазоне. Для простоты предположим, что включает в себя только строчные буквы, заглавные буквы и цифры (26 + 26 + 10 = 62)

Тогда мы получаем следующее уравнение:

2000000 = (62^(y+1) - 62)/(62-1) 
2000000 = (62^(y+1) - 62)/(61) 
2000000 * 61 = 62^(y+1) - 62 
122000000 = 62^(y+1) - 62 
122000000 + 62 = 62^(y+1) 
122000062 = 62^(y+1) 
log(122000062) = (y+1) 
log(122000062)/log(62) = y+1 
4.511492 = y+1 
3.511492 = y 

И, как вы сказали, 3.5 символы невозможны, поэтому требуется 4. Разумеется, разница в этом случае не имеет значения. Однако в определенных сценариях (особенно при работе с базой 2) это очень важно.

Answer 6

Вы можете решить эту проблему без математического волшебства.

26 + 26 + 10 = 62 символов

Try 1. 62 = 62 
Try 2. 62*62 = 3,844 
Try 3. 62*62*62 = 238,328 
Try 4. 62*62*62*62 = 14,776,336 

Так 4 ваш ответ :)