Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
I am not sure how to precisely measure its speed in Perl.

As Corion said, you can use Benchmark as I showed in the root node, and I also think that the built-in sort will always be faster. In fact, roughly 19 times faster:

Rate custom qsort sort custom 10697/s -- -83% -95% qsort 62127/s 481% -- -70% sort 209474/s 1858% 237% --

Where qsort is from List::MoreUtils.

#!/usr/bin/env perl use warnings; use strict; use Benchmark 'cmpthese'; use List::Util 'shuffle'; # 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/; srand 123; my @tests = ( # first item here will be used in benchmark by default [ [shuffle -52,-50..50,52,0], [-52,-50..-1,0,0..50,52], 'random'], [ [-52,-50..50,52,0], [-52,-50..-1,0,0..50,52], 'ordered' ], [ [shuffle -50..-1,1..50], [-50..-1,1..50], 'no zero'], [ [shuffle -102,-100..-1], [-102,-100..-1], 'negative only' ], [ [shuffle -102,-100..0], [-102,-100..-1,0], 'negative only with zero'], [ [shuffle 0..100,102],[0..100,102],'positive only with zero' ], [ [shuffle 1..100,102],[1..100,102],'positive only without zero'], [ [shuffle((-4..4)x10)], [ map {($_)x10} -4..4 ], 'many dupes' ], ); for my $t (@tests) { print "# ### Benchmarking with data set: $$t[2] ###\n"; cmpthese(DO_CHECK ? 1 : -2, { sort => sub { my @list = @{$$t[0]}; @list = sort {$a<=>$b} @list; Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK; }, qsort => sub { use List::MoreUtils 'qsort'; my @list = @{$$t[0]}; qsort {$a<=>$b} @list; Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK; }, custom => sub { my @list = @{$$t[0]}; QSort(@list); Compare(\@list,$$t[1]) or die "<@list>" if DO_CHECK; }, }); } sub QSort { @_ or return; my $First = 0; my $Last = @_ - 1; my @QStack; my $StackPtr = 0; my $temp; my $i; my $j; for (;;) { do { $temp = $_[int(($Last + $First) / 2)]; $i = $First; $j = $Last; do { while ($_[$i] < $temp) { $i++; } while ($_[$j] > $temp) { $j--; } if ($i < $j) { @_[$i, $j] = @_[$j, $i]; } if ($i <= $j) { $i++; $j--; } } while ($i <= $j); if ($i < $Last) { $QStack[$StackPtr++] = $i; $QStack[$StackPtr++] = $Last; } $Last = $j; } while ($First < $Last); $StackPtr or return; $Last = $QStack[--$StackPtr]; $First = $QStack[--$StackPtr]; } } __END__ # ### Benchmarking with data set: random ### Rate custom qsort sort custom 10697/s -- -83% -95% qsort 62127/s 481% -- -70% sort 209474/s 1858% 237% -- # ### Benchmarking with data set: ordered ### Rate custom qsort sort custom 16593/s -- -72% -96% qsort 59065/s 256% -- -84% sort 376539/s 2169% 537% -- # ### Benchmarking with data set: no zero ### Rate custom qsort sort custom 10808/s -- -83% -95% qsort 65159/s 503% -- -69% sort 213372/s 1874% 227% -- # ### Benchmarking with data set: negative only ### Rate custom qsort sort custom 11058/s -- -82% -95% qsort 62126/s 462% -- -72% sort 219498/s 1885% 253% -- # ### Benchmarking with data set: negative only with zero ### Rate custom qsort sort custom 11441/s -- -82% -95% qsort 63315/s 453% -- -71% sort 217417/s 1800% 243% -- # ### Benchmarking with data set: positive only with zero ### Rate custom qsort sort custom 10453/s -- -83% -95% qsort 60424/s 478% -- -71% sort 212006/s 1928% 251% -- # ### Benchmarking with data set: positive only without zero ### Rate custom qsort sort custom 10900/s -- -83% -95% qsort 65471/s 501% -- -70% sort 216391/s 1885% 231% -- # ### Benchmarking with data set: many dupes ### Rate custom qsort sort custom 13091/s -- -89% -95% qsort 123098/s 840% -- -48% sort 238432/s 1721% 94% --

In reply to Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by haukex
in thread 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 perusing the Monastery: (1)
As of 2021-10-21 03:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (82 votes). Check out past polls.

    Notices?