Generate big random sequence of unique numbers

Question

I need to fill a file with a lot of records identified by a number (test data). The number of records is very big, and the ids should be unique and the order of records should be random (or pseudo-random).

I tried this:

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

But it's eating all of my memory.

Is there a way to generate a big shuffled sequence of consecutive (not necessarily but it would be nice, otherwise unique) integer numbers? Using a generator and not keeping all the sequence in RAM?

Answer 1

If you have 100 million numbers like in the question, then this is actually manageable in-memory (it takes about 0.5 GB).

As DSM pointed out, this can be done with the standard modules in an efficient way:

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

---

It is also possible to use the third-party NumPy package, which is the standard Python tool for managing arrays in an efficient way:

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

(this is only useful if your program already uses NumPy, as the standard module approach is about as efficient).

---

Both method take about the same amount of time on my machine (maybe 1 minute for the shuffling), but the 0.5 GB they use is not too big for current computers.

PS: There are too many elements for the shuffling to be really random because there are way too many permutations possible, compared to the period of the random generators used. In other words, there are fewer Python shuffles than the number of possible shuffles!

Answer 2

Maybe something like (won't be consecutive, but will be unique):

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 3

You can fetch random int easily from reading (on linux) /dev/urandom or using os.urandom() and struct.unpack():

Return a string of n random bytes suitable for cryptographic use.

This function returns random bytes from an OS-specific randomness source. The returned data should be unpredictable enough for cryptographic applications, though its exact quality depends on the OS implementation. On a UNIX-like system this will query /dev/urandom, and on Windows it will use CryptGenRandom. If a randomness source is not found, NotImplementedError will be raised.

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

While on the other hand random package:

However, being completely deterministic, it is not suitable for all purposes, and is completely unsuitable for cryptographic purposes.

If you really need unique records you should go with this or answer provided by EOL.

But assuming really random source, with possibly repeated characters you'll have 1/N (where N = 2 ** sizeof(int)*8 = 2 ** 32) chance of hitting item at first guess, thus you can get (2**32) ** length possible outputs.

On the other hand when 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)!

Where ! is factorial, not logical negation. So you'll just decrease randomness of result.

Answer 4

This one will keep your memory OK but will probably kill your disk :)

It generates a file with the sequence of the numbers from 0 to 100000000 and then it randomly pick positions in it and writes to another file. The numbers have to be re-organized in the first file to "delete" the numbers that have been chosen already.

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"