次のコードを実行すると、永遠に時間がかかります。
"Hello there, very best wishes, from Syria...".match(/^((?:, |[\w ]+)+)$/)
次の実行中、これまでより少し時間がかかりますが、10 秒より少し長くかかります!
"Hello there, best wishes, from Syria...".match(/^((?:, |[\w ]+)+)$/)
...そして戻ってきますnull
私のUbuntu 12.04 64ビットマシン、Archlinux 32ビットサーバー、およびDebian Wheezy 32ビットサーバーで試してみました。これらはすべてノードv0.10.18を実行しています。
編集:どうやら動作は V8 から継承されているようです。同じコードで Chrome のコンソールがハングし、mongo シェル (V8 も使用) もハングします。
この正規表現は同等で、高速に実行されます。
/^([\w, ]+)$/
問題は、V8 ではなく正規表現にあります。他のエンジンは、しばらく試行した後に一致しないと報告するだけです (これは必ずしも正しい結果ではありません)。V8 は、時間がかかっても正しい結果を得ようとします。正規表現の書き方に注意する必要があります。これは他のコードと同じです。プログラマーのミスから魔法のように保護することはできません。
ここで起こっていることは、壊滅的なバックトラッキングであると確信しています。たとえば、私のマシンでは：
Hello there, best wishes, from Syria...約 13 ～ 14 秒かかります。Hello there, vbest wishes, from Syria...27 ～ 28 秒かかります。Hello there, vebest wishes, from Syria...56 秒かかります。かかる時間が指数関数的に増加することがわかります。正規表現エンジンがバックトラッキングを介して文字列に一致する方法を説明するために、上記のリンクから例を引用します。(x+x+)+ystringに正規表現を適用しますxxxxxxxxxxy。
この正規表現を xxxxxxxxxxy に適用するとどうなるか見てみましょう。最初の x+ は、10 個の x 文字すべてに一致します。2 番目の x+ は失敗します。最初の x+ は 9 つの一致に戻り、2 番目の x+ は残りの x を取得します。グループは 1 回一致しました。グループは繰り返されますが、最初の x+ で失敗します。1回の繰り返しで十分なので、グループは一致します。y は y と一致し、全体的な一致が見つかりました。正規表現が機能することが宣言され、コードが顧客に出荷され、顧客のコンピューターが爆発します。ほとんど。
対象の文字列に y がない場合、上記の正規表現は見苦しくなります。y が失敗すると、正規表現エンジンはバックトラックします。グループには、バックトラックできる反復が 1 つあります。2 番目の x+ は 1 つの x のみに一致したため、後戻りできません。しかし、最初の x+ は 1 つの x をあきらめることができます。2 番目の x+ はすぐに xx に一致します。グループは再び 1 回反復し、次の反復で失敗し、y で失敗します。再びバックトラックすると、2 番目の x+ には 1 つのバックトラック位置があり、x に一致するように縮小されます。グループは 2 回目の反復を試みます。最初の x+ は一致しますが、2 番目は文字列の最後でスタックします。再びバックトラックすると、グループの最初の繰り返しの最初の x+ は、それ自体を 7 文字に減らします。2 番目の x+ は xxx に一致します。y に失敗すると、2 番目の x+ は xx に縮小され、次に x に縮小されます。これで、グループは、各 x+ に対して 1 つの x を使用して、2 番目の反復に一致できます。しかし、この (7,1),(1,1) の組み合わせも失敗します。したがって、(6,4)、(6,2)(1,1)、(6,1)、(2,1)、(6,1)、(1,2)、そして Iドリフトを開始すると思います。
同じ例を使用している、正規表現のパフォーマンスに関する Jeff のこのページを参照してください。話の教訓: ものを一致させるだけでなく、正規表現を改善してください。繰り返し演算子をネストするときは、同じ一致に一致する方法が 1 つしかないことを絶対に確認してください。私が引用した例では、xx+yよりうまく機能します。そして、あなたの正規表現については、Esailjaが与えた答えがはるかにうまく機能します/^([\w, ]+)$/