sortの話(続き)
以前、Linux標準ソートのパフォーマンスが出ない
http://d.hatena.ne.jp/toritori0318/searchdiary?word=%2a%5bLinux%5d
というお話をしましたが、まだ続いてまして。
いろいろと調査した結果、キーが先頭に集中していると
結構パフォーマンスが出ることが判明しました。
例えば、
平均レコード長500b、カラム数約50、レコード数約100万件
というデータを、「A.5番目のキー+B.20番目のキー+C.30番目のキー」
でソートした時の処理速度を比較してみると…
- そのままの順番でキー指定してソートした場合
- →およそ20分
- A.B.C.をそれぞれ1,2,3番目にレイアウト変更してソートした場合
- →およそ2分
明らかにパフォーマンスが上がってるw
なので現在は以下のようなシェルを作成してソートしてます。
- 引数で受けとったキーで、先頭に置き換えるようにテキストのレイアウトを変更。
- sort実行。
- 引数で受け取ったキーから、元のレイアウトに戻す。
ただ、やはり余計な処理が入っているので自分的には不満…
オープンソースか何かでソート処理無いかなーと探していたところ、
msortというソートを発見!
というかDebianのパッケージで提供されてるじゃないですかw
パフォーマンスについてはあまり書かれてないですが、
試してみたかったのでインストールに挑戦しました。
まずはmsortをダウンロードしてインストールしてみる。
# cd /usr/local/src # wget http://billposer.org/Software/Downloads/msort-8.50.tar.gz # cd msort-8.50 # ./configure checking for a BSD-compatible install... /usr/bin/install -c checking whether build environment is sane... yes (中略) checking for regwcomp in -ltre... no configure: error: libtre not found. see http://laurikari.net/tre/
libtreが無いと言われた。
なので依存ライブラリのTREもインストール。
Fedora8で、yumやrpmでは提供されてなかったのでソースコンパイル。
# cd /usr/local/src # wget http://laurikari.net/tre/tre-0.7.5.tar.gz # cd tre-0.7.5 # ./configure # make # make install
再度msortのインストールを試みるが、次のエラーで進まない。
configure: error: LIB UTF8PROC and its header is obligatory. See http://www.flexiguided.de/publications.utf8proc.en.html
どうやらutf8procがいるらしい。これは必要そうなのでソースコンパイルで行ってみたが、
makeした共有ライブラリを/usrl/local/libに置いてもうまく認識してくれない…
しょうがないのでRPM Searchでパッケージ探してインストール。
# wget ftp://ftp.univie.ac.at/systems/linux/dag/fedora/8/en/i386/RPMS.dries/utf8proc-1.1.2-1.fc8.rf.i386.rpm # wget ftp://ftp.univie.ac.at/systems/linux/dag/fedora/8/en/i386/RPMS.dries/utf8proc-devel-1.1.2-1.fc8.rf.i386.rpm # rpm -ivh utf8proc-1.1.2-1.fc8.rf.i386.rpm # rpm -ivh utf8proc-devel-1.1.2-1.fc8.rf.i386.rpm
さらに、Uninumというパッケージもデフォルトで必要でしたが、
翻訳したら「非西洋の数体系を扱う場合に必要」という説明だったので、
無効にしてインストールしました。
# cd msort-8.50 # ./configure --disable-uninum # make # make install
これでインストールOK。
あとはマニュアル読んで使ってみるだけですね。
基本的なオプションは以下の通りとなっているようです。
-a,--algorithm <algorithm> ソートアルゴリズムの指定 -d,--field-separators <character>+ フィールドセパレータ -n,--position <POS>(,<POS>) キー位置の指定 -i,--invert-locally 降順 -1,--in <input file name> 入力ファイル -2,--out <output file name> 出力ファイル
来週、会社のPCにもインストールしてパフォーマンスを見てみようと思います。
乞うご期待!