in reply to Re: reversing a sort...
in thread reversing a sort...

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.

Replies are listed 'Best First'.
Re (tilly) 3: reversing a sort...
by tilly (Archbishop) on May 09, 2001 at 03:39 UTC
    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]
Re: Re: Re: reversing a sort...
by nardo (Friar) on May 09, 2001 at 02:49 UTC
    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]
        Actually the one with the reverse has the exact same constant factor as the regular sort.

        The additional inefficiency is O(n), not O(n log n). Plus it is O(n) with a fairly small factor...

[reply]

In Section Meditations