Алгоритм генерации случайного числа

Нет, ваш алгоритм не масштабируется. То, что я делал раньше, – это серийно выпускать номера (+1 каждый раз), а затем передавать их через операцию XOR, чтобы перемешивать биты, тем самым давая мне, казалось бы, случайные числа. Конечно, они на самом деле не случайны, но они выглядят так, как у пользователей.

[Изменить] Дополнительная информация

Логика этого алгоритма выглядит так: вы используете известную последовательность для генерации уникальных чисел, а затем вы детерминистически манипулируете ими, поэтому они больше не выглядят серийно. Общее решение – использовать некоторую форму шифрования, которая в моем случае была триггером XOR, потому что она так же быстро, как и может, и гарантирует гарантию того, что числа никогда не будут сталкиваться.

Однако вы можете использовать другие формы шифрования, если хотите, чтобы вы предпочитали даже более случайные числа, превышающие скорость (скажем, вам не нужно генерировать множество идентификаторов за раз). Теперь важным моментом в выборе алгоритма шифрования является «гарантия того, что числа никогда не будут сталкиваться». И способ доказать, может ли алгоритм шифрования выполнить эту гарантию, – проверить, имеет ли как исходный номер, так и результат шифрования одинаковое количество бит, и что алгоритм является обратимым (биекция).

[Спасибо Адаму Лиссу и Цезару за то, что он решил отказаться от решения]

Почему бы вам просто не использовать GUID? Большинство языков должны иметь встроенный способ сделать это. Он гарантированно будет уникальным (с очень разумными ограничениями).

Хотите получить более высокое решение?

Я предполагаю, что случайность не предназначена для обеспечения качества шифрования, но достаточно, чтобы препятствовать угадыванию долговечности пользователя пользователем_ user.

Во время разработки сгенерируйте список из 10 миллионов номеров в строковой форме.

Необязательно, выполните некоторое простое преобразование, например добавление постоянной строки в середину. (Это на случай, если результат слишком предсказуем.)

Передайте их в инструмент, который генерирует функции Perfect Hash , такие как gperf .

Полученный код может использоваться для быстрого кодирования идентификатора пользователя во время выполнения в уникальное значение хэш-функции, которое гарантируется, что оно не будет конфликтовать с любыми другими значениями хэш-функции.

Попробуйте оператор в mysql SELECT CAST (RAND () * 1000000 AS INT)

Предполагая, что:

• Случайность необходима для уникальности, а не для безопасности
• Ваш user_id – 32 бит
• Ваш предел в 9999999 был всего лишь примером

Вы могли бы сделать что-то простое, имея случайное число в виде 64-битного целого числа, причем верхние 32 бита содержат метку времени (при вставке строки) и нижние 32 бита user_id. Это было бы уникально даже для нескольких строк с одним и тем же пользователем, если вы используете соответствующее разрешение на своей временной отметке в зависимости от того, как часто вы добавляете новые строки для одного и того же пользователя. Объедините с уникальным ограничением в случайном столбце и поймайте любую такую ​​ошибку в своей логике, а затем просто повторите попытку.

Я думаю, вы обнаружите, что вы действительно не хотите этого делать. По мере увеличения числа в базе данных вы можете потратить слишком много времени на цикл «убедитесь, что этот номер не принят».

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

Мой опыт заключался в просто использовании RNG в PHP. Я обнаружил, что с использованием определенного размера числа (я использую int, поэтому у меня максимум 4G). Я провел несколько тестов и обнаружил, что в среднем в 500 000 итераций я получил 120 отдельных дубликатов. Я никогда не получал три повторения после запуска цикла кучу раз. Мое «решение» должно было просто вставить и проверить, не сработало ли оно, а затем сгенерировать новый идентификатор и вернуться снова.

Мой совет состоит в том, чтобы сделать то же самое и посмотреть, какова ваша ставка столкновения & c, и посмотреть, приемлемо ли это для вашего дела.

Это не оптимально, поэтому, если у кого-то есть предложения, которые я тоже смотрю 🙂

EDIT: я был ограничен 5-значным идентификатором ([a-zA-z0-9] {5,5}), тем больше идентификатор (больше комбинации, несколько коллизий). Например, md5 электронной почты почти никогда не конфликтует.

Проблема в том, что если вы производите случайные числа, очень возможно создавать дубликаты бесконечно.

Однако:

<?php //Lets assume we already have a connection to the db $sql = "SELECT randField FROM tableName"; $result = mysql_query($sql); $array = array(); while($row = mysql_fetch_assoc($result)) { $array[] = $row['randField']; } while(True) { $rand = rand(0, 999999); if(!in_array($rand)) { //This number is not in the db so use it! break; } } ?> 

Хотя это будет делать то, что вы тоже хотите, это плохая идея, так как это не будет масштабироваться долго, в конечном итоге ваш массив станет большим, и для создания случайного, который еще не находится в вашем db, потребуется очень много времени ,

Легко спроектировать генератор псевдослучайных чисел с длительным периодом ненаправления; например, этот , который используется для того же, за что вы хотите.

Кстати, почему бы просто не просто выпустить идентификатор пользователя?

Мне нравится идея Oddthinking, но вместо того, чтобы выбирать самую сильную хеш-функцию в мире, вы могли бы просто:

• Сгенерируйте MD5 из первых 10 миллионов чисел (выраженных как строки + соль)
• Проверяйте дубликаты в автономном режиме , т.е. перед тем, как начать работу (я думаю, их не будет)
• Хранить дубликаты в массиве где-то
• Когда ваше приложение запускается, загрузите массив
• Когда вы хотите вставить идентификатор, выберите следующий номер, вычислите его MD5, проверьте, находится ли он в массиве, и если он не использует его как идентификатор в базе данных. В противном случае выберите следующий номер

MD5 быстро, и проверка того, что строка принадлежит массиву, позволит вам выбрать SELECT.

Если вы действительно хотите получить «случайные» цифры от 0 до 9 999 999, тогда решение должно выполнить «рандомизацию» один раз, а затем сохранить результат на ваш диск.

Нетрудно получить желаемый результат, но я думаю, что это больше похоже на «сделать длинный список с цифрами», чем «получить случайное число».

 $array = range(0, 9999999); $numbers = shuffle($array); 

Вам также нужен указатель на текущую позицию в $ numbers (сохранить его в базе данных); начинайте с 0 и увеличивайте его каждый раз, когда вам нужен новый номер. (Или вы можете использовать array_shift () или array_pop (), если вы не хотите использовать указатели.)

Правильный алгоритм PRNG (псевдослучайный генератор чисел) будет иметь время цикла, в течение которого он никогда не будет находиться в одном и том же состоянии. Если вы выставляете все состояние PRNG в количестве, полученном от него, вы получите число, гарантированное уникальным для периода генератора.

Простой PRNG, который делает это, называется « линейным конгруэнтным » PRNG, который выполняет итерацию формулы:

 X(i) = AX(i-1)|M 

Используя правую пару факторов, вы можете получить период 2 ^ 30 (приблизительно 1 миллиард) от простого PRNG с 32-битным аккумулятором. Обратите внимание, что вам понадобится временная переменная длиной 64 бит, чтобы удерживать промежуточную «AX» часть вычисления. Большинство, если не все компиляторы C будут поддерживать этот тип данных. Вы также должны иметь возможность делать это с числовым типом данных на большинстве диалектов SQL.

При правильных значениях A и M мы можем получить генератор случайных чисел с хорошими статистическими и геометрическими свойствами. Известная статья об этом написана Фишманом и Муром.

При M = 2 ^ 31 – 1 мы можем использовать значения A ниже для получения PRNG с хорошим длинным периодом (2 ^ 30 IIRC).

Хорошие значения A:

 742,938,285 950,706,376 1,226,874,159 62,089,911 1,343,714,438 

Обратите внимание, что этот тип генератора (по определению) не криптографически защищен. Если вы знаете последнее число, сгенерированное из него, вы можете предсказать, что он будет делать дальше. К сожалению, я считаю, что вы не можете получить криптографическую безопасность и гарантированную неповторяемость в одно и то же время. Для того, чтобы PRNG был криптографически защищен (например, Blum Blum Shub ), он не может выставить достаточное состояние в сгенерированном номере, чтобы можно было предсказать следующее число в последовательности. Поэтому внутреннее состояние шире, чем сгенерированное число, и (для обеспечения хорошей безопасности) период будет длиннее, чем количество возможных значений, которые могут быть сгенерированы. Это означает, что выставленный номер не будет уникальным в течение периода.

По аналогичным причинам то же самое относится к долгопериодическим генераторам, таким как Mersenne Twister.

Я на самом деле ранее написал статью об этом . Он использует тот же подход, что и ответ Роберта Гулда, но дополнительно показывает, как сократить блок-шифр до подходящей длины, используя xor folding, а затем, как сгенерировать перестановки в диапазоне, который не является степенью 2, сохраняя при этом свойство уникальности.

существует несколько способов сделать это одним из способов: построить массив с номерами 0000000 – 9999999, а затем выбрать случайный выбор этих чисел в этом массиве и поменять выбранные значения чисел с максимальным значением Max, а затем уменьшить max на 1 и выберите другой случайный элемент этого массива до нового максимума

каждый раз уменьшая Макс одним

например (в основном): (справа – комментарии, которые должны быть удалены в реальной программе) Rndfunc – это вызов любой функции генератора случайных чисел, которую вы используете

 dim array(0 to 9999999) as integer for x% = 1 to 9999999 array(x%)=x% next x% maxPlus = 10000000 max =9999999 pickedrandom =int(Rndfunc*maxPlus) picks a random indext of the array based on how many numbers are left maxplus = maxplus-1 swap array(pickedrandom) , array(max) swap this array value to the current end of the array max = max -1 decrement the pointer of the max array value so it points to the next lowest place.. 

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

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

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

PHP уже имеет функцию для этого, uniqid . Он генерирует стандартный uuid, который является большим, если вам нужно получить доступ к данным из других источников. Не изобретайте велосипед.

Я, вероятно, не поймал ваш вопрос, но как насчет auto_increments?

Если вы хотите убедиться, что случайные числа не повторяются, вам понадобится не повторяющийся случайный генератор чисел (как описано здесь ).

Основная идея заключается в том, что следующая формула seed * seed & p произведет не повторяющиеся случайные числа для любого входа x such that 2x < p и p - x * x % p выведет все остальные случайные числа, не повторяющиеся, но только если p = 3 mod 4 . Таким образом, в основном все, что вам нужно, это однократное приближение до 9999999 насколько это возможно. Таким образом, усилие можно свести к одному полю чтения, но с недостатком, который генерирует либо слишком большие идентификаторы, либо генерируется слишком мало идентификаторов.

Этот алгоритм не перестраивается очень хорошо, поэтому я бы рекомендовал комбинировать его либо с XOR, либо с добавлением или каким-либо другим подходом, чтобы изменить точное значение без разрушения отношения 1-к-1 между семенами и их сгенерированным значением.