in reply to Things I have learnt
The value of the S::T is that you do all your potentially expensive functions calls once per value, rather than many times.
Normally when you sort one list into another, the normal perl idioms go like this
my @output = sort @input; # default sort using eq to compare values my @output = sort {$a <=> $b} @input; # numeric sort my @output = sort some_func @input; # custom algorithm
Now lets have look at that last one - how often does some_func get called? Heres some code to show a potential worst case scenario
#!/usr/bin/perl -w use strict; my @input = (1..6); my $calls; my $fibcalls; my @output = sort reorder @input; # how many calls to fib() ? sub reorder { $calls++; return fib($a) <=> fib($b); } sub fib { my $val = shift; $fibcalls++; $val == 0 ? return $val: $val == 1 ? return $val : return fib($val - 1) + fib($val - 2); } print "called $calls times - fib calls $fibcalls\n";
Output is
cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/lister.pl" called 9 times - fib calls 150
OK, so a fibonacci sequence is exagerating the impact, but even so, what if some_func was doing some DBI-based lookup, using LWP or something else potential slow or expensive ?
Wouldn't it be better that we call some_func once for each unique value ?
Well we can. Looking at what we have so far, sort takes an input list (and potentially a function to operate on elements of that list) and returns a list. Wouldn't it be better if, instead of sort calling some_func repeated, often for a value it has already seen, we gave sort a list of values with some_func already applied ?
What we need is a function that takes a list, applies a function to each element once and once only, and returns a list of those function applications.
That function is map
We can write a trivial implementation of map thus
code>sub my_map { my ($function, @values) = @_; my @results; foreach my $value (@values) { push @results, $function->($value); } return @results; } </code>
Putting that together, we can show my_map applied to a list thus
#!/usr/bin/perl -w use strict; my @input = (1..6); my @output = my_map(\&double, @input); sub double { return 2 * shift; } sub my_map { my ($function, @values) = @_; my @results; foreach my $value (@values) { push @results, $function->($value); } return @results; } use Data::Dumper; print Dumper \@output;;
Results are
cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/subber.pl" $VAR1 = [ 2, 4, 6, 8, 10, 12 ];
So to proceed, we want to pass the list of values that map has already processed to sort, and have sort compare those.
Like this
my @output = sort {$a <=> $b} map {fib($_)} @input;
But we have a problem now - @output is the sorted list of values that have had fib() applied to them, not the original list. If we put this together with our original example, we can see it more clearly
Output is#!/usr/bin/perl -w use strict; my @input = (1..6); my $calls; my $fib_calls; my @output = sort {$calls++; $a <=> $b} map {fib($_)} @input; sub fib { my $val = shift; $fib_calls++; $val == 0 ? return $val: $val == 1 ? return $val : return fib($val - 1) + fib($val - 2); } print "called $calls times - fib $fib_calls\n"; use Data::Dumper; print Dumper(\@output);
cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/lister.pl" called 9 times - fib 58 $VAR1 = [ 1, 1, 2, 3, 5, 8 ];
We only made 58 fib calls this time, but the output is wrong - it is the sorted fibonacci sequence, not the original list. How can we fix this ?
Map to the rescue. What we do is have the first map return a list of tuple's - in other word, pairs of values. The tuples are made up of the original value and the value with some_func (fib) applied e.g.
Output of this ismy @output = map {[$_, fib($_)]} @input;
cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/lister.pl" $VAR1 = [ [ 1, 1 ], [ 2, 1 ], [ 3, 2 ], [ 4, 3 ], [ 5, 5 ], [ 6, 8 ] ];
See how we have the pairs (value, some_func(value)) ?
So what we want now is for sort to use the second value in the pair to compare, but use the first value in generating the output list. Well sort wont do that, but we can use map again - it takes a list, does a manipulation to each element and returns a list of those manipulations. Code for that is
my @output = map {$_->[0]} # extract just the original # value from the tuple sort {$a->[1] <=> $b->[1]} # sort based on the # computed value map {[$_, some_func($_)]} # create (value, computed) # tuples @input;
Output is as required
HTH...
use brain;