умный способ генерировать уникальное случайное число

Question

Я хочу сгенерировать последовательность уникальных случайных чисел в диапазоне от 00000001 до 99999999.

Таким образом, первое может быть 00001010, второе 40002928 и т. Д.

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

Есть ли более умный способ?

РЕДАКТИРОВАТЬ, как и всегда, я забыл сказать, ПОЧЕМУ я хотел этого,и это, вероятно, прояснит ситуацию и, возможно, даст альтернативу, и это так: мы хотим сгенерировать номер заказа для бронирования, чтобы мы могли просто использовать 000001, 000002 и т. д. Но мы не хотим дать конкурентам подсказкусколько заказов создано (потому что это не большой объем рынка, и мы не хотим, чтобы они знали, находимся ли мы на 30-ом заказе через 2 месяца или на 100-м заказе.мы хотим, чтобы номер заказа был случайным (но уникальным)

Answer 1

Вы можете использовать либо линейный конгруэнтный генератор (LCG), либо регистр сдвига с линейной обратной связью (LFSR).Google или Википедия для получения дополнительной информации.

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

Обновление: я должен добавить, что нет необходимости предварительно рассчитывать или предварительно сохранять предыдущие значенияВ любом случае вам нужно только сохранить предыдущее начальное значение (single int) и вычислить «по требованию» следующее число в последовательности.Конечно, вы можете при желании сохранить цепочку предварительно рассчитанных чисел в вашей БД, но в этом нет необходимости.

Answer 2

Как насчет создания набора всех возможных чисел и простой рандомизации порядка?Затем вы можете просто выбрать следующий номер из хвоста.

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

Answer 3

Вы могли бы построить таблицу со всеми возможными числами в ней, присвоить записи «используемое» поле.

1. Выбрать все записи, которые не были «использованы»
2. Выбрать случайное число (r) от 1 до количества записей
3. Взять номер записи r
4. Получите ваше «случайное значение» из записи
5. Установите флаг «used» и обновите БД.

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

Answer 4

Используйте генераторы псевдослучайных чисел.

Например - Генератор линейных конгруэнтных случайных чисел

(если приращение и n взаимно просты, то код сгенерирует все числа от 0 до n-1):

    int seed = 1, increment = 3;
    int n = 10;

    int x = seed;
    for(int i = 0; i < n; i++)
    {
        x = (x + increment) % n;
        Console.WriteLine(x);
    }

Выход: 4 7 0 3 6 9 2 5 8 1

Основные генераторы случайных чисел

Mersenne Twister

Answer 5

Использование этого алгоритма может быть целесообразным, хотя и занимает много памяти: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle Поместите числа в массив от 1 до 99999999 и сделайте перемешивание.

Answer 6

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

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

Answer 7

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

Искусство компьютерного программирования, Том 2: Полу численные алгоритмы

Дональдом Кнутом. Глава 3 посвящена случайным числам.

Answer 8

Я должен был сделать что-то подобное раньше (создать «случайный» номер для части URL). Я создал список ключей, сгенерированных случайным образом. Каждый раз, когда ему требовался новый номер, он просто случайным образом выбирал номер из ключей. Подсчитайте и XOR ключ и данный порядковый номер, затем выведите значение XORed (в базе 62) с префиксом индекса ключей (в базе 62). Я также проверяю вывод, чтобы убедиться, что он не содержит никаких пустых слов. Если это так, просто возьмите следующий ключ и сделайте второй ход. Расшифровка числа одинаково проста (первая цифра - это индекс к используемому ключу, простой XOR, и все готово).

Мне нравится ответ Андоры , если вы генерируете новые числа и могли бы использовать их, если бы я знал. Однако, если бы я сделал это снова, я бы просто использовал UUIDs . Большинство (если не каждая) платформа имеет метод для их генерации, и длина не является проблемой для URL.

Answer 9

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

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

Answer 10

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

id = startValue + (totalNumberOfAccounts * inctrementalNumber)

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

id = startValue + (totalNumberOfAccounts * inctrementalNumber) + totalConflicts