No such thing as a small change | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
OK, I too will bite.
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
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
Output is
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
Results are
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
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
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 is
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
Output is as required HTH... use brain; In reply to Re: Things I have learnt
by leriksen
|
|