masatoz’s blog

プログラミングのメモ、日常の記録

高速ソート手法のシュワルツ変換はわりと簡単に実装できることがわかった

「すぐわかる Perlオブジェクト指向」からシュワルツ変換を取り上げます。

シュワルツ変換は、ソートを高速化するための方法です。

ソート対象の文字列の長さを最初に調べてインデックスをつくり、ハッシュの値にします。そのハッシュのキーにはソートする文字列そのものを入れます。

それでインデックスを比較した結果に応じてハッシュのキーを取り出すことでソートすることができます。 こうすることで、たぶん、文字列の長さをしらべる処理回数を減らすことができるため速度が上がるのだと思います。

数MB程度以上のテキストをソートする際に威力を発揮するようです。

いきなり完成コード

mapを使うと短く書けます。また玄人っぽい雰囲気がでます。

慣れないと読みづらいのが難点かも。

    my @sorted = map { 
        $_->[0], "\n" }  # 文字列を取り出す
        sort { $b->[1] <=> $a->[1] }  # 文字列の長さを比較
        map  [$_, length($_)], @lines; # 文字列とその長さのリストをつくる
    }

違う書き方

mapをforに置き換えてみます。

my @sorted = ();
for (@lines) {
    push(@sorted, [$_, length($_)]);
}
@sorted = sort { $b->[1] <=> $a->[1] } @sorted;

my @sorted2 = ();
for (@sorted) {
    push(@sorted2, $_->[0])
}

print map { $_,"\n" } @sorted2;

こんなんだっけ…ものすごくごちゃごちゃになってしまいました。

やっぱりmapを使った方がよいかもしれない!