Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1

by vr (Curate)
on Feb 05, 2019 at 16:00 UTC ( #1229415=note: print w/replies, xml ) Need Help??


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

use warnings; use strict; use Benchmark 'cmpthese'; use constant DO_CHECK => 0; use if DO_CHECK, 'Data::Compare', qw/Compare/; my @input = (-50..50); my @output = (0..50,-50..-1); use List::Util 'shuffle'; srand 123; @input = shuffle @input; # NB. NB. NB. NB. cmpthese(-2, { packz => sub { 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; }, 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; }, }); __END__ Rate Eily packz Eily 6495/s -- -66% packz 18967/s 192% --

Slow machine here. Shuffled input is important, otherwise Eily's code seems to be faster.

Replies are listed 'Best First'.
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by Eily (Monsignor) on Feb 05, 2019 at 17:12 UTC

    Shuffled input is important
    Yes, good catch! The GRT makes each comparison faster, but it seems like the number of comparisons is far lower for already sorted or nearly sorted input. It looks like the pack method is better no matter what because with this (and a list from -50 to 250):
    vr_map => sub { # https://www.perlmonks.org/?node_id=1229415 my @list = @input; @list = unpack 'i*', pack 'I*', sort { $a <=> $b } map { ~$_ } @list; # Doesn't even give the cor +rect answer, there's an offset of 1 Compare(\@list,\@output) or die "@list" if DO_CHECK; },
    your implementation is still noticeably faster (my version falls behind pretty fast on a non-sorted list):
    Rate Eily vr_map grepfirst sortfirst vr Eily 5208/s -- -53% -64% -67% -71% vr_map 11021/s 112% -- -25% -31% -38% grepfirst 14623/s 181% 33% -- -8% -17% sortfirst 15977/s 207% 45% 9% -- -10% vr 17701/s 240% 61% 21% 11% --

Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by haukex (Bishop) on Feb 05, 2019 at 16:20 UTC
    Shuffled input is important, otherwise Eily's code seems to be faster.

    Excellent point, having more representative sample input is important, as tybalt89 showed :-)

    I've updated the root node, yours is the best so far, congratulations!

Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by vr (Curate) on Feb 05, 2019 at 18:25 UTC

    If using CPAN is allowed, see Sort::Packed, this is faster:

    # ... use Sort::Packed 'sort_packed'; # ... sort_packed => sub { sort_packed I => my $s = pack 'i*', @input; my @list = unpack 'i*', $s; Compare(\@list,\@output) or die "@list" if DO_CHECK; }, # ...

    Edit: As I see now, I omitted copying @input list to unnecessary intermediate @list, as all contestants, it seems, are bound to do. To be fair, either everybody drop that line, or it's inserted into code above. Still, Sort::Packed is faster and scales better. Sorry, didn't measure other monks' answers from last night on. Surprise is counter-intuitive good speed of Discipulus' simple just-push-in-loop solution. + All tricks with sign bit interpretation sacrifice integer range (Veltro++).

Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by ikegami (Pope) on Feb 06, 2019 at 03:31 UTC
    Isn't
    @list = unpack 'j*', pack 'J*', sort { $a <=> $b } unpack 'J*', pack 'j*', @list;
    just a complicated/expensive way of doing
    @list = unpack 'j>*', sort pack 'j>*', @list;

      No, ikegami, what you wrote won't work, but perhaps, instead, you meant Tux' version. It's slower -- (un)packing per element rather than "en masse" into (from) single scalar.

        Oh right. It would be

        @list = map { unpack 'j>', $_ } sort map { pack 'j>', $_ } @list;

        I knew I was tired and missing something.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1229415]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2021-10-21 02:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (82 votes). Check out past polls.

    Notices?