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

Question

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

Я попытался это:

# 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() 

Но это едят все моей памяти.

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

Answer 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 меньше, чем количество возможных перетасовки!

Answer 2

Вы можете получить случайный Int легко от чтения (на Linux) /dev/urandom или с помощью os.urandom() и struct.unpack():

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

Эта функция возвращает случайные байты из источника случайности, специфичного для ОС. Возвращенные данные должны быть непредсказуемыми для криптографических приложений, хотя его точное качество зависит от реализации ОС. В 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 пакет:

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

Если вы действительно нужно уникальные записи, вы должны пойти с this или answer provided by EOL.

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

С другой стороны, когда using just unique results you'll have max:

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

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

Answer 3

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

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... 

Answer 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"