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
なので現在は以下のようなシェルを作成してソートしてます。

  1. 引数で受けとったキーで、先頭に置き換えるようにテキストのレイアウトを変更。
  2. sort実行。
  3. 引数で受け取ったキーから、元のレイアウトに戻す。


ただ、やはり余計な処理が入っているので自分的には不満…
オープンソースか何かでソート処理無いかなーと探していたところ、
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で、yumrpmでは提供されてなかったのでソースコンパイル

# 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にもインストールしてパフォーマンスを見てみようと思います。
乞うご期待!