Мне нужно сгенерировать около 9-100 миллионов неповторяющихся случайных чисел, от нуля до количества сгенерированных чисел, и мне нужно, чтобы они генерировались очень быстро. В нескольких ответах на похожие вопросы предлагалось просто перетасовать массив для получения случайных чисел, а в других предлагалось использовать фильтр Блума. Вопрос в том, какой из них более эффективен, и, если это фильтр Блума, как мне его использовать?
неповторяющиеся случайные числа
comment
Невозможно ответить на этот вопрос без реальных цифр. Сколько случайных чисел вам нужно, какого типа и какого диапазона, и какие другие ограничения вы не упомянули? Действительно большой не имеет смысла. Вы имеете в виду больше, чем поместится в памяти?
- person Lee Daniel Crocker schedule 11.08.2013
comment
Мне нужно около 9-100 миллионов случайных чисел, в диапазоне от нуля до количества сгенерированных чисел, а это означает, что память не очень большая проблема, но мне действительно нужен эффективный алгоритм, и я не уверен, сколько времени он отнимает будет хранить сгенерированные числа, а затем проверять, существуют ли они уже в хранилище, как предлагает ROOt_R3z. Спасибо за комментарий
- person user2635469 schedule 11.08.2013
comment
Насколько случайными они должны быть? Является ли безопасность проблемой?
- person sh1 schedule 14.08.2013
Ответы (2)
Вам вообще не нужны случайные числа. Вам нужны именно числа от 0 до N-1 в случайном порядке.
Простое заполнение массива и перетасовка должны быть очень быстрыми. Правильная перетасовка Фишера-Йейтса — это O(n), поэтому массив из 100 миллионов должен занять меньше секунды в C или даже в Java, немного медленнее в языке более высокого уровня, таком как Python.
Вам нужно только сгенерировать N-1 случайных чисел, чтобы выполнить перетасовку (возможно, до 1,3N, если вы используете выборку отклонения для достижения идеальной однородности), поэтому скорость будет во многом зависеть от того, насколько быстр ваш ГСЧ.
Вам никогда не придется искать, было ли уже сгенерировано число; это будет смертельно медленно, независимо от того, какой алгоритм вы используете, особенно ближе к концу прогона.
Если вам нужно чуть меньше N общих чисел, заполните массив от 0 до N-1, затем просто прервите перетасовку раньше и возьмите частичный результат. Только в том случае, если количество необходимых вам чисел очень мало по сравнению с их диапазоном, вы должны рассмотреть подход с генерацией и проверкой дубликатов. В этом случае алгоритм Боба Флойда может быть хорош.
person
Lee Daniel Crocker
schedule
12.08.2013
В качестве альтернативы вы можете использовать блочный шифр соответствующего размера. Используйте блочный шифр, чтобы зашифровать числа 0, 1, 2, ..., и вы получите ряд неповторяющихся случайных чисел. Какая именно серия будет зависеть от используемого вами ключа. Они гарантированно не повторяются, потому что блочный шифр — это обратимая перестановка.
Для 64-битных номеров используйте DES, для 32-битных используйте Hasty Pudding (который допускает широкий диапазон размеров блоков) или напишите свой собственный простой шифр Фейстеля. Предполагая, что безопасность не является большой проблемой для этого, возможно написать свой собственный.
person
rossum
schedule
12.08.2013
