「「無印良品」公式サイト、年末から続くメンテナンスが終わらず。再稼働は1月下旬予定」記事へのコメント

正規表現処理は実装によって大きく処理速度が異なる

[Anonymous Coward]

unixのコマンド内蔵正規表現ライブラリ、単独の正規表現ライブラリなんかでも、
同じ処理で、一瞬で処理が済んだり、フリーズしたかとおもうくらい時間がかかったりする

商用UNIXの正規表現ライブラリがクソ遅くて、
Linux(GNUのコマンド類)じゃ一瞬で動くものが、
商用UNIXではフリーズしたかの如く時間がかかるパターンとかにあったことがある

Re:正規表現処理は実装によって大きく処理速度が異なる

[taka2 (14791)]

それはたぶん、ライブラリが使ってるアルゴリズムの問題。

「正規表現のマッチング問題」は、そのまま素直に実装した場合、「*」などの繰り返しは割り当てを変えて繰り返す(バックトラック)ことになります。
そのため、パターンによってはものすごく時間がかかることになり、最悪値だと、長さnに対して O(2ⁿ) の時間が必要。

ところで、「正規表現のマッチング問題」はそのまま「非決定性有限オートマトン受理問題」に一対一対応するのですが、「非決定性有限オートマトン」は「決定性有限オートマトン」への変換が可能です。決定性の場合、バックトラック不要で、一回読み進めるだけで判定可能。処理時間はO(n)です。
そのかわり、「非決定性から決定性への変換」という事前処理が必要ですし、決定性有限オートマトンはメモリ消費がすごく大きくなります。こっちがO(2ⁿ)になる。

どちらも利点欠点がありますが、最近はメモリに困ることはないので、決定性のデメリットは薄いですね。

UNIX古来のツールでいうと、grepは非決定性で、egrepは決定性変換してる。
egrepは検索はものすごく速いけど、(オートマトンの変換で)検索開始までちょっと待たされるので、
昔は検索内容と検索量でgrepとegrepを使い分けてたりしましたが、
今は何も考えずにegrepですね。ていうかGNUはgrepもegrepも実体は同じ(オプション違い)だし。

Re:正規表現処理は実装によって大きく処理速度が異なる

[Anonymous Coward]

バックトラックについてはCloudflareの障害 [it.srad.jp]とかありましたね。
今時のスクリプトの処理系だと大抵はDFA+NFAのハイブリッド的な実装なので
かなり無頓着なパターンを書いてもクセに合わせた挙動になりますが、
コマンドや単体ライブラリを直接叩く場合はアルゴリズムを知っておかないと駄目ですね。