Потребовалось мне не так давно написать генератор псевдослучайных последовательностей символов (по образцу ID видеоролика на Youtube) с двумя требованиями – большой диапазон значений (минимум 1 миллиард) и неповторяемость в пределах этого диапазона.
Решение оказалось достаточно простым, думаю, что аналоги известны, но я пришёл к этому варианту самостоятельно, независимо от того, что уже существует. Вообще, генерация песвдослучайных последовательностей – занятие с точки зрения математики весьма интересное, к тому же это неплохая разминка для мозга.
Изначально диапазон значений планировался равным одному миллиарду (это немного меньше, чем 2 в степени 30), но потом было решено расширить его до 2 в степени 36 – около 68 миллиардов. Для обозначения идентификаторов используются цифры, большие и малые английские буквы, а также символы минус и подчёркивание – итого 64 символа, что тоже достаточно удобно, идентификатор получается из 6 знаков.
То есть, мы берём число в диапазоне от 0 до 2^36 - 1, переводим его в двоичную форму, разбиваем на группы по 6 бит и каждой группе сопоставляем символ из нашего диапазона. Всё просто, но есть один момент – последовательность будет иметь вид «AAAAAA», «AAAAAB» и так далее, что, по сути, является теми же числами. Алгоритм в таком случае легко раскрывается и смысл в этом пропадает.
Второй шаг оказался не сложнее первого. Математического обоснования приводить не буду, кому интересно, может поискать в сети учебники. Суть в том, что мы наш номер умножаем на число, взаимно простое с верхней границей диапазона (2^36), берём остаток от деления на значение этой границы и уже полученный результат разбиваем на группы по 6 бит. Главная особенность в том, что пока мы не переберём все 68 с лишним миллиардов чисел, остаток повторяться не будет, причём это обусловлено именно использованием взаимно простых чисел. А так как верхняя граница у нас является степенью двойки и иных делителей не имеет, взаимно простым будет любое нечётное число.
Экспериментальным путём было подобрано, что наилучшие результаты будут, если множитель у нас будет составлять примерно одну треть или две трети верхней границы. Я взял 46913843653.
В результате код на PHP (на другие языки переписать несложно) получился таким:
function getUID($x) {
$sym = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_'; // 64 (!) символа
$range = 68719476736; // Максимальное значение диапазона (не включая), 2^36
$delta = 46913843653; // Шаг генерации псевдослучайных чисел
$result = '';
$k = gmp_mul($delta, $x);
$x = gmp_mod($k, $range);
for ($i = 0; $i < 6; $i++) {
$j = intval(gmp_mod($x, 64));
$result = substr($sym, $j, 1) . $result;
$x = gmp_div($x, 64);
}
return $result;
}
Если вы боитесь, что этот алгоритм всё же можно раскрыть, а вам этого не хочется, можно его немного усложнить, например, после умножения поменять по определёному правилу биты в двоичной записи числа.
Comments: