アカウント名:
パスワード:
unixのコマンド内蔵正規表現ライブラリ、単独の正規表現ライブラリなんかでも、同じ処理で、一瞬で処理が済んだり、フリーズしたかとおもうくらい時間がかかったりする
商用UNIXの正規表現ライブラリがクソ遅くて、Linux(GNUのコマンド類)じゃ一瞬で動くものが、商用UNIXではフリーズしたかの如く時間がかかるパターンとかにあったことがある
それはたぶん、ライブラリが使ってるアルゴリズムの問題。
「正規表現のマッチング問題」は、そのまま素直に実装した場合、「*」などの繰り返しは割り当てを変えて繰り返す(バックトラック)ことになります。そのため、パターンによってはものすごく時間がかかることになり、最悪値だと、長さnに対して O(2n) の時間が必要。
ところで、「正規表現のマッチング問題」はそのまま「非決定性有限オートマトン受理問題」に一対一対応するのですが、「非決定性有限オートマトン」は「決定性有限オートマトン」への変換が可能です。決定性の場合、バックトラック不要で、一回読み進めるだけで判定可能
バックトラックについてはCloudflareの障害 [it.srad.jp]とかありましたね。今時のスクリプトの処理系だと大抵はDFA+NFAのハイブリッド的な実装なのでかなり無頓着なパターンを書いてもクセに合わせた挙動になりますが、コマンドや単体ライブラリを直接叩く場合はアルゴリズムを知っておかないと駄目ですね。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
私はプログラマです。1040 formに私の職業としてそう書いています -- Ken Thompson
正規表現処理は実装によって大きく処理速度が異なる (スコア:0)
unixのコマンド内蔵正規表現ライブラリ、単独の正規表現ライブラリなんかでも、
同じ処理で、一瞬で処理が済んだり、フリーズしたかとおもうくらい時間がかかったりする
商用UNIXの正規表現ライブラリがクソ遅くて、
Linux(GNUのコマンド類)じゃ一瞬で動くものが、
商用UNIXではフリーズしたかの如く時間がかかるパターンとかにあったことがある
Re: (スコア:4, 興味深い)
それはたぶん、ライブラリが使ってるアルゴリズムの問題。
「正規表現のマッチング問題」は、そのまま素直に実装した場合、「*」などの繰り返しは割り当てを変えて繰り返す(バックトラック)ことになります。
そのため、パターンによってはものすごく時間がかかることになり、最悪値だと、長さnに対して O(2n) の時間が必要。
ところで、「正規表現のマッチング問題」はそのまま「非決定性有限オートマトン受理問題」に一対一対応するのですが、「非決定性有限オートマトン」は「決定性有限オートマトン」への変換が可能です。決定性の場合、バックトラック不要で、一回読み進めるだけで判定可能
Re:正規表現処理は実装によって大きく処理速度が異なる (スコア:1)
バックトラックについてはCloudflareの障害 [it.srad.jp]とかありましたね。
今時のスクリプトの処理系だと大抵はDFA+NFAのハイブリッド的な実装なので
かなり無頓着なパターンを書いてもクセに合わせた挙動になりますが、
コマンドや単体ライブラリを直接叩く場合はアルゴリズムを知っておかないと駄目ですね。