Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
As an aside. I've long wished that perl had a numeric sort option built in (would one extra built-in called sortn be any great burden?), so that many cases where sorting numerically currently requires the overhead of a trivial callback or user block ...
Not true. Perl does optimize some trivial sort code blocks, so if it sees something that looks like
@sorted = sort { $a <=> $b } @list;
it will turn it into a native numerical sort. Benchmarks will show that there is no significant speed difference between native sorting as string, and sorting numerically with this block: there simply is no callback overhead.

I don't know the exact list, but it looks like at least normal and reversed numerical and string comparisons are in the list of blocks that get optimized away.

Here are some benchmarks. See how close the results are, numerical sorting is typically even faster than string sortings due to a faster comparison operator. reversed_string and native are even as good as equally fast!

For comparison I've also added a "messed up" callback block which doesn't use one of the idiomatic callback blocks, and doesn't get optimized away. See how efficiency falls back to one fifth of the optimized numerical sort, from 375 iterations / second, to a mere 75, and a third of the built-in native sort. The latter is the result you were expecting for the general case.

#!/usr/bin/perl -w use strict; use Benchmark; my(@sorted, @unsorted); push @unsorted, rand 10000 for 1 .. 1000; timethese(-3, { native => sub { @sorted = sort @unsorted }, string => sub { @sorted = sort { $a cmp $b } @unsorted }, reversed_string => sub { @sorted = sort { $b cmp $a } @unsorted }, numerical => sub { @sorted = sort { $a <=> $b } @unsorted }, reversed_numerical => sub { @sorted = sort { $b <=> $a } @unsorted + }, messed_up=> sub { @sorted = sort { my $cmp = $a <=> $b; $cmp } @un +sorted }, });
Results with a Perl 5.6.1:
Benchmark: running messed_up, native, numerical, reversed_numerical, r +eversed_string, string, each for at least 3 CPU seconds... messed_up: 3 wallclock secs ( 3.29 usr + 0.00 sys = 3.29 CPU) @ 75 +.99/s (n=250) native: 3 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 CPU) @ 24 +0.89/s (n=754) numerical: 3 wallclock secs ( 3.18 usr + 0.00 sys = 3.18 CPU) @ 37 +5.16/s (n=1193) reversed_numerical: 2 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 C +PU) @ 379.87/s (n=1189) reversed_string: 4 wallclock secs ( 3.62 usr + 0.00 sys = 3.62 CPU) + @ 239.78/s (n=868) string: 3 wallclock secs ( 3.24 usr + 0.00 sys = 3.24 CPU) @ 22 +6.54/s (n=734)

In reply to Sorting blocks and efficiency (in Re to Re: Algorithm::Treap) by bart
in thread Algorithm::Treap by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others pondering the Monastery: (9)
    As of 2014-12-29 15:16 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      Is guessing a good strategy for surviving in the IT business?





      Results (192 votes), past polls