On 02 Jun 2001 18:59:36 +0200, Adam Sjøgren wrote:
> Er'ed ikke overkill at sortere listen for at finde den største? (i
> princip, altså, næppe i praksis).
Faktisk overhovedet slet ikke i praksis, ser det ud til:
virgil
$ bin/maxtest 100000 a 100; bin/maxtest 100000 d 100; bin/maxtest 100000 r 100;
Testing functions: 100000 100000 100000
Benchmark: timing 100 iterations of max, max_naive, max_scan...
max: 27 wallclock secs (26.59 usr + 0.00 sys = 26.59 CPU) @ 3.76/s (n=100)
max_naive: 212 wallclock secs (211.76 usr + 0.02 sys = 211.78 CPU) @ 0.47/s (n=100)
max_scan: 144 wallclock secs (143.96 usr + 0.02 sys = 143.98 CPU) @ 0.69/s (n=100)
s/iter max_naive max_scan max
max_naive 2.12 -- -32% -87%
max_scan 1.44 47% -- -82%
max 0.266 696% 441% --
Testing functions: 100000 100000 100000
Benchmark: timing 100 iterations of max, max_naive, max_scan...
max: 30 wallclock secs (30.20 usr + 0.00 sys = 30.20 CPU) @ 3.31/s (n=100)
max_naive: 201 wallclock secs (200.20 usr + 0.07 sys = 200.27 CPU) @ 0.50/s (n=100)
max_scan: 134 wallclock secs (134.01 usr + 0.00 sys = 134.01 CPU) @ 0.75/s (n=100)
s/iter max_naive max_scan max
max_naive 2.00 -- -33% -85%
max_scan 1.34 49% -- -77%
max 0.302 563% 344% --
Testing functions: 99999 99999 99999
Benchmark: timing 100 iterations of max, max_naive, max_scan...
max: 80 wallclock secs (80.40 usr + 0.00 sys = 80.40 CPU) @ 1.24/s (n=100)
max_naive: 338 wallclock secs (336.62 usr + 0.08 sys = 336.70 CPU) @ 0.30/s (n=100)
max_scan: 274 wallclock secs (267.12 usr + 0.24 sys = 267.36 CPU) @ 0.37/s (n=100)
s/iter max_naive max_scan max
max_naive 3.37 -- -21% -76%
max_scan 2.67 26% -- -70%
max 0.804 319% 233% --
virgil
$
Jeg kan ikke komme med andre gæt end: 1) sort er optimeret godt og
grundigt og/eller 2) jeg har dummet mig i mit andet forsøg med
Benchmark modulet.
Her er det program jeg fik tampet sammen (jeg ku' ikke lige finde ud
af at undgå de dér fjollede test_* funktioner - gode råd er meget
velkomne!):
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw(cmpthese timediff timestr);
##### Subs:
sub max(\@) {
my($listref) = @_;
( sort {$a <=> $b} @{$listref} )[ $#{$listref} ];
}
sub max_scan(\@) {
my($listref)=@_;
my $max=${$listref}[0];
map { $max=$_ if $max<$_ } @{$listref};
return $max;
}
sub max_naive
{
my(@list)=@_;
my $max=$list[0];
map { $max=$_ if $max<$_ } @list;
return $max;
}
##### Init:
my $l=shift @ARGV;
my $type=shift @ARGV;
my @liste=create_list($type);
##### Args:
sub test_max
{
max(@liste);
}
sub test_max_scan
{
max_scan(@liste);
}
sub test_max_naive
{
max_naive(@liste);
}
##### Utility:
sub create_list
{
my($type)=@_;
if( $type eq "a" )
{
return (0..$l);
}
elsif( $type eq "d" )
{
return reverse(0..$l);
}
elsif( $type eq "r" )
{
my @liste;
srand(42); # Ensure same random list every time
map { push @liste, int(rand($l)) } (0..$l);
return @liste;
}
else
{
die "Unknown type: $type";
}
}
##### Run:
print "Testing functions: ";
print max(@liste) . " " . max_naive(@liste) . " " . max_scan(@liste) . "\n";
cmpthese(shift @ARGV,
{
'max' => 'test_max()',
'max_naive' => 'test_max_naive()',
'max_scan' => 'test_max_scan()',
});
exit 0;
--
"Bob Dylan? Han har en cool röst." Adam Sjøgren
asjo@koldfront.dk