シュワルツ変換

シュワルツ変換

Randal L. Schwartzが最初に指摘したことで知られるソート手法。計算量の多いソートを行う際,比較に必要な結果をあらかじめ計算しておくことでオーバーヘッドを大幅に減らすことができる。

以下はperlfaq4より引用

@sorted = map  { $_->[0] }
  sort { $a->[1] cmp $b->[1] }
  map  { [ $_, uc( (/\d+\s*(\S+)/)[0]) ] } @data;

また,シュワルツ変換より高速なソート手法が有ることも知られている。

@idx = ();
for (@data) {
  ($item) = /\d+\s*(\S+)/;
  push @idx, uc($item);
}
@sorted = @data[ sort { $idx[$a] cmp $idx[$b] } 0 .. $#idx ];