Re: 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%    --
[download]

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

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

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; },` [download] 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% --` [download]	[reply] [d/l] [select]
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by haukex (Archbishop) 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!	[reply] [d/l]
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; }, # ...` [download] 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++).	[reply] [d/l]
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by ikegami (Patriarch) on Feb 06, 2019 at 03:31 UTC
Isn't `@list = unpack 'j', pack 'J', sort { $a <=> $b } unpack 'J', pack 'j', @list;` [download] just a complicated/expensive way of doing `@list = unpack 'j>', sort pack 'j>', @list;` [download]	[reply] [d/l] [select]
Re^3: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by vr (Curate) on Feb 06, 2019 at 09:33 UTC
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.	[reply]
Re^4: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by ikegami (Patriarch) on Feb 06, 2019 at 20:10 UTC
Oh right. It would be `@list = map { unpack 'j>', $_ } sort map { pack 'j>', $_ } @list;` [download] I knew I was tired and missing something.	[reply] [d/l]