Генерация неповторяющихся случайных чисел в 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

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

Если вы думаете, что может быть кто-то, кто серьезно заинтересован в угадывании следующих значений, вы можете использовать базу данных.Последовательность для подсчета значений, которые вы генерируете, и шифрование их с помощью алгоритма шифрования или другого криптографически стойкого совершенного имеет функцию.Однако вам следует позаботиться о том, чтобы алгоритм шифрования не был легко взломанным, если можно получить последовательность сгенерированных вами последовательных чисел - например, простой RSA не сделает этого из-за Атака, связанная с сообщением Франклина-Рейтера .

Answer 2

Я начал пытаться написать объяснение использованного ниже подхода, но просто реализовать его было проще и точнее. У этого подхода странное поведение: чем быстрее вы сгенерируете число, тем быстрее оно будет. Но это работает и не требует, чтобы вы генерировали все числа заранее.

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

import random

class NonRepeatingRandom(object):

    def __init__(self, maxvalue):
        self.maxvalue = maxvalue
        self.used = set()

    def next(self):
        if len(self.used) >= self.maxvalue:
            raise StopIteration
        r = random.randrange(0, self.maxvalue - len(self.used))
        result = 0
        for i in range(1, r+1):
            result += 1
            while result in self.used:
                 result += 1
        self.used.add(result)
        return result

    def __iter__(self):
        return self

    def __getitem__(self):
        raise NotImplemented

    def get_all(self):
        return [i for i in self]

>>> n = NonRepeatingRandom(20)
>>> n.get_all()
[12, 14, 13, 2, 20, 4, 15, 16, 19, 1, 8, 6, 7, 9, 5, 11, 10, 3, 18, 17]

Answer 3

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

Answer 4

Вы заявляете, что храните числа в базе данных.

Не проще ли будет хранить там все числа и запрашивать в базе данных случайное неиспользуемое число? Большинство баз данных поддерживают такой запрос.

Примеры

MySQL:

SELECT column FROM table
ORDER BY RAND()
LIMIT 1

PostgreSQL:

SELECT column FROM table
ORDER BY RANDOM()
LIMIT 1

Answer 5

Чтобы сформировать список полностью случайных чисел в пределах определенного порога, следующим образом:

plist=list()
length_of_list=100
upbound=1000
lowbound=0
while len(pList)<(length_of_list):
     pList.append(rnd.randint(lowbound,upbound))
     pList=list(set(pList))

Answer 6

Я столкнулся с той же проблемой и открыл вопрос с другим названием , прежде чем перейти к этому. Мое решение - это генератор случайных выборок индексов (т.е. неповторяющихся чисел) в интервале [0,maximal), называемый itersample.Вот несколько примеров использования:

import random
generator=itersample(maximal)
another_number=generator.next() # pick the next non-repeating random number

или

import random
generator=itersample(maximal)
for random_number in generator:
    # do something with random_number
    if some_condition: # exit loop when needed
        break

itersample генерирует неповторяющиеся случайные целые числа, потребность в памяти ограничена выбранными числами и временем, необходимым для выбора n цифры должны быть (как подтверждают некоторые тесты) O(n log(n)), регистр maximal.

Вот код itersample:

import random
def itersample(c): # c = upper bound of generated integers
    sampled=[]
    def fsb(a,b): # free spaces before middle of interval a,b
        fsb.idx=a+(b+1-a)/2
        fsb.last=sampled[fsb.idx]-fsb.idx if len(sampled)>0 else 0
        return fsb.last
    while len(sampled)<c:
        sample_index=random.randrange(c-len(sampled))
        a,b=0,len(sampled)-1
        if fsb(a,a)>sample_index:
            yielding=sample_index
            sampled.insert(0,yielding)
            yield yielding
        elif fsb(b,b)<sample_index+1:
            yielding=len(sampled)+sample_index
            sampled.insert(len(sampled),yielding)
            yield yielding
        else: # sample_index falls inside sampled list
            while a+1<b:
                if fsb(a,b)<sample_index+1:
                    a=fsb.idx
                else:
                    b=fsb.idx
            yielding=a+1+sample_index
            sampled.insert(a+1,yielding)
            yield yielding

Answer 7

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

Подумайте о хэш-хе ... вам на самом деле не нужна вся эта штука. Делайте то, что делают git или другие службы сокращения URL, и берите первые 3/4/5 символов хеша. Учитывая, что каждый символ теперь имеет 36 возможных значений вместо 10, у вас есть 2 176 782 336 комбинаций вместо 999 999 комбинаций (для шести цифр). Объедините это с быстрой проверкой того, существует ли комбинация (запрос с чистым индексом) и начальным числом, таким как отметка времени + случайное число, и это должно применяться практически в любой ситуации.