On Fri, Apr 05, 2002 at 06:30:17PM +0300, Ilmari Karonen wrote:
>
> On Fri, 5 Apr 2002 [EMAIL PROTECTED] wrote:
> > On Fri, Apr 05, 2002 at 12:17:27AM +0300, Ilmari Karonen wrote:
> > > The point of taking a reference is that the Fisher-Yates algorithm is an
> > > in-place shuffle. If your array happens to be a couple of megabytes in
> > > size, you start to appreciate this feature. So, since we have this nice
> >
> > Ah, well, one could give the same argument for sort and map, but
> > noone seems to object to them not performing in situ operations.
>
> Well, map does allow in-place modification. I seem to recall you taking
> advantage of this feature before, and defending it quite vehemently
> against accusations of obfuscation... ;-)
I challenge you to find a piece of code of me that uses map{} to
modify the list it's working on.
Don't confuse modifying *ELEMENTS* with modifying an array. Any function
can modify array elements already, if the array is given as argument.
(See below ;-)
> > @array = shuffle @array; # Tada!
>
> That's not an in-place shuffle. It's a copy-and-shuffle, where the
> final copy just happens to overwrite the original. It still takes O(n)
> extra memory[1], whereas a real in-place algorithm takes O(1).
Oh, but with a few modifications, you don't need to the extra memory.
sub shuffle {
for (my $i = @_; $i;) {
my $j = rand $i --;
@_ [$i => $j] = @_ [$j => $i]
}
@_;
}
Perhaps this is the best of both worlds:
- It takes a list as argument.
- It's in-situ.
- In list context, it returns the shuffled list.
- In scalar (and hence void) context, it doesn't require linear
additional memory.
It's also, IMO, a simpler function than the one presented previously.
No references, no return in a wierd place, no check for special cases.
(Yes, I realize that it swaps element 0 with itself at the end - a fair
price for the simplicity)
Abigail
