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

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

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

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

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

Это не оптимально, поэтому, если у кого-то есть предложения, я тоже ищу :)

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

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

[Редактировать] Дополнительная информация

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

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

[Спасибо Адам Лисс и CesarB за подробное описание решения]

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

тем не мение:

<?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;
     }
 }
?>

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

Предполагая:

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

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

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

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

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

Хотите превосходное решение?

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

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

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

Передайте их в инструмент, который генерирует Идеальные хеш-функции, например gperf.

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

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

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

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

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

Попробуйте инструкцию в mysql ВЫБРАТЬ CAST (RAND () * 1000000 AS INT)

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

Я, наверное, не уловил твою мысль, но как насчет auto_increments?

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

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

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

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

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

Простой ГПСЧ, который делает это, называется ГПСЧ «Линейный конгруэнтный», который повторяет формулу:

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

Используя правильную пару факторов, вы можете получить период 2 ^ 30 (приблизительно 1 миллиард) из простого ГПСЧ с 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 был криптографически безопасным (например, Блюм Блюм Шуб), он не может раскрыть достаточное состояние в сгенерированном числе, чтобы можно было предсказать следующее число в последовательности. Следовательно, внутреннее состояние шире, чем сгенерированное число, и (для обеспечения хорошей безопасности) период будет больше, чем количество возможных значений, которые могут быть сгенерированы. Это означает, что выставленный номер не будет уникальным в течение периода.

По тем же причинам то же самое верно и для генераторов с большим периодом, таких как Мерсенн Твистер..

есть несколько способов сделать это, один из них - построить массив с числами от 0000000 до 9999999, а затем выбрать случайный выбор этих чисел в этом массиве и поменяйте местами выбранные значения чисел с наивысшим значением Макс. затем уменьшите 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..

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

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

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

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

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

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