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

Question

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

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

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

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

Спасибо.

Answer 1

Есть несколько способов сделать это: создать массив с номерами от 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..

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

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

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

Answer 2

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

Простой PRNG, который делает это, называется ' Linear Congruential ' PRNG, который повторяет формулу:

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

Используя правильную пару факторов, вы можете получить период 2 ^ 30 (приблизительно 1 миллиард) от простого PRNG с 32-разрядным аккумулятором. Обратите внимание, что вам понадобится временная переменная длиной 64 бита для хранения промежуточной части AX вычисления. Большинство, если не все компиляторы Си будут поддерживать этот тип данных. Вы также должны иметь возможность делать это с числовым типом данных на большинстве диалектов 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 3

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

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

Answer 7

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