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

Question

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

1) Наименьшее количество запросов к база данных выполнена. 2) Выполняется наименьшее количество обхода структуры данных в памяти.

По существу, идея состоит в том, чтобы сделать следующее

1) Создать случайное число от 0 до 9999999
2) Проверьте базу данных, чтобы увидеть, если номер существует
ИЛИ
2) Запрос к базе данных для все номера
3) Посмотрите, соответствует ли возвращаемый результат тому, что пришло из db
4) Если он совпадает, повторите шаг 1, если проблема не решена.

Спасибо.

Answer 1

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

---

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

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

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

[Благодаря Адам Liss & CesarB для exapanding на решение]

Answer 2

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

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

Answer 3

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

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

Это не является оптимальным, так что если у кого-то есть предложения, я смотрю тоже :)

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

Answer 4

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

однако:

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

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

Answer 8

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

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

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

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

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

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

Answer 9

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

Answer 10

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

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

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

Answer 11

Попробуйте заявление в тузд SELECT CAST (RAND() * 1000000 AS INT)

Answer 12

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

Answer 13

Я, вероятно, не понял вашу точку зрения, но как насчет auto_increments?

Answer 14

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

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

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

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

Answer 15

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

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

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.

Answer 16

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

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

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

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

Answer 17

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

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

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