作者: dune
日時: 2004/1/04(00:17)
極悪です。

藤岡和夫 さんの [TSfree:588] Re: 欄区切りのソート から
>　あっ、そうですね(^^;)そのSchwartz変換とか、
>Guttman-Rosler 変換というのは、どのような原理なのでしょうか。

Schwartz 変換は @nifty フォーラム時代にわたなべさんがさりげ
なく紹介してたと思いますが、ソートを始める前にフィールド（ソ
ートキー）と元々のデータを配列に変換しておくものです。ソート
中はフィールドの比較だけすればいいので処理が速くなります。

Guttman-Rostler 変換は配列ではなくひとつの文字列に変換するも
のです。ソート中は文字列の比較だけになるので、配列のデリファ
レンスが不要になり、sort 関数自体も組み込みの比較処理を使う
ので最速になります。

特定のフィールドでソートするとか、大文字小文字を無視してソー
トする場合はとりあえず Schwartz 変換、フィールドが固定長だっ
たり、IP アドレスのようにとりうるデータのサイズがわかってい
る場合は Schwartz 変換が使えます。

「○○変換」は perl 独自の用語かもしれませんが、処理時間がデ
ータ数 N に比例する前処理と後処理に時間をかけて、N log N に
比例するメインの sort 部分の処理を軽くすれば、結果的に速くな
る、というのは他の言語でも同じでしょう。



日本語と読みと英語がタブで区切られた辞書ファイル（dict.utf8）
・・・
悪霊    [あくれい]  /evil spirit/
悪路    [あくろ]    /bad road/
悪露    [おろ]  /lochia/post-natal vaginal discharge/
・・・
を英語のフィールド（$field = 2）をキーにしてソートする例です。
アルファベットの大文字小文字は同一視します。データは１万４千行
あります。

スクリプトを普通に書くとこんなかんじです（test1.pl）
    use strict;
    my $field = 2;
    sub bywhat{
        (split(m/\t/,"\U$a"))[$field] cmp (split(m/\t/,"\U$b"))[$field]
            or
        $a cmp $b;
    }
    print sort bywhat <STDIN>;

Schwartz 変換で書いた場合（test2.pl）
    use strict;
    my $field = 2;
    print map{ $_->[0] }
            sort{ $a->[1] cmp $b->[1] or $a->[0] cmp $b->[0] }
            map{ [$_,(split(m/\t/,"\U$_"))[$field]] }
            <STDIN>;

Guttman-Rostler 変換で書いた場合（test2.pl）
    use strict;
    my $field = 2;
    print map{ substr($_,1024) }
            sort
            map{ pack("A1024",(split m/\t/,"\U$_")[$field]).$_ }
            <STDIN>;

本題とは関係ないですが、時間を計測するためのモジュール
    use strict;
    my $time;
    END{ print STDERR "time cost ",time - $time,"[sec]\n" }
    BEGIN{ $time = time }

実行するとこんなかんじです。
    
    D:% perl -Mkeisoku test1.pl  <dict.utf8 >test1.utf8
    time cost 19[sec]
    
    D:% perl -Mkeisoku test2.pl  <dict.utf8 >test2.utf8
    time cost 14[sec]
    
    D:% perl -Mkeisoku test3.pl  <dict.utf8 >test3.utf8
    time cost 11[sec]
    
    D:%

最後の Guttman-Rostler 変換がいちばん速いです（めでたしめで
たし）。
＃あらためて勉強しながら書いてしまった・・・

藤岡和夫 さんの [TSfree:588] Re: 欄区切りのソート から
>　僕は日常的には連想配列に同一のキーがあるときは、一つのキ
>ーにタブかなにかで挟んで、どんどん値を集めちゃって、後から
>処理しています。まあ、連想配列のキーにはユニークなものを使
>うことがよいわけですけど、現実はそう甘くありませんね。

キーの後ろに行番号（$.）をつければ安定ソートになるし、単に元
のデータをくっつけるだけでもいいかも。
-- 
FZH01112 at nifty.com
http://hpcgi1.nifty.com/dune/gwiki.pl?