Geek asks and answers

Non repeating random numbers

I need to create about 9-100 million non-repeating random numbers, ranging from zero to the number of generated numbers, and I need them to be generated very quickly. Several answers to similar questions suggested simply shuffling the array to get random numbers, while others suggested using a flowering filter. The question is which one is more effective, and if it is a flower filter, how to use it?

+2
source share
2 answers

You don't need random numbers at all. You want the exact numbers from 0 to N-1 in random order.

Simple array filling and shuffling should be very fast. A proper Fisher-Yates enumeration is O (n), so an array of 100 million should take up to a second in C or even Java, a bit slower in a higher-level language like Python.

You only need to create random N-1 numbers to perform shuffling (possibly up to 1.3N if you use sampling to get perfect uniformity), so the speed will depend largely on how fast your RNG is.

You will not need to search if a number has already been created; which will be deadly slow no matter which algorithm you use, especially towards the end of the run.

N , 0 N-1, . , "--check-for-dups". .

+5

- . 0, 1, 2,... . , . , - .

64- DES, 32- Hasty Pudding ( ) Feistel cypher. , , .

+2

More articles:


All Articles