Sstrhsrtj

I need to generate nearly 1 Billion records of unique integers.
I tried with awk but it is not generating more than 5million records.
Below is what I had tried so far -

 awk -v loop=10000000000 -v range=10000000000 'BEGIN{

  srand()

  do {

    numb = 1 + int(rand() * range)

    if (!(numb in prev)) {

       print numb

       prev[numb] = 1

       count++

    }

  } while (count<loop)

}' 

But it is not generating more than 599160237 records and process got killed automatically

You could use GNU seq + sort to first generate a list of unique 1B integers (in sequential order), then sort -R to shuffle them randomly).
While this is not CPU-efficient, it is memory agnostic as sort will use as much memory as available, then revert to temporary files.

This will takes several minutes (depending on your machine's CPU/Ram/disk):

$ seq 1000000000 > 1B.txt



$ ls -lhog 1B.txt 

-rw-rw-r-- 1   9.3G Dec 26 17:31 1B.txt



$ sort -R 1B.txt > 1B.random.txt

If you have access to a machine with enough RAM you can use GNU shuf:

$ shuf -i 1-1000000000 > 1B.random.txt

Empirically, shuf needed ~8GB of free ram and ~6 minutes of runtime on my machine.

It will be better to use a program that will not allocate much of memory to complete the task. However, there is a problem with random number generation: if you need completely random numbers, then you need to use "good" random number source like /dev/urandom.

I think this C program can help you with this task. It generates numbers on the run, and with three arguments you specify: start int, end int and number of them to generate. So to generate a 100 ints in range in (0..200), you do:

./mkrnd 0 200 100

You probably will want a redirect to file, so do

./mkrnd 0 200 100 >randomints.txt

The compiling is simple, just do gcc mkrnd.c -o mkrnd (or I can compile it for you).

Believed to be fast enough, but still will require hours to work I think. For me on Athlon64 5000+:

% time null ./mkrnd 0 1000000000 10000000                                                          



real    0m33.471s

user    0m0.000s

sys 0m0.000s

Remove #if 0 ... #endif to make it grab random integers from /dev/urandom (maybe slower).

And about memory requirements: it takes only 4K RSS on musl system during all it's runtime.

EDIT: Replacing gettimeofday with clock_gettime gives double speed.

in python3.4 you can generate and play with huge numbers like this:

    #!/bin/python3.4

    import random

    print(random.sample(range(1, 1000000000000),1000000000))

this will print one billion unique numbers

if there is memory problem of allocating huge sample , then one can use the range and print the numbers in a loop , but that will be in a sequence , not random:

    x=range(1, 1000000000000)

    for i in x:

      print (i)     #or process i , whatever the operation is.

The reason for the process getting killed might be that awk has a bug/limitation in arrays that your code is hitting, or your code is just so space-consuming that it hits some process based limit.

I mean, you're trying to build an array with maximum index of 10 billion (based on the range) with 1 billion defined values. So, awk needs potentially to reserve space for 10 billion variables. I'm not familiar enough to tell how much space that would mean, but 10 billion 16 bit integers would mean 18.5 GB, and even if awk is clever in building such a sparse array, it would require over 1.8 GB just so store the numbers you're generating.

To be able to keep the results unique, you will need to have all the previous values somewhere, so it will necessarily be heavy on space requirements, but it might be that some other language would allow the algorithm to finish.

How to escape from the huge memory requirements, then?

A.Gordon presents one option, by relying on a sequence and just shuffling it for randomness. That works well when there is a requirement that the result should truly be numbers and you want them to be from a given range. If the range is more complex than from one to N, you could generate the sequence with awk and then pass it to sort -R. Also see my comment on the answer for how to make the range and the count of produced numbers be different.

One option could be to use a cryptographic (hash) function for producing the random numbers, but in that case you can't define the range to be 1 to N since those functions usually produce N bit output and you can't mangle the results without risking producing a collision (a duplicate number in the set).Such functions, however, would be guaranteed to easily produce 1 billion unique outputs (as those hash functions are designed to not produce the same output twice even with a extremely large number of repeated calls). Depending on the implementation, their output might not be numbers but strings, and one could possibly convert the string output to numbers, but since their output size is typically quite large, then range of the numbers resulting from the conversion would be really huge. You could start from this Stackoverflow question if you're interested in exploring this option.

If you can risk the chance of having a collision, even if that is rather unlikely, you could try using a good source of randomness (/dev/urandom is one option) to generate the 1 billion numbers. I don't know how likely it is that you could get 1 billion unique numbers from that, but trying it out would surely be worth the try. There is no memory-efficient way of telling if there is a duplicate in the result set, though, since that would require having all the numbers in memory for comparison.