in reply to Re^3: Array problem
in thread Array problem

where a linear will do.

Could you show us that please?

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

Replies are listed 'Best First'.
Re^5: Array problem
by JavaFan (Canon) on Sep 28, 2008 at 20:09 UTC
    Just don't shuffle the entire array; stop if you have shuffled three elements (taking care you don't shuffle in the leading animal). 
    my @animals = qw [dog cat bird mouse rat snake horse cow
                  pig lizard lamb zebra lion elephant monkey];

my @scratch = @animals;

foreach my $animal (@animals) {
    for (my $j = @scratch - 1; $j >= @scratch - 3; $j --) {
        my $r = rand ($j + 1);
        @scratch[$j, $r] = @scratch[$r, $j];
        if ($scratch[$j] eq $animal) {
            my $r = rand ($j);
            @scratch[$j, $r] = @scratch[$r, $j];
        }
    }
    say "$animal @scratch[-3..-1]";
}

    [download]
    As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.
[reply]
[d/l]
[select]
      As one can see easily, the running time inside the main loop is independent of the size of the array, hence, O(1), making the entire program run in linear time.

      Yep. Linear, but twice as slow as my code above for the OPs stated requirements: 

      c:\test>713977-javafan -N=1e6
Took 0.00029 seconds/iteration

c:\test>713977 -N=1e6
Took 0.00015 seconds/iteration

      [download]

      How much bigger than the requirements does the problem need to get before the additional complexity achieves parity?

      And how much bigger still, before the additional complexity of your solution starts to save enough time that the user will actually notice?

      Finally, what affect does that re-pick have upon the fairness of the shuffle?

      Read more... (2 kB)
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
[select]
        Oops, I was mistaken. I thought he was doing my $r = rand ($r);. I don't see any unfairness.
[reply]
[d/l]

        Finally, what affect does that re-pick have upon the fairness of the shuffle?

        Shuffling a previously fairly shuffled array should be as fair as shuffling the original. Right?

        What makes it unfair is the my $r = rand ($j);. It slightly favours anything preceding $animal in the array to shuffle.

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom