note
blazar
<blockquote><i>[blazar]++. Just checking if anyone is still paying attention :)</i></blockquote>
<p>Still paying attention and also [href://news:h6he93dt84l5n6bbblqt1n08ci2nt6sfhv@4ax.com|advertising] in [href://news:comp.lang.perl.misc|clpmisc] ([http://groups.google.com/groups?threadm=h6he93dt84l5n6bbblqt1n08ci2nt6sfhv@4ax.com|link] @ [http://groups.google.com/|GG]). So [BrowserUk]++ for the additional insight and the many details provided in this reply of yours.</p>
<blockquote><i>Since <c>bukNew()</c> doesn't need to copy the input list--because it shuffles, and therefore mutates, a list of indices generated internally, rather than mutating a copy of the input--it seemes silly to pass arrays in by value forcing their duplication. Most uses of <c>shuffle()</c> are applied to pre-existing arrays. That's why we make a copy of them, or create a list of aliases to them in most versions--simply to avoid the shuffle from modifying the external arrays.</i></blockquote>
<p>Well, but then that is somewhat obvious, and even the naive implementation would would be better apt at shuffling an <em>array</em> in place, and would thus better be rewritten like this:</p>
<c>
sub naive (@) {
for (reverse 1..$#_) {
my $r=int rand($_+1);
@_[$_,$r]=@_[$r,$_];
}
}
</c>
<p>(Not that this would make it really faster - I checked and it's still <em>considerably</em> slower than the alternatives presented here.)</p>
<p>But then I think that in any case you would be comparing apples and bananas: for it was somewhat clear that the interface was in terms of "accept a list, return a (shuffled) list"... unless the interface itself was also part of the choice to take. OTOH your tests themselves show that [blokhead]'s [id://626127|solution] performs best on large datasets, which is exactly were speed is <em>more likely</em> to matter (well, not strictly, since one may have 10^6 shuffles of 10 elements long lists to do...) - and it has a more intuitive interface, so I would go for it. More precisely I have "decided" that my favourite version is the following modification of <c>blokhead()</c> that can be considered a "hybrid" with another [id://626117|version] of yours:</p>
<c>
sub bzr (@) {
my @a = 0..$#_;
my $i = @_;
my $n;
map +($_[$a[$n=rand($i--)]], $a[$n]=$a[$i])[0], @_;
}
</c>
<p>I must say that I've included it in the benchmarks too and while it doesn't perform well compared to <c>blokhead()</c>, <c>buk()</c> and <c>bukNew()</c> in the short list tests, it is comparable with the best on the 1000 strings one, and in two of them it even performed best of all, although I'd rather consider this to be a fluctuation. Why this is so, anyway, is beyond my comprehension.</p>
<p>In the meanwhile, I received a [href://news:slrnf9erh0.79h.hjp-usenet2@zeno.hjp.at|followup] from <em>Peter J. Holzer</em> in clpmisc, which addresses my own post (a copy of the [id://625977|root node] here) and I'm also reporting herafter in its entirey for completeness.</p>
<hr>
<h4>Peter J. Holzer's reply</h4>
<readmore>
<p>The main performance improvement comes from avoiding hash slices. Just
replacing <c>@l[$_,$r]=@l[$r,$_]</c>; in your code with a conventional swap via
a temporary variable:</p>
<c>
my $x = $l[$r];
$l[$r] = $l[$_];
$l[$_] = $x;
</c>
<p>gives me a 10 % performance boost.</p>
<p>The rest of the improvement comes from not swapping in-place at all, but
building a new array from scratch:</p>
<c>
sub naive2 (@) {
my @l=@_;
my @l2;
for (reverse 0..$#l) {
my $r=int rand($_+1);
push @l2, $l[$r];
$l[$r] = $l[$_];
}
@l2;
}
</c>
<p>is just as fast as the map (and it does the same thing, really).</p>
<p>Fascinating. I would have expected both changes to make the performance
worse, not better. Just shows again that intuition is an unreliable
guide on perl performance.</p>
</readmore>
625977
626269