[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