www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - randomCover not so random?

reply dsimcha <dsimcha yahoo.com> writes:
Maybe I'm doing something subtly wrong here, but I've checked all the obvious
stuff.

import std.stdio, std.random, std.array;

import dstats.base : Perm;

void main() {
    uint[int[]] counts;
    immutable int[] foo = [1,2,3];

    // Make sure every permutation is represented in counts.
    foreach(perm; Perm!int(foo.dup)) {
        counts[perm.dup] = 0;
    }

    foreach(i; 0..10_000) {
        int[] result;
        foreach(elem; randomCover(foo, Random(unpredictableSeed))) {
            result ~= elem;
        }
        counts[result]++;
    }
    foreach(k, v; counts) {
        writeln(k, "\t", v);
    }
}

Output:

2 3 1   0
3 2 1   0
1 3 2   0
3 1 2   0
1 2 3   4929
2 1 3   5071

Note that when I use randomShuffle instead of randomCover, I get a fairly
uniform distribution on the permutation space.
Apr 20 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 Maybe I'm doing something subtly wrong here, but I've checked all the obvious
 stuff.
 
 import std.stdio, std.random, std.array;
 
 import dstats.base : Perm;
 
 void main() {
     uint[int[]] counts;
     immutable int[] foo = [1,2,3];
 
     // Make sure every permutation is represented in counts.
     foreach(perm; Perm!int(foo.dup)) {
         counts[perm.dup] = 0;
     }
 
     foreach(i; 0..10_000) {
         int[] result;
         foreach(elem; randomCover(foo, Random(unpredictableSeed))) {

Here you reseed the random number generator every pass through the outer loop. Although unpredictableSeed is designed to be unpredictable, it is _not_ random. You'd need to have each cover use the same random generator. Here's where a shortcoming in the design of randomCover becomes evident: randomCover stores a copy of its generator, which makes it difficult to support what you need. I will look into a fix. Andrei
Apr 20 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 dsimcha wrote:
 Maybe I'm doing something subtly wrong here, but I've checked all the obvious
 stuff.

 import std.stdio, std.random, std.array;

 import dstats.base : Perm;

 void main() {
     uint[int[]] counts;
     immutable int[] foo = [1,2,3];

     // Make sure every permutation is represented in counts.
     foreach(perm; Perm!int(foo.dup)) {
         counts[perm.dup] = 0;
     }

     foreach(i; 0..10_000) {
         int[] result;
         foreach(elem; randomCover(foo, Random(unpredictableSeed))) {

loop. Although unpredictableSeed is designed to be unpredictable, it is _not_ random. You'd need to have each cover use the same random generator. Here's where a shortcoming in the design of randomCover becomes evident: randomCover stores a copy of its generator, which makes it difficult to support what you need. I will look into a fix. Andrei

Actually, I meant to mention in the original post that I thought of this already and it's not the problem. When I re-seed the generator every time but use randomShuffle, I get something pretty uniform looking. Furthermore, even after I allow a few more clock ticks to go by and re-run the program, I still get the same thing when using randomCover. I also tried things like keeping a Mersenne Twister outside the loop and using successive iterations of that to seed the generator that I pass to randomCover. I actually did find the real problem, though. It's really simple and I've filed it in Bugzilla. See http://d.puremagic.com/issues/show_bug.cgi?id=2865 . Also, since I remember the discussion a while back on how to make randomCover as efficient as possible, why are we using bool[] instead of BitArray for it?
Apr 20 2009