Создать большую случайную последовательность уникальных чисел

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

Я пробовал это:

# coding: utf-8
import random

COUNT = 100000000

random.seed(0)
file_1 = open('file1', 'w')
for i in random.sample(xrange(COUNT), COUNT):
    file_1.write('ID{0},A{0}\n'.format(i))
file_1.close()

Но он ест всю мою память.

Есть ли способ генерировать большую перетасованную последовательность последовательных (не обязательно, но это было бы красиво, иначе уникально) целые числа? Используя генератор и не сохраняя всю последовательность в ОЗУ?

Ответ 1

Если у вас есть 100 миллионов номеров, как в вопросе, то это фактически управляемое в памяти (оно занимает около 0,5 ГБ).

Как указывал DSM, это можно сделать с помощью стандартных модулей эффективным образом:

>>> import array
>>> a = array.array('I', xrange(10**8))  # a.itemsize indicates 4 bytes per element => about 0.5 GB
>>> import random                                                               
>>> random.shuffle(a)

Также возможно использовать сторонний пакет NumPy, который является стандартным инструментом Python для эффективного управления массивами:

>>> import numpy
>>> ids = numpy.arange(100000000, dtype='uint32')  # 32 bits is enough for numbers up to about 4 billion
>>> numpy.random.shuffle(ids)

(это полезно, только если ваша программа уже использует NumPy, поскольку стандартный подход к модулю примерно такой же эффективный).

Оба метода занимают примерно такое же количество времени на моей машине (возможно, 1 минуту для перетасовки), но 0,5 ГБ, которые они используют, не слишком велики для текущих компьютеров.

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

Ответ 2

Может быть, что-то вроде (не будет последовательным, но будет уникальным):

from uuid import uuid4

def unique_nums():  # Not strictly unique, but *practically* unique
    while True:
        yield int(uuid4().hex, 16)
        # alternative yield uuid4().int

unique_num = unique_nums()
next(unique_num)
next(unique_num) # etc...

Ответ 3

Вы можете легко получить случайную информацию из чтения (в linux) /dev/urandom или используя os.urandom() и struct.unpack():

Возвращает строку из n случайных байтов, подходящих для использования в криптографии.

Эта функция возвращает случайные байты из источника случайности, специфичного для ОС. Возвращенные данные должны быть непредсказуемыми для криптографических приложений, хотя его точное качество зависит от реализации ОС. В UNIX-подобной системе это будет запрашивать /dev/urandom, а в Windows он будет использовать CryptGenRandom. Если источник случайности не найден, будет добавлен NotImplementedError.

>>> for i in range(4): print( hex( struct.unpack('<L', os.urandom(4))[0]))
... 
0xbd7b6def
0xd3ecf2e6
0xf570b955
0xe30babb6

В то время как с другой стороны random package:

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

Если вам действительно нужны нужны уникальные записи, вы должны пойти с этим или ответом, предоставленным EOL.

Но если предположить, что действительно случайный источник, возможно, с повторяющимися символами, у вас будет 1/N (где N = 2 ** sizeof(int)*8 = 2 ** 32) вероятность попадания элемента с первого раза, поэтому вы можете получить (2**32) ** length возможные выходы.

С другой стороны, когда используя только уникальные результаты, вы будете иметь max:

product from i = 0 to length {2*32 - i} 
               = n! / (n-length)!
               = (2**32)! / (2**32-length)!

Где ! - факториальное, а не логическое отрицание. Таким образом, вы просто уменьшите случайность результата.

Ответ 4

Это сохранит вашу память в порядке, но, вероятно, убьет ваш диск:)

Он генерирует файл с последовательностью чисел от 0 до 100000000, а затем он произвольно выбирает позиции в нем и записывает в другой файл. Цифры должны быть реорганизованы в первом файле для "удаления" уже выбранных чисел.

import random

COUNT = 100000000

# Feed the file
with open('file1','w') as f:
    i = 0
    while i <= COUNT:
        f.write("{0:08d}".format(i))
        i += 1

with open('file1','r+') as f1:
    i = COUNT
    with open('file2','w') as f2:
        while i >= 0:
            f1.seek(i*8)
            # Read the last val
            last_val = f1.read(8)
            random_pos = random.randint(0, i)
            # Read random pos
            f1.seek(random_pos*8)
            random_val = f1.read(8)
            f2.write('ID{0},A{0}\n'.format(random_val))
            # Write the last value to this position
            f1.seek(random_pos*8)
            f1.write(last_val)
            i -= 1
print "Done"