Re^6: Array problem

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?

#713977-javafan.pl
#! perl -slw
use strict;
use Time::HiRes qw[ time ];

our $N ||= 1000;

my  @animals = qw[
    dog cat bird mouse rat snake horse cow
    pig lizard lamb zebra lion elephant monkey
];

my $start = time;
for( 1 .. $N ) {
    my @scratch = @animals;
    my @want;

    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];
            }
        }
        push @want, "$animal @scratch[ -3 .. -1 ]";
    }
}
printf "Took %7.5f seconds/iteration\n", ( time() - $start ) / $N;

#713977.pl
#! perl -slw
use strict;
use List::Util qw[ shuffle ];
use Time::HiRes qw[ time ];

our $N      ||= 1000;

my  @start = qw[
    dog cat bird mouse rat snake horse cow
    pig lizard lamb zebra lion elephant monkey
];

my $start = time;
for ( 1 .. $N ) {
    my  @want = map{
        join ' ', $start[ $_ ],
        ( shuffle @start[ 0 .. $_-1, $_+1 .. $#start ] )[ 0 .. 2 ]
    } 0 .. $#start;
}
printf "Took %7.5f seconds/iteration\n", ( time() - $start ) / $N;
[download]

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

Comment on Re^6: Array problem Select or Download Code

Replies are listed 'Best First'.
Re^7: Array problem by ikegami (Patriarch) on Sep 29, 2008 at 01:33 UTC
Oops, I was mistaken. I thought he was doing `my $r = rand ($r);`. I don't see any unfairness.	[reply] [d/l]
Re^8: Array problem by BrowserUk (Patriarch) on Sep 29, 2008 at 04:25 UTC
I don't see any unfairness. Okay, try running this and see if it changes your mind. #! perl -slw use strict; our $N \|\|= 1e6; my %stats; my @data = 'A' .. 'Z'; for my $n ( 1 .. $N ) { my @scratch = @data; foreach my $first ( @data ) { for my $j ( reverse $#scratch -2 .. $#scratch ) { my $r = rand( $j + 1 ); @scratch[ $j, $r ] = @scratch[ $r, $j ]; if( $scratch[ $j ] eq $first ) { my $r = rand $j; @scratch[ $j, $r ] = @scratch[ $r, $j ]; } } ++$stats{ $_ } for @scratch[ -3 .. -1 ]; } system 'cls'; printf "%8d\n", $n; printf "%s : %6d ( %+3d ) %s\n", $_, $stats{ $_ }, $stats{ $_ } - ( 3 * $n ), '#' x abs( $stats{ $_ } - ( 3 * $n ) ) for @data; } [download] Over time, the variance should tend to converge towards zero for all choices, but every time I run this, one or two of the choices show no signs of converging. Indeed, their variance just seems to grow. Not mathematical proof of unfairness--I can't work out how to apply a Chi Squared test to this kind of data--but sufficient to convince me that there is something hookey. BTW, you'll need a wide terminal to see the effect at it's best. Mine is set to 1000 wide. Setting a small font also helps as the numbers grow. 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."	[reply] [d/l]
Re^9: Array problem by ikegami (Patriarch) on Sep 29, 2008 at 04:57 UTC
I ran it on your solution and got similar results to those obtained by JavaFan's solution.. Maybe the test or the interpretation of the test is wrong. Looking at absolute numbers seems wrong.	[reply] [d/l]
Re^9: Array problem by JavaFan (Canon) on Sep 29, 2008 at 09:42 UTC
Well, if my algorithm has a bias, it should be the same values that are picked more or less often than expected, each time you run the algorithm. Furthermore, I don't think `abs($stats{$_} - 3 * $n)` is what needs to converge towards zero; `abs($stats{$_} - 3 * $n)/$n` ought to converge towards zero. And that does.	[reply] [d/l] [select]
Re^10: Array problem by BrowserUk (Patriarch) on Sep 29, 2008 at 15:22 UTC
Re^7: Array problem by ikegami (Patriarch) on Sep 29, 2008 at 00:37 UTC
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]
Re^8: Array problem by BrowserUk (Patriarch) on Sep 29, 2008 at 01:09 UTC
What makes it unfair is the my $r = rand ($j); That's what I meant by "re-pick". 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."	[reply]