Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

So I was just working on this seemingly simple task, and I think there are probably a lot of ways to optimize it, but I don't have the time to look at them all, since my lists aren't too long (and the sort won't be called that often) that optimization really matters. So I thought it might be a neat little challenge: who can do the following faster? :-)

The input is a list of any integers in any order, I hope the sort order is clear from the examples I've provided: (-50..50) should become (0..50,-50..-1).

#!/usr/bin/env perl use warnings; use strict; use Benchmark 'cmpthese'; # to run tests first: $ DO_CHECK=1 perl sort.pl && perl sort.pl use constant DO_CHECK => !!$ENV{DO_CHECK}; use if DO_CHECK, 'Data::Compare', qw/Compare/; my @input = (-52,-50..50,52,0); my @output = (0,0..50,52,-52,-50..-1); use List::Util 'shuffle'; srand 123; @input = shuffle @input; cmpthese(DO_CHECK ? 1 : -2, { sortfirst => sub { my @list = @input; @list = sort {$a<=>$b} @list; @list = ( (grep {$_>=0} @list), (grep {$_<0} @list) ); Compare(\@list,\@output) or die "@list" if DO_CHECK; }, grepfirst => sub { my @list = @input; my @pos = grep {$_>=0} @list; my @neg = grep {$_<0} @list; @list = ( (sort {$a<=>$b} @pos), (sort {$a<=>$b} @neg) ); Compare(\@list,\@output) or die "@list" if DO_CHECK; }, # ##### UPDATE - From the replies: ##### Corion => sub { # based on Corion's idea in the CB my @list = @input; @list = sort { $a>=0&&$b<0 ? -1 : ( $a<0&&$b>=0 ? 1 : $a<=>$b ) } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, choroba0 => sub { # from CB my @list = @input; @list = sort { (($b +.5 <=> 0) <=> ($a + .5 <=> 0)) || ($a <=> $b) } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, choroba => sub { # https://www.perlmonks.org/?node_id=1229407 my @list = @input; @list = sort { ((-1, 0, 1)[$a <=> 0] <=> (-1, 0, 1)[$b <=> 0]) || ($a <=> $b) } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, choroba2 => sub { # https://www.perlmonks.org/?node_id=1229407 my @list = @input; @list = sort { ((($a <=> 0) & 3) <=> (($b <=> 0) & 3)) || ($a <=> $b) } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, johngg => sub { # https://www.perlmonks.org/?node_id=1229410 my @list = @input; @list = map { unpack q{xl>}, $_ } sort map { my $neg = $_ < 0 ? 1 : 0; pack q{Cl>}, $neg, $_; } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, Tux => sub { # https://www.perlmonks.org/?node_id=1229409 # (johngg made a similar suggestion in the CB first) my @list = @input; @list = map {unpack "l>", $_} sort map {pack "l>", $_} @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, pryrt => sub { # https://www.perlmonks.org/?node_id=1229408 my @list = @input; sub sgn { $_[0]<0?-1:1 } @list = (sort {(sgn($b) <=> sgn($a)) || ($a <=> $b)} @list); Compare(\@list,\@output) or die "@list" if DO_CHECK; }, Eily => sub { # https://www.perlmonks.org/?node_id=1229411 my @list = @input; @list = sort { ~$b <=> ~$a } @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, vr => sub { # https://www.perlmonks.org/?node_id=1229415 my @list = @input; @list = unpack 'i*', pack 'I*', sort { $a <=> $b } unpack 'I*', pack 'i*', @list; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, Discipulus => sub { # https://www.perlmonks.org/?node_id=1229419 my @list = @input; @list = sort {$a<=>$b} @list; push @list, shift @list until $list[0] >= 0; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, haukex3 => sub { # based on sortfirst above my @list = @input; @list = sort {$a<=>$b} @list; my $i; for (0..$#list) { if($list[$_]>=0){$i=$_;last} } # with this module is ~5% faster: #use List::MoreUtils::XS 'firstidx'; #my $i = firstidx { $_>=0 } @list; @list = (@list[$i..$#list], @list[0..$i-1]); Compare(\@list,\@output) or die "@list" if DO_CHECK; }, }); __END__ # Results on my machine (v5.28.1 built for x86_64-linux): Rate pryrt choroba0 choroba johngg choroba2 Corion Tux + Eily grepfirst sortfirst haukex3 vr Discipulus pryrt 10176/s -- -36% -42% -58% -59% -66% -67% + -76% -87% -89% -91% -91% -92% choroba0 15907/s 56% -- -10% -35% -36% -46% -49% + -63% -80% -83% -85% -86% -88% choroba 17600/s 73% 11% -- -28% -29% -40% -44% + -59% -77% -81% -84% -84% -87% johngg 24316/s 139% 53% 38% -- -2% -18% -22% + -44% -69% -74% -77% -78% -82% choroba2 24769/s 143% 56% 41% 2% -- -16% -21% + -43% -68% -73% -77% -78% -81% Corion 29510/s 190% 86% 68% 21% 19% -- -5% + -32% -62% -68% -72% -74% -78% Tux 31189/s 207% 96% 77% 28% 26% 6% -- + -28% -60% -66% -71% -72% -77% Eily 43216/s 325% 172% 146% 78% 74% 46% 39% + -- -44% -53% -60% -61% -67% grepfirst 77841/s 665% 389% 342% 220% 214% 164% 150% + 80% -- -16% -27% -30% -41% sortfirst 92880/s 813% 484% 428% 282% 275% 215% 198% + 115% 19% -- -13% -17% -30% haukex3 107128/s 953% 573% 509% 341% 333% 263% 243% + 148% 38% 15% -- -4% -19% vr 111499/s 996% 601% 534% 359% 350% 278% 257% + 158% 43% 20% 4% -- -16% Discipulus 132736/s 1204% 734% 654% 446% 436% 350% 326% + 207% 71% 43% 24% 19% --

Update: Made ranges a bit longer so the differences become more clear. Other very minor tweaks to text.

Update 2: Added code from replies so far. At the moment, on my machine Eily's code is winning (sort { ~$b <=> ~$a } @list), and thanks for everyone for the great ideas - TIMTOWTDI! :-) Post more if you've got 'em, I'll add them later.

Update 3: Added code from Corion and vr, made input data more representative, and it looks like vr has the new best time with unpack 'i*', pack 'I*', sort { $a <=> $b } unpack 'I*', pack 'i*', @list (Eily's is still shortest) :-)

Update 4: Discipulus takes the lead! (I also added my own attempt at optimizing sortfirst which I happened to be working on in the meantime)

Update 5: An interesting race between various solutions! See my update post here.


In reply to Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by haukex

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



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (None)
    As of 2021-10-21 03:05 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      My first memorable Perl project was:







      Results (82 votes). Check out past polls.

      Notices?