Сколько возможных 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

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

x + x ^ 2 + x ^ 3 + ... + x ^ y = 2000000

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

x + x ^ 2 + x ^ 3 + ... + x ^ y = x * (x ^ y - 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 3

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

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 ваш ответ:)

Answer 4

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

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

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

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

Answer 5

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

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

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

Answer 6

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

Это добавляет 4 дополнительных символа к вашему основанию и, таким образом,

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

Хотя это по-прежнему означает, что у вас будет максимум 4-символьный URL-путь.