http://www.perlmonks.org?node_id=1229411


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

Using the fact that a negative value read as an unsigned is bigger than any signed positive:

  eily => sub {
    my @list = -50..50;
    @list = sort { ~$b <=> ~$a } @list;
    Compare(\@list,[0..50,-50..-1]) or die "@list" if DO_CHECK;
  }

[download]
             Rate grepfirst sortfirst      eily
grepfirst 59577/s        --      -14%      -32%
sortfirst 69292/s       16%        --      -21%
eily      87583/s       47%       26%        --

[download]

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

    Just noting down a small caveat that using unary you may loose a bit of numeric range in Perl (including this method). On a 64 machine the valid range for this method would be from -(2^63): -9223372036854775808 to (2^63-1) 9223372036854775807 (thus signed 64 bit integer). Positive Perl integers can be bigger but the result of the unary overlaps the negative range for positive numbers in the upper range (> 2^63-1).

    To illustrate this with some numbers:

     ~ -9223372036854775808 = 9223372036854775807
 ~  9223372036854775808 = 9223372036854775807

    [download]

    I have not checked all of the other (now 13) proposed solutions, but just spotted this one. I think there are proposed solutions that do not suffer from this (such as Discipulus's method).

[reply]
[d/l]
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by Eily (Monsignor) on Feb 06, 2019 at 10:48 UTC

    As vr pointed out this only performs well on already sorted lists but falls behind pretty fast otherwise. This actually means that you can make it run faster on unsorted list by sorting twice (still doesn't beat most of the leading propositions though): 

    use warnings;
use strict;
use Benchmark 'cmpthese';
use constant DO_CHECK => 0;
use if DO_CHECK, 'Data::Compare', qw/Compare/;

my @input = (-57..50,52,0);
my @output = (0,0..50,52,-57..-1);
use List::Util 'shuffle';
srand 123;
@input = shuffle @input;

cmpthese(DO_CHECK ? 1 : -2, {
  Eily => sub {
    my @list = @input;
    @list = sort { ~$b <=> ~$a } @list;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
  Eily2 => sub {
    my @list = @input;
    @list = sort { ~$b <=> ~$a } sort { $a <=> $b } @list;
    Compare(\@list,\@output) or die "@list" if DO_CHECK;
  },
});

__END__
         Rate  Eily Eily2
Eily  20139/s    --  -58%
Eily2 47615/s  136%    --

    [download]
    Going twice as fast by doing the job twice, talk about counter intuitive :D.

[reply]
[d/l]

In Section Seekers of Perl Wisdom