あいかわらずですが、でっかい int 集合を uniq したいときのもう一つの方法として、連想配列を使う方法があります。特定の値を除外したいなど、ちょっとデータを加工したいときになんかしらの言語を使うかんじです。
php だったら
(ひさしぶりの) php でやるなら、とりあえず配列のキーにいろいろ突っ込んでいって、最後まで読んだらキーのリストを眺めればいいわけですね。
<?php $tmp = array(); while ($id = get_next()) { $tmp[$a] = 1; } $uinq_list = array_keys($tmp);
けれど、やりたいことはデカい int 集合なんで、phpなんかでやってると遅そうだし、やっぱ awk だよな、と思うわけです。
awk (oawk), nawk, gawk
今回の環境は Solaris 10 (5/09) です。 awk は以下の 3 種類が入ってました。 mawk は入ってなかった。
素の awk は getline すら使えない、ほんとシンプルなものです。期待としては、oawk で書ける範囲の作業は一番速かったりしないかな? gawk は便利な代わりに遅かったりするのかな?? ってとこ。
oawk は脱落
ところがね、いきなり oawk は脱落でした。
BEGIN { for (i = 0; i < max; i++) x[i] = 1 exit }
みたいな単純なもので、配列サイズ N に対して O(N^2) の時間かかるっぽい!! max を 10,000 〜 200,000 と変化させてみて、 /usr/bin/time の real は以下のようになりました。
緑色の、ぐにゃっと曲がった線が oawk で、軸は右側の軸です! 同じ軸だとつぶれちゃうんです。oawk は実装もナイーブってことなのかなぁ...。
nawk, gawk (+php) で etime, rss を比較
ということで nawk と gawk で以下のようなスクリプト書いて(一部はしょり気味)、これに seq 30000000 を食わせ、その実行時間とメモリ使用量をみました。この数は入力の行数ではなく、最終的な uniq | wc -l の数に対応するので、もっと入力が多かったとしても多分線形になるんじゃないかと思います。
BEGIN { OFS = "\t" ps = "ps -eo fname,rss,etime | grep awk" } { x[$1] = 1 if (NR % 1000000) { ps | getline l print NR, l close(ps) } }
さらに x[$1] のぶぶんで int と string で違うのかな、と思って x["s" $1] も試してみました。
比較対象として、みんな大好きな php で以下のようなかんじ。fgets が改行付きで返してくるのを trim せずに int に cast してるとかの関係で、string 版は省略です。(この問題においてはいろいろ不利になるから)
<?php $aho = array(); while (($line = fgets(STDIN)) !== false) { $aho[$i = (int) $line] = 1; if ($i % 1000000 == 0) { echo "$i ".shell_exec('ps -eo fname,rss,etime | grep php'); } }
実行時間
結果、以下のようになりました。横軸は NR の経過で100万単位、縦軸は経過時間で秒単位です。gawk の int は str の赤い線にかぶって消えちゃってます。
多少違いはあるものの、全体としては3000万IDでも2分程度なので、入力1億行で結果が2000万〜3000万くらいなら10分もあれば終わるかな? と思ってよさそう。
いちばん速かったのは gawk(int) = gawk(str) で、対して nawk(str) が 159%, nawk(int) が 226%, php が 400% となりました。nawk で int のほうが遅いのはちょっと意外。php は「やっぱりね」って感じですが、それでも linear だし、よくがんばってると思います。ここまで来て mawk を比較してないのが悔やまれます...。
