Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re^4: sort an array with +ve & -ve numbers in it

by grinder (Bishop)
on Apr 03, 2009 at 21:52 UTC ( #755350=note: print w/ replies, xml ) Need Help??


in reply to Re^3: sort an array with +ve & -ve numbers in it
in thread sort an array with +ve & -ve numbers in it

Easier and simpler, but less efficient

Woah! I would benchmark that before making such a statement. I expect you'll need a seriously huge list before the O(n log n) starts to lose to your straight O(n).

There's no debate that it will, but the problem is the 0(n) algorithm is using a comparatively large number of slow ops, where as the sort compiles down into a single op, and there you're running at C speed (simple {$a <=> $b} blocks are recognised and special-cased during the parse). This will drown out the extra cost for a long, long time (that is: for a long list of values). On my machine, the cross-over occurs between 100 000 and 1 000 000 elements (and I had to run the million element benchmark for 15 seconds in order to give it enough time to settle down)

Rate with_scan_1 with_sort_1 with_scan_1 35662/s -- -53% with_sort_1 76332/s 114% -- Rate with_scan_2 with_sort_2 with_scan_2 6838/s -- -40% with_sort_2 11437/s 67% -- Rate with_scan_3 with_sort_3 with_scan_3 759/s -- -11% with_sort_3 853/s 12% -- Rate with_sort_4 with_scan_4 with_sort_4 62.6/s -- -18% with_scan_4 76.2/s 22% -- Rate with_sort_5 with_scan_5 with_sort_5 3.38/s -- -47% with_scan_5 6.38/s 89% -- s/iter with_sort_6 with_scan_6 with_sort_6 4.88 -- -66% with_scan_6 1.65 196% --

And since either choice is crazy fast enough for me, I'd throw my lot in with the more succinct version -- less chance of introducing semantic mistakes and off-by-one errors). For instance, I had to think for a little while about how you initialised $min and $max...

#! /usr/local/bin/perl use strict; use warnings; use Benchmark 'cmpthese'; my @s1 = (999, -999, map {rand(900)-900} 0..10); my @s2 = (999, -999, map {rand(900)-900} 0..100); my @s3 = (999, -999, map {rand(900)-900} 0..1000); my @s4 = (999, -999, map {rand(900)-900} 0..10000); my @s5 = (999, -999, map {rand(900)-900} 0..100000); my @s6 = (999, -999, map {rand(900)-900} 0..1000000); sub with_scan { my ( $min, $max ) = @_; for my $element ( @_ ) { $min = $element if $min > $element; $max = $element if $max < $element; } return ($min, $max); } sub with_sort { return (sort {$a <=> $b} @_)[0,-1]; } print join(',', with_scan(@s1)), $/; print join(',', with_sort(@s1)), $/; cmpthese( -3, { 'with_sort_1' => sub {with_sort(@s1)}, 'with_scan_1' => sub {with_scan(@s1)}, } ); cmpthese( -3, { 'with_sort_2' => sub {with_sort(@s2)}, 'with_scan_2' => sub {with_scan(@s2)}, } ); cmpthese( -3, { 'with_sort_3' => sub {with_sort(@s3)}, 'with_scan_3' => sub {with_scan(@s3)}, } ); cmpthese( -3, { 'with_sort_4' => sub {with_sort(@s4)}, 'with_scan_4' => sub {with_scan(@s4)}, } ); cmpthese( -3, { 'with_sort_5' => sub {with_sort(@s5)}, 'with_scan_5' => sub {with_scan(@s5)}, } ); cmpthese( -15, { 'with_sort_6' => sub {with_sort(@s6)}, 'with_scan_6' => sub {with_scan(@s6)}, } );

• another intruder with the mooring in the heart of the Perl


Comment on Re^4: sort an array with +ve & -ve numbers in it
Select or Download Code

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (10)
As of 2015-07-07 00:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (86 votes), past polls