We don't bite newbies here... much PerlMonks

### Comment on

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

```#!/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/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.

```my @output =  map {[\$_, fib(\$_)]} @input;
Output of this is
```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;

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

Title:
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.
• 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: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
 [shmem]: because it affects "my team" [shmem]: ah well... git is incomplete. There are commands missing: [shmem]: git stop crap [shmem]: for instance [karlgoethebier]: shmem]: "The Other Team" sounds like "The Dark Side Of The Force" in this context [karlgoethebier]: Ouch! [karlgoethebier]: crawls back to his cell

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (7)
As of 2018-03-20 18:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (258 votes). Check out past polls.

Notices?