Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

Comment on

( #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

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/" 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/" $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

#!/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);
Output is

cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/" 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.

my @output = map {[$_, fib($_)]} @input;
Output of this is
cd /home/le6303/src/perl/ /usr/bin/perl -w "/home/le6303/src/perl/" $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


use brain;

In reply to Re: Things I have learnt by leriksen
in thread Things I have learnt by neilh

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (6)
    As of 2017-03-24 20:11 GMT
    Find Nodes?
      Voting Booth?
      Should Pluto Get Its Planethood Back?

      Results (307 votes). Check out past polls.