Genera una grande sequenza casuale di numeri univoci

Question

Ho bisogno di riempire un file con molti record identificati da un numero (dati di test). Il numero di record è molto grande e gli ID dovrebbero essere unici e l'ordine dei record dovrebbe essere casuale (o pseudo-casuale).

ho provato questo:

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

ma è mangiare tutta la mia memoria.

C'è un modo per generare una grande sequenza mescolata di numeri interi consecutivi (non necessariamente ma sarebbe bello, altrimenti unico)? Usando un generatore e non mantenendo tutta la sequenza nella RAM?

Answer 1

Se si dispone di 100 milioni di numeri come nella domanda, questo in realtà è gestibile in memoria (ci vogliono circa 0,5 GB).

Come DSM sottolineato, questo può essere fatto con i moduli standard in modo efficiente:

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

---

È anche possibile utilizzare il pacchetto NumPy terze parti, che è lo standard di Python strumento per gestire gli array in modo efficiente:

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

(questo è utile solo se il programma utilizza già NumPy, come l'approccio modulo standard è quanto di più efficiente).

---

Sia metodo di prendere circa la stessa quantità di tempo sulla mia macchina (forse 1 minuto per la rimescolamento), ma il 0,5 GB che usano non è troppo grande per i computer attuali.

PS: Ci sono troppi elementi per il mescolamento sia veramente casuale perché ci sono troppi permutazioni possibili, rispetto al periodo dei generatori casuali utilizzati. In altre parole, ci sono meno mescolanze di Python rispetto al numero di possibili mescolanze!

Answer 2

Si possono scaricare i int casuale facilmente dalla lettura (su Linux) /dev/urandom o utilizzando os.urandom() e struct.unpack():

Restituisce una stringa di byte n casuali adatti per l'uso di crittografia.

Questa funzione restituisce byte casuali da una sorgente di casualità specifica del sistema operativo. I dati restituiti dovrebbero essere abbastanza imprevedibili per le applicazioni crittografiche, sebbene la sua esatta qualità dipenda dall'implementazione del sistema operativo. Su un sistema simile a UNIX questo interrogherà /dev/urandom, e su Windows utilizzerà CryptGenRandom. Se non viene trovata una fonte di casualità, verrà sollevato l'errore NotImplementedError.

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

Mentre d'altra parte pacchetto random:

Tuttavia, essendo completamente deterministico, non è adatto a tutti gli effetti, ed è completamente inadatto per scopi crittografici.

Se davvero bisogno record univoci si dovrebbe andare con this o answer provided by EOL.

Ma supponendo fonte veramente casuale, con personaggi possibilmente ripetuti avrete 1/N (dove N = 2 ** sizeof(int)*8 = 2 ** 32) possibilità di colpire elemento alla prima ipotesi, in tal modo è possibile ottenere (2**32) ** length possibili uscite.

D'altra parte, quando 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)! 

Dove ! è fattoriale, non negazione logica. Quindi diminuirai la casualità del risultato.

Answer 3

Forse qualcosa di simile (non sarà consecutiva, ma sarà unica):

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

Questo manterrà la vostra memoria OK ma probabilmente uccidere il vostro disco :)

Si genera un file con la sequenza dei numeri da 0 a 100000000 e quindi seleziona in modo casuale le posizioni in esso e scrive in un altro file. I numeri devono essere riorganizzati nel primo file per "cancellare" i numeri che sono già stati scelti.

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"