<snip>
> 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.
</snip>
Well, forcing the sort to copy the entire array isn't exactly fair.
The proper way to write the sort based max is
my $max = (sort { $a <=> $b } @array)[-1];
This keeps Perl from copying the entire array (it only grabs the last
element). Here are my benchmark results with three added cases:a naive
Perl foreach loop, a shorter Perl for loop, a version of your map based
max (let me know if you have problems with my cut down version), and a
version written with Inline::C.
<output>
Sample set is 10
Rate map for naive sort Inline::C
map 63232/s -- -1% -5% -63% -81%
for 63735/s 1% -- -4% -63% -81%
naive 66248/s 5% 4% -- -61% -80%
sort 171775/s 172% 170% 159% -- -48%
Inline::C 331567/s 424% 420% 400% 93% --
Sample set is 100
Rate map for naive sort Inline::C
map 9091/s -- -18% -19% -31% -95%
for 11035/s 21% -- -2% -16% -93%
naive 11240/s 24% 2% -- -15% -93%
sort 13159/s 45% 19% 17% -- -92%
Inline::C 169712/s 1767% 1438% 1410% 1190% --
Sample set is 200
Rate map sort for naive Inline::C
map 4787/s -- -12% -17% -20% -96%
sort 5444/s 14% -- -6% -9% -95%
for 5781/s 21% 6% -- -3% -95%
naive 5985/s 25% 10% 4% -- -95%
Inline::C 114686/s 2296% 2006% 1884% 1816% --
Sample set is 1000
Rate sort map for naive Inline::C
sort 806/s -- -17% -31% -36% -97%
map 976/s 21% -- -16% -22% -97%
for 1169/s 45% 20% -- -7% -96%
naive 1252/s 55% 28% 7% -- -96%
Inline::C 29954/s 3614% 2968% 2462% 2292% --
Sample set is 10000
Rate sort map for naive Inline::C
sort 42.1/s -- -48% -62% -64% -96%
map 81.2/s 93% -- -27% -30% -93%
for 111/s 163% 36% -- -5% -90%
naive 117/s 177% 44% 5% -- -90%
Inline::C 1117/s 2552% 1275% 910% 858% --
Sample set is 100000
Rate sort map for naive Inline::C
sort 2.12/s -- -73% -80% -81% -97%
map 7.77/s 266% -- -27% -31% -89%
for 10.6/s 400% 37% -- -6% -86%
naive 11.3/s 434% 46% 7% -- -85%
Inline::C 73.9/s 3385% 852% 597% 553% --
<output>
Personally I find the results amazing. I would have sworn that the for
version of max would have beaten the naive version, but it never did.
As we can see from the results the best case is always the Inline::C
version of max (as expected); however Inline::C is not always available,
so the next best thing is the sort version of max for sample sets <= 100
and the naive version of max for all other sample sets.
<code>
#!/usr/bin/perl
use strict;
use Benchmark;
use Inline 'C';
our @array;
my %sub = (
'sort' => sub {
our @array;
return (sort { $a <=> $b } @array)[-1];
},
'map' => sub {
our @array;
my $max = $array[0];
map { ($max < $_)?($max = $_):undef } @array;
return $max;
},
'naive' => sub {
our @array;
my $max = $array[0];
foreach my $current (@array) {
if ($max < $current) {
$max = $current
}
}
return $max;
},
'for' => sub {
our @array;
my $max = $array[0];
$max < $_ ? $max = $_ : undef for @array;
return $max;
},
'Inline::C' => sub {
our @array;
return Max(@array);
}
);
foreach my $array_size (10,100,200,1_000,10_000,100_000) {
our @array = map { .5 - rand } (0..$array_size);
my $max;
print "Sample set is $array_size\n";
my $results = Benchmark::timethese(-3, \%sub, 'none');
Benchmark::cmpthese($results);
print "\n";
}
__END__
__C__
void Max (SV* first_element, ...) {
Inline_Stack_Vars;
int i;
double max = SvNV(Inline_Stack_Item(0));
for (i = 0; i < Inline_Stack_Items; i++) {
double current = SvNV(Inline_Stack_Item(i));
if (max < current) max = current;
}
Inline_Stack_Reset;
Inline_Stack_Push(newSVnv(max));
Inline_Stack_Done;
}
</code>
--
Today is Pungenday the 52nd day of Confusion in the YOLD 3168
Missile Address: 33:48:3.521N 84:23:34.786W
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
