2007-05-26

眠い・・・

最近寝過ぎだと思います。8時間は絶対寝てるもんなー。
もうちょい工夫しよう。

2007-05-24

メモリに入りきらないデータを扱う

タイトルのように、例えばWebデータを扱ってそこに出現する単語の頻度をカウントするような場合、どうするのが一番手軽で楽なんでしょうというお話。

勿論、多分ほとんどの人は知っていて、常識なのかもしれませんが、僕は最近気づきました。
まず、対象となる単語（研究によって異なるでしょう）だけを行単位で全部書き出します。

aaa
bbb
ccc

みたいに。
この時データ量があまりに多い場合複数ファイルに書き出した方が楽かもしれません。

その後は、単一ファイルの場合、

sort -S 500M | uniq -c | sort -nr -S 500M

で終わりです。

複数ファイルの場合は、全てのファイルをソートした後に、

sort -m -S 500M *.sort(ソート済みファイル) > merge.txt
uniq -c merge.txt > count.txt
sort -nr -S 500M count.txt > result.txt

だけでした。
sort の-Sオプションはこれだけのメモリに収めてくださいということです。
-mオプションでマージしながらソートしてくれます。
ちなみにマージソートの場合は、メモリをあまり使わなくてもファイルを上手く利用してソートが可能です。

そんなこんなで最近知ったトリビア。
クイックソートは実はマージソートよりも遅いです。
だから、C言語の標準ライブラリにあるqsortは内部でマージソートを利用しています。
（以前はクイックソート）

ちなみに計算量はどちらもO(nlogn)になります。

いろいろ考えて、自分でマージソートを実装するのが面倒だ…と思っていたときにUNIXコマンドにあることを思い出した俺は…orz

2007/07/20 追記：
Linuxなどで上記のコマンドを行った場合、LANGやLC_ALLの言語環境に影響を受けるようです。
（詳しくは調べていません。ただこの部分ではまりました。）
EUC-JPのテキストをja_JP.UTF-8の環境で行うと時間が通常の10倍以上かかり、おかしな結果になりました。
上手くいかない場合は、LANGUAGE=C(これはメッセージなので関係ないと思うけど）やLC_ALL=C、LANG=Cとして再度試してみてください。
おそらく、



LC_COLLATE 並べかえ(ソート)の順番を設定する

もしくは



LC_CTYPE　文字定義、大文字、小文字など。これらは toupper、tolower、islower、isdigit のような関数で用いられる。

この辺が原因。LC_ALLで上書きされます。

2007-05-02

CppUnitを使え！

あとで追記予定。

2007-05-02

autoconfとautomakeを使え！

えっと、autoconfとautomakeは研究用のプログラム書く時でも、ちょっとした処理を書く時でも、かなり便利です。
便利でした。
もっと前から知っていれば…。というか、怖がって手を出せないでいただけですが…。

３年前までは情報もあまりなかったけれども最近Web上にも日本語情報があふれているので最近チャレンジ。
手順はこのあたりかな？
http://www.saiin.net/~silphire/tips/autoconf.html

autoscan (/usr/autotool/devel/bin/autoscan)
mv configure.scan configure.in
configure.in、Makefile.amを書く。
autoheader
aclocal
touch NEWS README AUTHORS ChangeLog
automake -a
autoconf
./configure; make; make install

これだけで、ソースの追加も自由自在です。手書きでMakefileを書かなくていいってなんて素敵なんだ！

2007-05-02

strchrとC++ stringのfindの速度差

find

void find(std::string &a) {

    for(int k = 0; k < 1000; k++){
        a.find('b');
    }

}

int main(void){
    std::string a;
    a.reserve(10000000);

    for(int j = 0; j < 1000; j++){
        for(int i = 0; i < 10000; i++){
            a[i + j * 10000] = 'a';
        }
        a[j * 10000] = 'b';
    }

    for(int l = 0; l < 1000; l++){
      find(a);
    }
}

strchr

void find(const char* a) {

    for(int k = 0; k < 1000; k++){
        strchr(a, 'b');
    }

}

int main(void){
    char *str;
    str = (char *) malloc(sizeof(char)*10000000);
    str[1] = 'b';

    for(int j = 0; j < 1000; j++){
        for(int i = 0; i < 10000; i++){
            str[i + j * 10000] = 'a';
        }
       str[j * 10000] = 'b';
    }
    for(int l = 0; l < 1000; l++){
      find(str);
    }
    free(str);
}

で速度比較を行った。

  strchr
  real    0m0.133s
  user    0m0.111s
  sys     0m0.021s

  find
  real    0m0.192s
  user    0m0.173s
  sys     0m0.019s

だいたい1.5倍かな？　
ただ、文字列の構築に時間がかかっている可能性もあるので、一概に比較できないのが残念なところ。
プロファイラを取ったんだが、macだとC++のシンボル名がデマングルされないみたいです。
これ、なんとかできないかなぁ？
ちなみにコンパイラはどちらもg++で、最適化オプションはなしです。