неповторяющиеся случайные числа

Question

Мне нужно генерировать около 9-100 миллионов неповторяющихся случайных чисел, начиная от нуля до количества генерируемых чисел, и мне нужно, чтобы они были сгенерированы очень быстро. Несколько ответов на подобные вопросы предложили просто перетасовать массив, чтобы получить случайные числа, а другие предложили использовать фильтр цветения. Вопрос в том, какой из них более эффективен, и в случае, если он является фильтром цветка, как его использовать?

Answer 1

Вам не нужны случайные числа. Вы хотите точно цифры от 0 до N-1 в случайном порядке.

Простое заполнение массива и перетасовка должны быть очень быстрыми. Правильный перебор Fisher-Yates - O (n), поэтому массив из 100 миллионов должен занять до секунды на C или даже Java, немного медленнее на языке более высокого уровня, таком как Python.

Вам нужно только создать случайные числа N-1, чтобы сделать случайный выбор (возможно, до 1.3N, если вы используете отбор проб для получения идеальной однородности), поэтому скорость будет зависеть в значительной степени от того, насколько быстро ваш RNG.

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

Если вам нужно немного меньше N суммарных чисел, заполните массив от 0 до N-1, а затем просто отмените перетасовку раньше и выполните частичный результат. Только если количество нужных вам чисел очень мало по сравнению с их диапазоном, если вы рассматриваете подход «генерировать-и-check-for-dups». В этом случае алгоритм Боба Флойда может быть хорошим.

Answer 2

В качестве альтернативы вы можете использовать блок-шифр соответствующего размера. Используйте шифр блока для шифрования чисел 0, 1, 2, ... и вы получите серию неповторяющихся случайных чисел. Точно, какая серия будет зависеть от используемого вами ключа. Им гарантировано не повторяться, потому что блок-шифр является обратимой перестановкой.

Для 64-разрядных номеров используется DES, для 32-разрядного использования Hasty Pudding (что позволяет использовать большой диапазон размеров блоков) или написать свой собственный простой Feistel cypher. Предполагая, что безопасность не является большой проблемой для этого, тогда можно написать собственное.