View mode: basic / threaded / horizontal-split · Log in · Help
May 03, 2012
Fixed-size arrays and randomShuffle()
May be that this works as intended, but it fooled me:
---
import std.random;
import std.stdio;
void main() {
        int[5] a = 0;
        a[0] = 1;
        int[] b = [1, 0, 0, 0, 0];
        randomShuffle(a);
        writeln(a);
        randomShuffle(b);
        writeln(b);
}
---

In DMD 2.0.59 the fixed-size array "a" won't be shuffled (the dynamic 
array "b" will), and you won't get any warning about it.

I'm not sure whether this counts as something that should be reported as 
a bug/improvement, nor if only randomShuffle() displays this behaviour, 
perhaps you could enlighten me.
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 05/03/2012 06:30 AM, Vidar Wahlberg wrote:
> May be that this works as intended, but it fooled me:
> ---
> import std.random;
> import std.stdio;
> void main() {
> int[5] a = 0;
> a[0] = 1;
> int[] b = [1, 0, 0, 0, 0];
> randomShuffle(a);

Fixed-length arrays are value types. 'a' is copied to randomShuffle() so 
its copy is shuffled. Passing a slice of the whole array works:

        randomShuffle(a[]);

> writeln(a);
> randomShuffle(b);
> writeln(b);
> }
> ---
>
> In DMD 2.0.59 the fixed-size array "a" won't be shuffled (the dynamic
> array "b" will), and you won't get any warning about it.
>
> I'm not sure whether this counts as something that should be reported as
> a bug/improvement, nor if only randomShuffle() displays this behaviour,
> perhaps you could enlighten me.

Ali
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 2012-05-03 15:34, Ali Çehreli wrote:
> Fixed-length arrays are value types. 'a' is copied to randomShuffle() so
> its copy is shuffled. Passing a slice of the whole array works:
>
> randomShuffle(a[]);

True, it is however still not exceptionally newbie (or perhaps even 
user?) friendly (my question was more of "does it have to be this way?" 
rather than "how do you do this?", even though I appreciate the answer 
on how to do it).
Is it not possible for the compilator to let you know that what you're 
doing doesn't make any sense?

A quick follow-up:
I've tried some various random number engines, but neither come even 
close to the performance of whatever is used for Java's 
"Collection.shuffle()" method. Perhaps someone can shed some light on this?
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
Why would you not want it to shuffle a fixed array? That's a very 
frustrating silent failure.
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 05/03/2012 06:55 AM, Vidar Wahlberg wrote:
> On 2012-05-03 15:34, Ali Çehreli wrote:
>> Fixed-length arrays are value types. 'a' is copied to randomShuffle() so
>> its copy is shuffled. Passing a slice of the whole array works:
>>
>> randomShuffle(a[]);
>
> True, it is however still not exceptionally newbie (or perhaps even
> user?) friendly (my question was more of "does it have to be this way?"
> rather than "how do you do this?", even though I appreciate the answer
> on how to do it).
> Is it not possible for the compilator to let you know that what you're
> doing doesn't make any sense?

Random shuffle can work on a fixed-length array and there is a way for 
the implementation to know:

import std.traits;
// ...
  __traits(isStaticArray, a)

That can be used in a template constraint.

> A quick follow-up:
> I've tried some various random number engines, but neither come even
> close to the performance of whatever is used for Java's
> "Collection.shuffle()" method. Perhaps someone can shed some light on 
this?

I have no idea with that one.

Ali
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 03.05.2012 18:02, Ali Çehreli wrote:

>
>  > A quick follow-up:
>  > I've tried some various random number engines, but neither come even
>  > close to the performance of whatever is used for Java's
>  > "Collection.shuffle()" method. Perhaps someone can shed some light on
> this?
>
> I have no idea with that one.
>

It's all about RNG used behind the scenes. Default one is Mersane 
Twister which (AFAIK) is not particularly fast. But has a period of 
2^19937 elements.
You should probably use XorShift or MinstdRand generator and a version 
of shuffle with 2nd parameter.

-- 
Dmitry Olshansky
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 2012-05-03 16:26, Dmitry Olshansky wrote:
> It's all about RNG used behind the scenes. Default one is Mersane
> Twister which (AFAIK) is not particularly fast. But has a period of
> 2^19937 elements.
> You should probably use XorShift or MinstdRand generator and a version
> of shuffle with 2nd parameter.

I tried those two as well. Still significantly slower than what I can 
achieve in Java.
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On Thursday, 3 May 2012 at 14:41:20 UTC, Vidar Wahlberg wrote:
> I tried those two as well. Still significantly slower than what 
> I can achieve in Java.

You might want to post your code... I wrote this code in D:
-=-=-=-

import std.random, std.stdio, std.datetime;

void main() {
	int[] arr = new int[5_000_000];
    foreach(i, ref e; arr)
        e = i;

    StopWatch sw = AutoStart.yes;
    arr.randomShuffle();
    sw.stop();

    writeln("Took ", sw.peek().to!("msecs", double)(), "ms");
}

-=-=-=-

And it performed _identically_ to this in Java:

-=-=-=-

import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String[] args) {
		ArrayList<Integer> ints = new ArrayList<>(5000);
		for(int i = 0; i < 5_000_000; ++i)
			ints.add(i);

		long startTime = System.currentTimeMillis();
		Collections.shuffle(ints);
		long endTime = System.currentTimeMillis();

		System.out.println("Took " + (endTime - startTime) + "ms");
	}
}

-=-=-=-
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On 2012-05-03 17:31, Chris Cain wrote:
> You might want to post your code...

Sure!
D:
---
import std.random;
import std.stdio;
void main() {
        auto iterations = 10000000;
        int[] a;
        for (int i = 0; i < 42; ++i)
                a ~= i;
        for (int i = 0; i < iterations; ++i)
                randomShuffle(a);
}

naushika:~/projects> dmd random.d && time ./random
./random  38,35s user 0,05s system 99% cpu 38,420 total
---


Java (7):
---
import java.util.ArrayList;
import java.util.Collections;
public class Rnd {
        public static void main(String... args) {
                int iterations = 10000000;
                ArrayList<Integer> a = new ArrayList<Integer>();
                for (int i = 0; i < 42; ++i)
                        a.add(i);
                for (int i = 0; i < iterations; ++i)
                        Collections.shuffle(a);
        }
}

naushika:~/projects> javac Rnd.java && time java Rnd
java Rnd  9,92s user 0,03s system 100% cpu 9,922 total
---
May 03, 2012
Re: Fixed-size arrays and randomShuffle()
On a related note, how did you get the other random generators 
working? I tried to compile this and it gives me an error:
-=-=-=-
import std.random, std.stdio, std.datetime;

void main() {
	int[] arr = new int[5_000_000];
    foreach(i, ref e; arr)
        e = i;
    auto rng = MinstdRand0(1);
    rng.seed(unpredictableSeed);
    StopWatch sw = AutoStart.yes;
    randomShuffle(arr, rng);
    sw.stop();

    writeln("Took ", sw.peek().to!("msecs", double)(), "ms");
}
-=-=-=-

The error:
-=-=-=-
C:\D\dmd2\windows\bin\..\..\src\phobos\std\random.d(1263): Error: 
cannot implicitly convert expression (rndGen()) of type 
MersenneTwisterEngine!(uint,32,624,397,31,-1727483681u,11,7,-1658038656u,15,-272236544u,18) 
to LinearCongruentialEngine!(uint,16807,0,2147483647)
-=-=-=-

Is this a bug in 2.059? Or am I doing something wrong?
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home