end0tknr's kipple - 新web写経開発

http://d.hatena.ne.jp/end0tknr/ から移転します

シュウォーツ変換によるsortの高速化

sortを高速化する際、「シュウォーツ変換」という手法があるそうです。
シュウォーツ変換ではsortで要素の比較に用いる条件が複雑な場合、予め各要素を比較するための値を算出し、何度も計算するのを避けることで高速化を可能にします。

サンプルコードは次の通り

@data = map {$_->[0]}
        sort {$a->[2] <=> $b->[2]}
        map {[$_, split /,/]} @data;
@data = map {$_->[0]},
        sort {$a->[1] <=>$b->[1]}
        map {$_,length($_)}, @data