3 ms·
Fisher Yates is simple, fast and correct. The only area of improvement I can think of is reducing cache misses.
by im3w1l 2y ago
Fisher Yates is simple, fast and correct. The only area of improvement I can think of is reducing cache misses.
- o11c 2y agoThat needs some conditions: * original Fisher-Yates is slow; Knuth's variation is what makes it fast * Fisher-Yates relies on "generate integer in range", which is often implemented badly (with bias, or with unnecessary slowness). See the PCG blog for the best-known solution. https://www.pcg-random.org/posts/bounded-rands.html https://www.pcg-random.org/posts/bounded-rands.html
- im3w1l 2y agoModern languages usually provide a generate integer in range primitive. Edit: Even C++ seems to have it nowadays in std::uniform_int_distribution
- jltsiren 2y agoThe C++ distributions are problematic, because the standard does not specify the algorithms. If you specify the generator and the seed, you can still get different random numbers on different platforms. Which is why applications that need reproducible results must use another library or implement their own distributions.
- Dylan16807 2y agoWhat's unnecessary slowness in this situation? Are we worried about a single division per random number? I wish this page showed some separate charts for fast and slow RNGs and some better slow options. If you actually care about proper shuffling and the minuscule bias you get from 2^64 % 52 then you should be using a CSPRNG, not a cheap method.
- whyever 2y agoYou will still get better results when avoiding the bias, even with a non-CSPRNG. Their bias is much smaller. Avoiding the division can be faster, especially if you sample many numbers from the same range. But it depends on the use case.
- Dylan16807 2y agoYou can generate so many megabytes of random per second with a CSPRNG though. I really don't see the use case where you care about bias enough to use very careful range functions but don't want to bother with a better generator.
- whyever 2y agoIn Monte Carlo simulations you usually don't care about predictability (so using a non-CSPRNG is fine), but statistical bias may compromise your results. But I agree that a CSPRNG should be the default.
- Dylan16807 2y agoIf the modulus fits in 16 bits and the raw random number is 64 bits I don't think your results are going to be compromised.
- pclmulqdq 2y agoFloyd optimal sampling is also an interesting algorithm along these lines.