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

Question

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

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

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

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

Спасибо.

Answer 1

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

---

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

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

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

[Благодарю Адама Лисса & CesarB за расширение на решение]

Answer 2

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

Answer 3

Хотите сверхурочное решение?

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

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

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

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

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

Answer 4

Попробуйте утверждение в MySQL ВЫБЕРИТЕ CAST (RAND () * 1000000 AS INT)

Answer 5

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

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

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

Answer 6

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

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

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

РЕДАКТИРОВАТЬ: я был ограничен 5-значным идентификатором ([a-zA-z0-9] {5,5}), чем длиннее идентификатор (чем больше комбинация, тем меньше коллизий). Например, md5 сообщения почти никогда не будет конфликтовать.

Answer 7

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

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

Answer 8

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

однако:

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

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

Answer 9

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

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

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

Answer 10

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

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