The Schwartzian Transform would work for this application, just like it would for any sort. It is a replacement for a normal sort which trades memory space for speed. For example, imagine you need to sort by the foozle() of each member of a list. You could do it the easy way:
@result = sort { foozle($a) <=> foozle($b) } @list;
But the problem is that foozle() will be called multiple times for each item being sorted. If foozle() is a slow function then you'll be wasting a lot of time. The Schwartzian transform works by building up a temporary data structure than contains the value and the foozle() of that value. Example:
@result = map { $_->[1] }
sort { $a->[0] <=> $b->[0] }
map { [ foozle($_), $_ ] }
@list;
However, in this case the "foozle()" is just a hash lookup. Hash lookups are so fast that an ST is probably more expensive than a simple sort.
-sam
|