Question

What is the fastest shuffling algorithm in C? The one I am using takes around 10 seconds to shuffle 50 million integers :(

Answer 1

is there a difference between algorithm in C and not C? :D

Answer 2

when you thinking about what you are actually trying to do. 10 seconds is still pretty fast.

shuffling 50 million integers around to me sounds like you're randomly accessing somewhere in the array to swap to with another random place in the array. definitely not very cache friendly.

Answer 3

Why would you need to 'shuffle' 50 million integers?? Aren't they supposed to be randomly generated anyway?? And why generate 50 million integers upfront? A feature of pseudo-random number generators is there ability to generate predictable sequences based on the same input seed, so if you really needed to know which 50 million integers your simulation was using just use the same seed when you initialise your generator.

Answer 4

One of the faster shuffles you can do is the random swap. Iterate from 0-n, generating a random index random index r, and swap the current value with the one at r. It's O(n), and mostly limited by the performance of your random number generator. For really large arrays, it can be beneficial for performance to constrain the r to be within [n; n+m], where m is chosen to minimize cache misses (so that when the current index is fetched, the one at r is in the cache as well). You may need a couple of iterations to get a thorough enough shuffle if you do this, depending on the size of m compared to the size of the array.

Answer 5

Ah, I just saw that's what you're already doing. Try the random index constraint with a small offset (16 elements or so) to see if cache misses are your problem.