Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

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

by Eily (Monsignor)
on Feb 05, 2019 at 14:34 UTC ( #1229411=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

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; }
Rate grepfirst sortfirst eily grepfirst 59577/s -- -14% -32% sortfirst 69292/s 16% -- -21% eily 87583/s 47% 26% --

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

    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).

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% --
    Going twice as fast by doing the job twice, talk about counter intuitive :D.

Log In?
Username:
Password:

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

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







    Results (77 votes). Check out past polls.

    Notices?