Huh? I don't think your assertion makes sense. reverse sort { arbitrary code } @list will always be less efficient than sort { arbitrary code with $a and $b swapped } @list.
Whether the sort takes more time than the reverse doesn't matter, because you have to do the same sort in either case. | [reply]
[d/l]
[select] |
He was pointing out that sort {$a cmp $b} @list is slower than sort @list because you save the overhead of calling the sort function. The difference should be big enough at some point that it is faster to reverse sort @list instead of sort {$b cmp $a} @list.
Testing this is going to be tricky, of course, because sorting effiency depends on the order you see elements in.
Also this is a very, very special case. With more complex sorts there is choice about how to write it either way, and reverse has to be a waste of time.
UPDATE
Bloody language maintainers. Going and rendering my
hard-won optimization knowledge obsolete by making
everything fast. Bah.
| [reply]
[d/l]
[select] |
Well, that's just no longer the case. In perl5.6, the four common sort routines:
{ $a cmp $b } { $a <=> $b } { $b cmp $a } { $b <=> $a }
are all optimized. This was change 2595 in perl5.005_55 on Jan 13, 1999. (See the Changes file (big!) or the patch.)
| [reply]
[d/l] |
reverse sort { arbitrary code } @list will always be less efficient than sort { arbitrary code with $a and $b swapped } @list
Not always, the number of comparisons and swaps performed by sort will depend on the order of the list. On my machine, reverse sort {$a <=> $b} (1..100000); is faster than sort {$b <=> $a} (1..100000);
For almost all cases, you are correct, but it is not _always_ the case.
| [reply]
[d/l]
[select] |
I quite intentionally did not say one would be always be "faster". I said reverse sort is less efficient. sort and reverse sort are both O(n log n), but the one with reverse has a larger constant factor and is less efficient.
By the way, if you want to know the fastest way to sort the list (1..100_000) in descending order, it's:
reverse (1 .. 100_000);
;)
Update: Doh. As Tilly explains below, I totally messed up the Big O analysis. Anyway, there is an added inefficiency with reverse sort, that's my point. :)
| [reply]
[d/l] |