メモリに入りきらないデータを扱う
タイトルのように、例えば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_ALLで上書きされます。
LC_CTYPE 文字定義、大文字、小文字など。これらは toupper、tolower、islower、isdigit のような関数で用いられる。
