正規表現の処理速度

職場で、先輩のロビンソンさん (仮名) が、若手のジョンくん (仮名) に、「ログファイルの中から、特定の条件に合う部分を抽出するツール」を Java で書いてみて、という指示を出していた。すでにロビンソンさん (仮名) が Perl で書いたのがあるので、それを参考にしてやってみて、ということだった。
しばしの後、ジョンくん (仮名) が僕をつついた。
「出力は正しくできるようになったんですけど、やけに時間がかかるんですよ……」


調べてみると、java.util.regex.Matcher#find() で時間がかかっている模様。これを matches() にすると、一気に時間が短縮された。
その日はそれで話が終わったのだけど、find() ってそんなに重いのだろうか? 気になって、もうちょっと確認してみることにした。

ふむ

ロビンソンさん (仮名) の Perl 版では、正規表現がだいたいこんな感じになっていた。

^([0-9/]+) ([0-9:]+) (.+Foo) (.+)$

ジョンくん (仮名) は、これを流用して Java 版を作っていたんだけど、コピーする時に、'^' と '$' を消してしまっていたのだった。
'^' と '$' をつけて試してみると、find() でも matches() とだいたい同じくらいの時間で終わってくれる。

ふむふむ

ついでに、いくつかのパターンで試してみた (Java 1.4 で、find() 使用)。

正規表現 処理時間
([0-9/]+) ([0-9:]+) (.+Foo) (.+) 6407
^([0-9/]+) ([0-9:]+) (.+Foo) (.+)$ 1016
(\d{4}/\d{2}/\d{2}) (\d{2}:\d{2}:\d{2}) (.+Foo) (.+) 1360
(\d\d\d\d/\d\d/\d\d) (\d\d:\d\d:\d\d) (.+Foo) (.+) 1250
(2007/\d\d/\d\d) (\d\d:\d\d:\d\d) (.+Foo) (.+) 1150
^(2007/\d\d/\d\d) (\d\d:\d\d:\d\d) (.+Foo) (.+)$ 922

曖昧さが減れば減るほど、マッチングも早くなる。なるほど、そりゃそうか。一番上のが遅いのは、最初の 2 つのグループ (年月日と時分秒) が似ているあたりが原因かな……? (あてずっぽう)