• yes (5/5) Jan 09 2009 How do I use this?
• Denis Koroskin (19/25) Jan 09 2009 Shuffling is usually implemented in-place. A random element is picked, s...
• yes (1/26) Jan 09 2009

yes <yes no.com> writes:

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? 

"Denis Koroskin" <2korden gmail.com> writes:

On Sat, 10 Jan 2009 07:12:13 +0300, yes <yes 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").

yes <yes no.com> writes:

Thanks !

 
 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").