高效排序

有这么一种情况：要对一个数组中的元素排序，而排序规则是一个自定义的函数。

典型的代码结构是这样的：

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
{
    my $call_total=0;
    sub ask_monkey_about(){
        my $people=shift;
        ++$call_total;
        return$people;
    }
    sub get_total(){
        return$call_total;
    }
}
my @cataways=qw(Gilligan Skippers Professor Ginger Mary_Ann Thurston Lovey);
my @wasters=sort {&ask_monkey_about($a) cmp  &ask_monkey_about($b)} @cataways;
print &get_total(),"\n";

要对@cataways中的元素排序，规则在子程序ask_monkey_about中定义了（这里是个示意，所以什么也没干，直接这回原值）。

排序的时候，直接把子程序写在sort语句中。

变量$call_total用来计算子程序被调用了多少次。

从输出结果可以看到，有7个元素的数组排序，子程序被调用了26次。

而实际上，叧要调用7次就完全足够了。多出来的19次完全是重复调用。如果未加任何优化，当待排序的元素个数很多时，规则子程序的调用次数会更加多，如对一个有1000个数的数组排序，按17行的写法，规则子程序会被调用将近2000次。这样做太傻了，白白的付出了多一倍的子程序调用开销，如果规则更加复杂，程序的效率就非常低。

有一个办法可以避免多出来的调用——先把规则子程序的返回值算出来。

#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;
{
    my $call_total=0;
    sub ask_monkey_about(){
        my $people=shift;
        my $people=shift;
        ++$call_total;
        return $people;
    }
    sub get_total(){
        return $call_total;
    }
}
my @cataways=qw(Gilligan Skippers Professor Ginger Mary_Ann Thurston Lovey);
my @names_and_pineapples=map {
    [$_,&ask_monkey_about($_)]
} @cataways;
my @wasters=sort {$a->[1] cmp $b->[1]} @names_and_pineapples;
my @names=map $_->[0] @wasters;
print &get_total(),"\n";

在上面这段程序的第17~19行，先将待排序数组的每个规则返回值都计算出来了，并把原值和返回值放在一个匿名数组中，作为一个中间结果集@names_and_pineapples的元素。即，@names_and_pineapples中有scalar @cataways个匿名数组，每一个匿名数组中有2个元素，分别是@cataways中1个元素的原值和规则返回值。然后以中间结果集为对象进行排序，排序关键字是其中的规则返回值。排序结束后，在排序结果集中取出原值即可。这样，规则子程序叧调用了和待排序对象个数一样的次数，在这里是7次。返是一种以空间换时间的思想，毕竟中间结果集要多占用一倍的空间（至少）。