>> sorting has a best expected runtime of O(nlog(n)), finding the max item
>> via a linear search is O(n).
>
> This should really be in the FAQ, but here we go again. This is why big
> O notation only tells you half the story. Sort is implemented in C and
> is one operation as far as Perl is concerned, whereas the loop method
> contains many Perl operands that must be interpreted. For all but the
> largest data sets the C code beats the Perl code hands down (IIRC it
> takes half the time). If you do not believe me check out other threads
> in this mailing list or run the benchmarks yourself.
Ok, it's a slow day, I'll bite at that. Try as I might. I can't make
your sort beat my map-based linear search.
use strict;
use Benchmark;
my $elements = shift;
my $iterations = shift;
srand();
our @array = ();
for(my $i = 0; $i < $elements; $i++) {
push @array, rand();
}
my $coderef1 = sub {
my @a = @array;
@a = sort { $a <=> $b } @a;
return $a[$#a];
};
my $coderef2 = sub {
my @a = @array;
my $max = $array[0];
map {($max < $_)?($max = $_):undef} @a;
return $max;
};
Benchmark::cmpthese($iterations, {'sort'=> $coderef1, 'map'=>
$coderef2 });
# tiny arrays (10 els)
15:14:53(george@localhost)[~]> perl -w f.pl 10 10000
Benchmark: timing 10000 iterations of map, sort...
map: 0 wallclock secs ( 0.20 usr + 0.00 sys = 0.20 CPU) @
50000.00/s (n=10000)
(warning: too few iterations for a reliable count)
sort: 2 wallclock secs ( 1.43 usr + 0.00 sys = 1.43 CPU) @
6993.01/s (n=10000)
Rate sort map
sort 6993/s -- -86%
map 50000/s 615% --
# small array (100 els)
15:08:42(george@localhost)[~]> perl -w f.pl 100 1000
Benchmark: timing 1000 iterations of map, sort...
map: 0 wallclock secs ( 0.20 usr + 0.00 sys = 0.20 CPU) @
5000.00/s (n=1000)
(warning: too few iterations for a reliable count)
sort: 2 wallclock secs ( 1.53 usr + 0.00 sys = 1.53 CPU) @
653.59/s (n=1000)
Rate sort map
sort 654/s -- -87%
map 5000/s 665% --
# medium array (1000 els)
15:08:13(george@localhost)[~]> perl -w f.pl 1000 1000
Benchmark: timing 1000 iterations of map, sort...
map: 2 wallclock secs ( 1.61 usr + 0.00 sys = 1.61 CPU) @
621.12/s (n=1000)
sort: 17 wallclock secs (16.47 usr + 0.00 sys = 16.47 CPU) @
60.72/s (n=1000)
Rate sort map
sort 60.7/s -- -90%
map 621/s 923% --
# large array (10000 els)
Benchmark: timing 1000 iterations of map, sort...
map: 22 wallclock secs (20.62 usr + 0.00 sys = 20.62 CPU) @
48.50/s (n=1000)
sort: 196 wallclock secs (180.22 usr + 0.00 sys = 180.22 CPU) @
5.55/s (n=1000)
Rate sort map
sort 5.55/s -- -89%
map 48.5/s 774% --
// George Schlossnagle
// Principal Consultant
// OmniTI, Inc http://www.omniti.com
// (c) 240.460.5234 (e) [EMAIL PROTECTED]
// 1024D/1100A5A0 1370 F70A 9365 96C9 2F5E 56C2 B2B9 262F 1100 A5A0
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
