On Sat, 10 Jan 2009 07:12:13 +0300, yes <y...@no.com> wrote:
How do I use this?
I'd like a fast shuffle of a large array.
void randomShuffle(T, SomeRandomGen)(T[] array, ref SomeRandomGen r);
Shuffles elements of array using r as a shuffler.
Shuffling a whole array should be faster than taking a random element
every time and keeping track of taken elements, right?
Shuffling is usually implemented in-place. A random element is picked, swapped
with last one, and then range is decreased. Something like this:
void shuffle(T)(T[] array)
{
int len = array.length;
while (len > 1) {
int offset = random(0, len); // get a random value that belongs to [0,
len)
--len;
swap(array[offset], array[len]);
array.length = len;
}
}
The algorithm is very simple. However, user might not be satisfied with "default"
distribution and thus be able to provide his own random number generator. That's what
"SomeRandomGen" object is needed for.
From a quick glance, I didn't find meaningful explanation and requirements for
this type (i.e. what methods and properties set it should provide), but it
should be described in the docs somewhere.
Unit-test shows the following use-case:
auto a = ([ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]).dup;
Mt19937 gen;
randomShuffle(a, gen);
As a side note I'd add that you should better use Random instead of Mt19937 (the former being an
alias to the latter), because it is easier to read and understand (I bet too many people exclaim
"wtf is that??" when they first see a class named "Mt19937").
