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