Perl排序：施瓦茨变换
给定一个数组a = (a1, a2, ... , an)和一个函数fn()，现在对数组(fn(a1), fn(a2), ... , fn(an))排序。如果用下面的方法直接排序的话，会存在很多的对fn()重复计算的情况。如果函数fn()比较复杂，这种重复会显得更加突出。
施瓦茨变换就是为了解决这个对fn()重复计算问题，如下：
1 my @sorted =
2 map $_->,
3 sort { $b-> <=> $a-> }
4 map [ $_, f($_) ],
5 @original;
泛化一点：
1 my @sorted =
2 map $_->,
3 sort { SORT COMPARISON USING $a-> AND $b-> }
4 map [ $_, EXPENSIVE FUNCTION OF $_ ],
5 @original;
6
举例：
1 # case insensitive sorting in alphabetical order
2my @sorted =
3 map $_->,
4 sort { $a-> cmp $b-> }
5 map [ $_, "\U$_" ],
6 @original
在三级排序中使用施瓦茨变换：
1 # 首先用SOME FUNCTION排序，再用ANOTHER排序，最后用
2 # YET ANOTHER排序
3my @sorted =
4 map $_->,
5 sort { SORT COMPARISON USING $a-> AND $b-> or
6 ANOTHER USING $a-> AND $b-> or
7 YET ANOTHER USING $a-> AND $b-> }
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;
页:
[1]