[Chicago-talk] neat little optimization
Steven Lembark
lembark at wrkhors.com
Wed Oct 13 10:23:30 CDT 2004
> Uses? Minimal. You need a very frequently called function that does a
> lot of hash lookups based upon the stringified version of the object.
> If it doesn't do a lot of lookups or isn't called a hell of a lot, you
> probably wouldn't even be able to measure the difference.
>
> But for super speed critical stuff? Works like a charm.
Hash lookups are expensive themselves. You may be able to
use a disjointed Schwartzian Transform to get an array of
sorted [ key, value ] pairs then use something like:
my $key = '';
my $val = '';
my @keyz = ();
my @valuz = ();
my @stuff =
# skip the final map, leaving the sort key attached.
sort { $a->[0] cmp $b->[0] }
map { [ "$_", $_ ] }
@itemz;
for( @stuff )
{
unless( $key eq $_->[0] )
{
# save the values, if avoids pushing
# extra value.
if( $key )
{
push @valuz, $val;
push @keyz, $key;
}
$key = $_->[0];
$val = 0;
}
$val += $_->[1]; # whatever your calculation is...
}
# at this point you have @keyz and @valuz in order
# now put them in a hash for easier access.
my %result = ();
@result{@keyz} = @valuz;
One obvious speedup is doing away with the extraneous @stuff:
for
(
sort { $a->[0] cmp $b->[0] }
map { [ "$_", $_ ] }
@itemz
)
{
...
}
Though, the whole thing does look a bit listish to begin
with:
my $key = '';
my $sum = '';
%totalz =
map
{
if( $key eq $_->[0] )
{
$sum += $_->[1][0]; # whatever...
# empty list
()
}
else
{
if( $key )
{
my $a = $key;
my $b = $sum;
$key = $_->[0];
$sum = $_->[1][0]; # whatever
# current key and total go onto the list
( $a, $b )
}
}
}
sort{ $a->[0] cmp $b->[0] }
map { [ "$_", $_ ] }
@itemz;
The point is that you can probably avoid hash lookups,
and in some cases the sort will be faster than repeated
hashed access.
--
Steven Lembark 85-09 90th Street
Workhorse Computing Woodhaven, NY 11421
lembark at wrkhors.com 1 888 359 3508
More information about the Chicago-talk
mailing list