grepでOR検索の高速化

シェル芸提唱者上田さんの著書でシェル芸本第2弾ですが、この本に関する記事です。

b.ueda.tech

この本の5章は、大きなデータを処理するというテーマ。その中でシェルのバックグラウンド処理機能を使い、並列処理で高速化を図る記載がある。ボトルネックになる高負荷なプロセスがある場合は、並列処理させる方が高速化出来るということ。

また、ファイルがキャッシュにのった場合は、複数のプロセスから同時に読み込みが出来る。ということで、ちょっとgrepを使った並列処理のネタを思いついた。テスト環境はいつものようにMac + Homebrewでインストールした最新GNU grep (ggrep)。

扱うデータは、シェル芸界隈で使われる下記のような1億行4GBのテキストデータ。値の意味は特に無くてランダムなデータのようだ。

$ ls -l TESTDATA
-r--r--r--  1 papiro  staff  4243427895  4  6 13:54 TESTDATA

$ wc -l TESTDATA
 100000000 TESTDATA

$ head TESTDATA
2377 高知県 -9,987,759 2001年1月5日
2910 鹿児島県 5,689,492 1992年5月6日
8458 大分県 1,099,824 2010年2月22日
1522 秋田県 -4,497,866 1991年2月23日
5855 新潟県 5,721,468 2001年2月28日
1934 大分県 6,120,180 1992年2月14日
8106 高知県 -8,281,463 2005年5月15日
1735 千葉県 9,122,213 2010年3月15日
4849 兵庫県 -2,773,561 2007年3月28日
1518 和歌山県 -988,312 2008年12月7日

まずはファイルをメモリキャッシュに乗せる。

$ time cat TESTDATA > /dev/null

real   0m50.279s
user   0m0.025s
sys    0m2.000s

ちなみに最新版GNU grepは超高速であり、簡単な検索なら1億行を4秒足らずでさばいてしまう。

$ time ggrep 佐賀県 TESTDATA > /dev/null

real   0m3.716s
user   0m2.935s
sys    0m0.728s

お題

＜＜＜佐賀県、福岡県、長崎県、大分県の4県分のデータを取り出す＞＞＞

OR検索になるので、パイプをつないで絞り込むことは出来ない（よね？）。

拡張正規表現を使う

grepの拡張正規表現を使う方法。まあ普通はこちらを思いつくかな？grepの拡張正規表現を使ってこんな感じ。

$ time ggrep -E '(佐賀県|福岡県|長崎県|大分県)' TESTDATA > /dev/null

real   0m21.729s
user   0m20.908s
sys    0m0.792s

あれあれ、かなり処理速度が落ちてしまう。拡張正規表現でOR検索すると、速度低下の影響が大きいようだ。

バックグラウンドによる並列処理

ではせっかくのマルチコアマルチスレッドを活用するために、シェルのバックグラウンド機能を使う。

$ time {
>  ggrep 佐賀県 TESTDATA &\
>  ggrep 福岡県 TESTDATA &\
>  ggrep 長崎県 TESTDATA &\
>  ggrep 大分県 TESTDATA &\
>  wait
> } > /dev/null
[1] 2876
[2] 2877
[3] 2878
[4] 2879
[1]   Done                    ggrep 佐賀県 TESTDATA
[4]+  Done                    ggrep 大分県 TESTDATA
[2]-  Done                    ggrep 福岡県 TESTDATA
[3]+  Done                    ggrep 長崎県 TESTDATA

real   0m5.372s
user   0m14.390s
sys    0m4.190s

マルチコアが生かされて高速に処理が出来た。出力結果は順番が狂っていると思うが、とにかく絞り込むだけならこちらの方法が圧倒的に早くなる。

ちなみに改行せずに書くなら、下記のような書き方に。{}カッコの場合は最後を;で終わらないといけないので注意。()カッコの場合は、サブシェルで動いている。

$ time { ggrep 佐賀県 TESTDATA & ggrep 福岡県 TESTDATA & ggrep 長崎県 TESTDATA & ggrep 大分県 TESTDATA & wait; } > /dev/null

$ time ( ggrep 佐賀県 TESTDATA & ggrep 福岡県 TESTDATA & ggrep 長崎県 TESTDATA & ggrep 大分県 TESTDATA & wait ) > /dev/null

まとめ

grepの拡張正規表現を使ったOR検索は処理速度低下が大きい
マルチコアなら簡単なgrep検索をバックグラウンドで並列処理すれば早い

参考

Twitterでこんなコメントいただいた。あああ、確かにね。

固定文字列だけの検索なら「fgrep $'佐賀県\n福岡県\n長崎県\n大分県' TESTDAT」なんてのも良いかも。

grepでOR検索の高速化 - 日々之迷歩 http://t.co/FVwchxqLs2
— ゾンビプログラマ (@qeMkDrlaJwLLcQ) 2015年6月9日

実験結果はこちら。正規表現を使わず固定文字列ならこれが早い。

$ time echo -e '佐賀県\n福岡県\n長崎県\n大分県' |\
> ggrep -F -f - TESTDATA > /dev/null
real   0m5.699s
user   0m4.896s
sys    0m0.776s