random shuffle

[richk]

Does anybody have a fast routine to do a random shuffle of an array of integers? I have looked at the random_shuffle template, but I want to shuffle the array itself, rather than vectors. I have been using the rand() function then using a modulus to pick a random entry and then swapping memory. It works, but I can't help thinking that there must be a faster way.

thanks

[peterchen]

From inquiry.com:
>>>>
Using random_shuffle() with Built-in Arrays
You shouldn't be concerned about the overhead of using containers instead of built-in arrays. All STL algorithms apply to sequences, not just containers. Thus, you can use random_shuffle() with built-in arrays as well. Make sure that the second argument of random_shuffle() points one element past the array bounds:

char carr[4] = {'a', 'b', 'c', 'd'};
/*carr+4 points one position past array bounds*/
random_shuffle(carr, carr+4);
for (int i = 0; i < 4; i++)
cout<<carr[i]; /* display shuffled elements */




However, it depends on the actual STL implementation how fast it is.

A simple algorithm to shuffle N integers a[0]..a[N-1]:
pick an random number r from [0..N-1]
swap a[r] with a[N-1]
N=N-1 and repeat until N reaches 1




(I haven't tested it, I just proved it correct ;-)

[richk]

The simple routine at the end of your post was the same way I originally coded mine, but I hoped that something else would be faster. I needed to shuffle an array many times to test a simulation. When I tested the template class, it was exactly the same speed as my original routine. (49 seconds to shuffle a deck of cards 5 million times on 500 mHz P3)

thanks

[peterchen]

Hi,

No, As much as I meditated about it, there is no faster algorithm - unless you want to sacrifice some randomness.

5 million shuffles in fifty seconds sounds relatively cool - but I don't know what you need.

I assume you already switched to a release build, and perhaps played with the optimization options a bit, if so you could just eval some low level optimizations - but only if it#s woth the trouble. I could imagine using an inlined rand() replacement (one of the x=(a+x)%b generators should be perfect, if you re-shuffle the previous table you need no extra shuffle table) Check Knuth for good values of a and b.

If you don't know if your snipped is "optimal" (mostly it is if you don't do something blatantly wrong with nowadays compilers), just post it.

Good luck.
Peter