Wednesday, September 19, 2007

Schwarzian Transform

I like to remind myself of this Perl gem every so often. I always call it Schwarzian transform but it's actually Schwartzian transform.

#using schwarzian transform
#@sorted contains objects sorted by their distance
my @sorted=
map {$_->[1]}
sort { $a->[0] <=> $b->[0] }
map { [$_->distance(), $_ ] } @{$paObject};

map EXPRESSION, list returns a new list whose elements are the outcome of the expression
Example: @newArray = map {uc $_}, @array
is just
@array = qw(a b c d);
@newArray = ();
foreach my $temp (@array) {
   push @newArray, uc $temp;

back to the example...
$paObject is a pointer to an array of objects.   The object has a method name distance() that returns an int
@{$paObject} dereferences the array.
working backwards,

map { [$_->distance(), $_ ] } @{$paObject}, creates an array like [[10,object reference 1],[2,object reference 2]]

and then feeds that into sort { $a->[0] <=> $b->[0] } which sorts according to the element at index 0

keeping with this example it yields [[2,object reference 2],[10, object reference 1]] 
which is fed into map {$_->[1]} which selects element at index 1

so now @sorted contains [object reference 2, object ref]

The benefit of the algorithm is that you only call the distance() method for each object once.  
If this method is computationally intensive and the list is large, the savings can be quite large.  
If your list is small, it's probably better to something like: @sorted =  {$a <=> $b} @unsorted

No comments: