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

Question

Хорошо, это один из тех хитрых вопросов, которые звучат, поэтому я перехожу к переполнению стека, потому что не могу придумать хорошего ответа. Вот что я хочу: мне нужно, чтобы Python генерировал простой список чисел от 0 до 1 000 000 000 в случайном порядке, который будет использоваться для серийных номеров (с использованием случайного числа, чтобы вы не могли сказать, сколько из них было назначено, или выполнить синхронизацию атакует так же легко, то есть угадывает следующую, которая появится). Эти числа хранятся в таблице базы данных (индексируются) вместе с информацией, связанной с ними. Программа, генерирующая их, не работает вечно, поэтому она не может полагаться на внутреннее состояние.

Ничего страшного, верно? Просто сгенерируйте список чисел, поместите их в массив и используйте Python «random.shuffle (big_number_array)», и все готово. Проблема в том, что я хотел бы избежать необходимости хранить список чисел (и, таким образом, прочитать файл, вытолкнуть его сверху, сохранить файл и закрыть его). Я бы лучше сгенерировал их на лету. Проблема в том, что решения, о которых я могу думать, имеют проблемы:

1) Создайте случайное число, а затем проверьте, было ли оно уже использовано. Если он использовался, создайте новый номер, проверьте, повторяйте по мере необходимости, пока я не найду неиспользованный. Проблема в том, что мне может не повезти, и я сгенерирую много использованных чисел, прежде чем получу одно неиспользованное число. Возможное решение: используйте очень большой пул чисел, чтобы уменьшить шансы на это (но тогда я получу глупые длинные числа).

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

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

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

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

6) Добавлять или добавлять информацию, основанную на времени, к случайному числу (т. Е. Метку времени unix), чтобы уменьшить вероятность столкновения, и опять я получаю большие числа, чем мне нужно.

У любого есть какие-нибудь умные идеи, которые уменьшат шансы на «столкновение» (т. Е. Генерирование уже взятого случайного числа), но также позволят мне сохранить число «маленьким» (т. Е. Менее миллиарда (или тысяча миллионов для ваших европейцев =)).

Ответ и почему я его принял:

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

Answer 1

Это аккуратная проблема, и я некоторое время думал об этом (с решениями, похожими на Sjoerd's ), но в конце вот что я думаю:

Используй свою точку 1) и перестань беспокоиться.

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

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

Даже если вы близки к тому, чтобы выбрать миллиард номеров ранее, вероятность того, что ваш новый номер уже занят, все равно составляет всего 0,1%.

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

Вы выиграете в лотерею до того, как этот запасной вариант когда-нибудь будет использован.

Answer 2

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

Блочные шифры обычно имеют фиксированный размер блока, например 64 или 128 бит. Но шифрование, сохраняющее формат, позволяет вам взять стандартный шифр, такой как AES, и сделать шифр меньшей ширины с любой шириной и шириной (например, 10, ширина 9 для параметров вопроса) с алгоритмом, который все еще работает. криптографически устойчивый.

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

AES-FFX является одним из предложенных стандартных методов для достижения этой цели.

Я экспериментировал с некоторым базовым кодом Python для AES-FFX - см. Код Python здесь (но учтите, что он не полностью соответствует спецификации AES-FFX). Это может, например, зашифровать счетчик до случайного 7-значного десятичного числа. E.g.:

0000000   0731134
0000001   6161064
0000002   8899846
0000003   9575678
0000004   3030773
0000005   2748859
0000006   5127539
0000007   1372978
0000008   3830458
0000009   7628602
0000010   6643859
0000011   2563651
0000012   9522955
0000013   9286113
0000014   5543492
0000015   3230955
...       ...

Для другого примера в Python, использующего другой не AES-FFX (я думаю) метод, см. это сообщение в блоге «Как создать номер счета» , в котором FPE использует шифр Фейстеля. Генерирует числа от 0 до 2 ^ 32-1.

Answer 3

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

modulo = 87178291199 # prime
incrementor = 17180131327 # relative prime

current = 433494437 # some start value
for i in xrange(1, 100):
    print current
    current = (current + incrementor) % modulo

Answer 4

Если вам не нужно что-то криптографически безопасное, а просто «достаточно запутанное» ...

Поля Галуа

Вы можете попробовать операции в Полях Галуа , например. GF (2) ³² , чтобы отобразить простой инкрементный счетчик x на кажущийся случайным серийный номер y :

x = counter_value
y = some_galois_function(x)

• умножить на постоянную
  • Инверсия умножается на обратную величину постоянной
• Подъем к власти : x ⁿ
• Взаимное x ^-1
  • Особый случай поднятия к власти n
  • Это его собственная обратная
• Возведение в степень примитивного элемента: a ^x
  • Обратите внимание, что здесь нет легко вычисляемого обратного (дискретного логарифма)
  • Убедитесь, что a является примитивным элементом , он же генератор

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

Что касается поиска библиотеки для Galois Field для Python ... хороший вопрос. Если вам не нужна скорость (что вам не нужно для этого), то вы можете сделать свою собственную. Я не пробовал это:

• NZMATH
• Пакет Python для конечного поля
• Sage , хотя это целая среда для математических вычислений, гораздо больше, чем просто библиотека Python

Умножение матриц в GF (2)

Выберите подходящую 32 × 32 обратимую матрицу в GF (2) и умножьте на нее 32-битный входной счетчик. Это концептуально связано с LFSR, как описано в ответе S.Lott .

CRC

Связанная возможность заключается в использовании вычисления CRC . На основе остатка от длинного деления с неприводимым полиномом в GF (2). Код Python легко доступен для CRC ( crcmod , pycrc ), хотя вы можете выбрать другой неприводимый многочлен, который обычно используется для ваших целей. Я немного не уверен в теории, но я думаю, что 32-битный CRC должен генерировать уникальное значение для каждой возможной комбинации 4-байтовых входов. Проверь это. Экспериментально проверить это довольно просто, подав вывод обратно во вход и проверив, что он производит полный цикл длины 2 ³² -1 (ноль просто отображается в ноль). Вам может потребоваться избавиться от любых начальных / конечных XOR в алгоритме CRC, чтобы эта проверка работала.

Answer 5

Если они не должны быть случайными, но просто не должны быть линейными (1, 2, 3, 4, ...), то вот простой алгоритм:

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

max_value = 795028841
step = 360287471
previous_serial = 0
for i in xrange(0, max_value):
    previous_serial += step
    previous_serial %= max_value
    print "Serial: %09i" % previous_serial

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

s = set()
with open("test.txt", "w+") as f:
    previous_serial = 0
    for i in xrange(0, 2711):
        previous_serial += 1811
        previous_serial %= 2711
        assert previous_serial not in s
        s.add(previous_serial)

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

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

Answer 6

Я думаю, вы переоцениваете проблемы с подходом 1). Если у вас нет жестких требований в реальном времени, простая проверка по случайному выбору завершается довольно быстро. Вероятность того, что потребуется больше, чем количество итераций, уменьшается в геометрической прогрессии. При выводе 100M чисел (коэффициент заполнения 10%) у вас будет один шанс на миллиард, требующий более 9 итераций. Даже если вы взяли 50% номеров, в среднем вам потребуется 2 итерации, и у вас будет 1 шанс на миллиард, требующий более 30 проверок. Или даже крайний случай, когда 99% чисел уже взяты, все еще может быть разумным - вы в среднем получите 100 итераций и получите 1 из миллиарда, что потребует 2062 итерации

Answer 7

Стандартная начальная последовательность генератора линейных конгруэнтных случайных чисел НЕ МОЖЕТ повторяться до тех пор, пока не будет создан полный набор чисел из начального начального значения. Тогда это ДОЛЖНО точно повторяться.

Внутреннее начальное число часто большое (48 или 64 бита). Сгенерированные числа меньше (обычно 32 бита), потому что весь набор битов не является случайным. Если вы будете следовать начальным значениям, они сформируют отличную неповторяющуюся последовательность.

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

В Кнуте есть некоторые рекомендации по выбору подходящих семян, которые будут генерировать очень длинные последовательности уникальных чисел.

Answer 8

Мое решение https://github.com/glushchenko/python-unique-id, Я думаю, вы должны расширить матрицу на 1 000 000 000 вариантов и получать удовольствие.

Answer 9

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

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

Совершенно очевидно, что после того, как вы собрали 10 чисел, ваш пул возможных случайных чисел будет уменьшен на 10. Поэтому вы не должны выбирать число от 1 до 1.000.000, а от 1 до 999.990. Конечно, это число не является действительным числом, а является только индексом (если только 10 собранных чисел не были 999,991, 999,992,…); теперь вам нужно считать от 1, пропустив все собранные номера.

Конечно, ваш алгоритм должен быть умнее, чем просто считать от 1 до 1.000.000, но я надеюсь, что вы понимаете метод.

Я не люблю рисовать случайные числа, пока не получу подходящее. Это просто неправильно.

Answer 10

Ответ запоздал, но я нигде не видел, чтобы это предлагалось.

Почему бы не использовать модуль uuid для создания глобально уникальных идентификаторов