Perl排序：施瓦茨变换

89ou

　　给定一个数组a = (a1, a2, ... , an)和一个函数fn()，现在对数组(fn(a1), fn(a2), ... , fn(an))排序。
　　如果用下面的方法直接排序的话，会存在很多的对fn()重复计算的情况。如果函数fn()比较复杂，这种重复会显得更加突出。
　　施瓦茨变换就是为了解决这个对fn()重复计算问题，如下：




1 my @sorted =
2   map $_->[0],
3   sort { $b->[1] <=> $a->[1] }
4   map [ $_, f($_) ],
5   @original;   
　　
泛化一点：




1 my @sorted =
2   map $_->[0],
3   sort { SORT COMPARISON USING $a->[1] AND $b->[1] }
4   map [ $_, EXPENSIVE FUNCTION OF $_ ],
5   @original;
6  
　　
举例：




1 # case insensitive sorting in alphabetical order
2  my @sorted =
3   map $_->[0],
4   sort { $a->[1] cmp $b->[1] }
5   map [ $_, "\U$_" ],
6   @original
　　
在三级排序中使用施瓦茨变换：




1 # 首先用SOME FUNCTION排序，再用ANOTHER排序，最后用
2 # YET ANOTHER排序
3  my @sorted =
4   map $_->[0],
5   sort { SORT COMPARISON USING $a->[1] AND $b->[1] or
6           ANOTHER USING $a->[2] AND $b->[2] or
7       YET ANOTHER USING $a->[3] AND $b->[3] }
8   map [ $_, SOME FUNCTION OF $_, ANOTHER, YET ANOTHER ],
9   @original;
10  
　　或者将每次计算的结果保存一下，这也避免了重复计算(举例用cmp做字符串比较)：




1 @sorted = do {
2     my %fv;
3     sort { ($fv{$a} ||= f($a))
4                   cmp
5                ($fv{$b} ||= f($b))
6             }
7             @original
8 };
　　
或者把用于cache的hash定义在do block外：




1 my %fv;
2  @sorted =
3     sort { (fv{$a} ||= f($a))
4                    cmp
5                (fv{$b} ||= f($b))
6     }
7     @original;
　　或者事先把所有的fn()计算出来：




1 my %fv;
2  @gv{@original} = map { fn($_) } @original;
3  @sorted = sort { $fv{$a} cmp $v{$b} } @original;
　　
或者用Memoize模块：




use Memoize;
memoize('fn');
@sorted = sort { fn($a) cmp fn($b) } @original;