in reply to Randomising the order of an array

I like to do this to randomize an array:

my @shuffled =
    map { $_->[1] }
     sort { $a->[0] <=> $b->[0] }
      map { [rand(),$_] }
       @unshuffled;

[download]

Update: This wouldn't work (see OP's update)

    -Bryan

Replies are listed 'Best First'.
Re^2: Randomising the order of an array
by ikegami (Patriarch) on Jul 19, 2005 at 18:49 UTC

    Your solution is not guaranteed to be well shuffled since you relying on sort to shuffle ties.

    By using sort, you've converted a O(N) problem into an O(N log N) problem. That can make a substantial difference in execution time. In other words, your solution is less scalable.

    Something which isn't scalable could still be fast for smaller input set, but it's not even the case here:

    >perl script.pl 50

             Rate mrborisguy    ikegami
mrborisguy 2074/s         --       -51%
ikegami    4225/s       104%         --    # Without XS.

              Rate mrborisguy    ikegami
mrborisguy  2167/s         --       -91%
ikegami    23688/s       993%         --   # With XS.

    [download]

    And for an array of 1700, as relevant here:

    >perl script.pl 1700

             Rate mrborisguy    ikegami
mrborisguy 31.0/s         --       -74%
ikegami     120/s       286%         --    # Without XS.

             Rate mrborisguy    ikegami
mrborisguy 31.7/s         --       -96%
ikegami     722/s      2179%         --    # With XS.

    [download]

    The benchmark script:

    Read more... (765 Bytes)

    Update: Added benchmarks to back my statements.

[reply]
[d/l]
[select]
      Your solution is not guaranteed to be well shuffled since you relying on sort to shuffle ties.
      But you do know the period of repetition for rand(), right? ;-)
[reply]
[d/l]
        Numbers can repeat more often than rand's period, but you're right, it won't happen often.
[reply]

In Section Seekers of Perl Wisdom