0

I ran the following command to generate 1 billion random numbers:

time shuf -i 1-1000000000 > "SHUF TEST 1"

To my surprise it was able to do this in less than 10 mins. I then ran the output file through uniq -d to determine how many of the generated numbers were duplicate, and was again surprised when it turned out to be 0. I also ran the output file through uniq -u and sort -u to confirm these results.

How is it that the shuf command is able to generate a billion random numbers in such a relatively short amount of time, and can I depend on its randomness? Note that I don't need a cryptographically secure random number generator for my needs, just something good enough to always return a unique number.

  • 1
    to determine how many of the generated numbers were duplicate, and was again surprised when it turned out to be 0shuf does not generate random numbers, it generates random permutation, random order. With -i 1-1000000000 one should expect each integer from this range to appear exactly once. No surprise at all. – Kamil Maciorowski Jun 30 at 17:23
  • 1
    As @KamilMaciorowski states, a "shuffling" algorithm creates an array of number 1 to n, then randomly switches pairs of numbers. Does it matter if the order is exactly duplicated each time it's run? Some algorithms start the random number generator at the same pint each time. – DrMoishe Pippik Jun 30 at 19:29
  • That makes sense now. Either one of you should feel free to add an answer along those lines. – Prometheus Jun 30 at 22:28
1

The shuf utility shuffles its input by outputting a random permutation of its input lines. According to it's manpage, "Each output permutation is equally likely". An analogy would be to shuffle a deck of cards.

If the input lines contain duplicates, the output from shuf will also contain duplicates. Why? Because shuf performs a random permutation of it's input. If the input lines contain no duplicates, the output from shuf will contain no duplicates.

In your example, shuf -i 1-1000000000, the -i option causes shuf to act as if it's input came from a file containing the range of unsigned decimal integers 1 through 1000000000, one unsigned integer per line. In other words, shuf acts as if it had 1000000000 lines of input with each line containing a unique unsigned integer. Hence there are no duplicates to be found in the output.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.