7.3 Sorting Efficiently

As the Professor tries to maintain the community computing facility (built entirely out of bamboo, coconuts, and pineapples, and powered by a live monkey), he continues to discover that people are leaving entirely too much data on the single monkey-powered filesystem and decides to print a list of offenders.

The Professor has written a subroutine called ask_monkey_about( ) which is given a castaway's name and returns the number of pineapples of storage they use. You have to ask the monkey because he's in charge of the pineapples. An initial naive approach to find the offenders from greatest to least might be something like:

my @castaways =
  qw(Gilligan Skipper Professor Ginger Mary_Ann Thurston Lovey);
my @wasters = sort {
  ask_monkey_about($b) <=> ask_monkey_about($a)
} @castaways;

In theory, this would be fine. For the first pair of names (Gilligan and Skipper), you ask the monkey "how many pineapples does Gilligan have?" and "how many pineapples does Skipper have?" You get back two values from the monkey and use them to order Gilligan and Skipper in the final list.

However, at some point, you have to compare the number of pineapples that Gilligan has with another castaway as well. For example, suppose the pair is Ginger and Gilligan. Ask the monkey about Ginger, get a number back, and then ask the monkey about Gilligan...again. This will probably annoy the monkey a bit, since you already asked earlier. But you need to ask for each value two, three, or maybe even four times just to put the seven values into order.

This can be a problem because it irritates the monkey.

How do you keep the number of monkey requests to a minimum? Well, you can build a table first. Use a map with seven inputs and seven outputs, turning each castaway item into a separate array reference, with each referenced array consisting of the castaway name and the pineapple count reported by the monkey:

my @names_and_pineapples = map {
  [ $_, ask_monkey_about($_) ]
} @castaways;

At this point, you asked the monkey seven questions in a row, but that's the last time you have to talk to the monkey! You now have everything you need to finish the task.

For the next step, sort the arrayrefs, ordering them by the monkey-returned value:

my @sorted_names_and_pineapples = sort {
  $b->[1] <=> $a->[1];
} @names_and_pineapples;

In this subroutine, $a and $b are still two elements from the list of things to be sorted. When you're sorting numbers, $a and $b are numbers; when you're sorting references, $a and $b are references. Dereference them to get to the corresponding array itself, and pick out item 1 from the array (the monkey's pineapple value). Because $b appears to the left of $a, it'll be a descending sort as well. (You want a descending sort because the Professor wants the first name on the list to be the person who uses the most pineapples.)

You're almost done, but what if you just wanted the top names, rather than the names and pineapple counts? You merely need to perform another map to transform the references back to the original data:

my @names = map $_->[0], @sorted_names_and_pineapples;

Each element of the list ends up in $_, so you'll dereference that to pick out the element 0 of that array, which is just the name.

Now you have a list of names, ordered by their pineapple counts, and a calm monkey, all in three easy steps.