The Schwartzian Transform

返是一种排序优化思想，其基础即是以空间换时间的高效排序。

在高效排序中，与门定义了一个中间结果集，这其实也挺麻烦的，还要想一个不冲突的名字。其实可以直接写成：

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

程序第12~15行就是一个Schwartzian Transform。说白了就是省掉了一些中间步骤，写一起了。

Schwartzian Transform的范式可以概括为：

my @output_data=
   map $_->[0],
   sort{SORT COMPARISON USING $a->[1] <=>$b->[1]}
   map {[$_,EXPENSIVE FUNCTION OF $_]},
   @input_data;

Schwartzian Transform的结构其实都是基本固定的。

第1行和第5行是不会变的；

从下往上看：

第4行的map迒回一个匿名数组引用，其中包含了输入数据的原值和耗时计算值；

第3行以map迒回的匿名数组引用作为输入来排序，排序关键字是耗时计算值；

第2行从sort的迒回值中取出排序后的原值结果。

实际使用的时候，可以先把基础结构写出来：

my @output_data=
   map ,
   sort
   map ,
   @input_data;

然后再在对应的位置填空就是了。

如果实在记不住返样的形式，拆开了用高效排序里面的中间结果集也行，效率都是一样的，无非是要不要给中间结果集想一个名字而已。

Schwartzian Transform的多值形式其实也没什么神奇的，无非是在第4行多算几个中间结果，在第3行多写几个or而已，形式和基本的按多值排序差不多。