Python regexは文字列の空白のときに遅くなります

Question

Pythons regexモジュールを使用して文字列を一致させたいと思います。

私の場合、文字列の開始、終了、および大文字の組み合わせが "_"であることを確認したいと思います。たとえば、「MY_HERO2」という文字列が有効です。次の文字列は有効ではありません。 "_MY_HREO2"、 "MY HERO2"、 "MY_HERO2_"

が、私はこのコードを使用する文字列を検証するには：

import re 
my_string = "MY_HERO" 

p = re.compile("^([A-Z,0-9]+_??)+[A-Z,0-9]$") 
if p.match(my_string): 
    print "validated" 

をだから私の問題は何ですか？空白文字を含む長い文字列の検証は非常に遅いです。どうすればこれを避けることができますか？私のパターンは間違っていますか？この行動の理由は何ですか？事前にごanwsersと応答のための

MY_HERO2 --> 53 ms 
MY_SUPER_GREAT_UNBELIEVABLE_HERO --> 69 microseconds 
MY_SUPER_GREAT_UNBELIEVABLE HERO --> 223576 microseconds 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO --> 15 microseconds 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO --> 979429 microseconds 

ありがとう：

は、ここではいくつかの数字です。 :-) ポール

Answer 1

私の問題は何ですか？

問題はcatastrophic backtrackingです。正規表現エンジンは、多くの時間をかけてさまざまなバリエーションを試しています。

かなり単純な例でこれを試してみましょう：A_B D。

エンジンは、まず、それが今_??を試みるが、それは任意（遅延）あるので、それは今のためにそれをスキップし、これは([A-Z,0-9]+_??)+を終了した[A-Z,0-9]+とAに一致します。

今、エンジンが[A-Z,0-9]を一致させようとしますが、それが失敗し、それが最後の時間を失敗し、_??を試み、成功し([A-Z,0-9]+_??)+を再入力するようになりましたそれは、バックトラックする必要があるので、_は、文字列でもあります。

今、エンジンが再び([A-Z,0-9]+_??)+を終了し、[A-Z,0-9]を一致させようとし、それが成功し、それは終わりの文字列$を一致させようとしたが失敗し、今ではバックトラックと再び([A-Z,0-9]+_??)+に入ります。

私はそれを書くの階層ていますし、我々はそのようななど#や%、としてあなたの正規表現では受け入れられていない任意の文字がこれを引き起こします-actuallyまだを空白文字に達していないとして、これが起こっている場所を見て期待し、空白だけでなく、これは小さな小さな例ですが、長い文字列の場合は、文字列全体に一致するか失敗するまで何百回から何百回も行う必要があります。したがって、大量の時間。

空白文字を含む長い文字列の検証は非常に遅いです。

これもやはりバックトラックとバラバラのためです。

どうすればこの問題を回避できますか？

あなたが代わりにこの正規表現を使用することができます。

^([A-Z0-9]_?)*[A-Z0-9]$ 

これは文字列は、オプション_続く大文字または数字で始まる確保し、この1回以上繰り返して、だけ大文字があることを確認してください最後に数字が表示されます。

私のパターンは間違っていますか？この行動の理由は何ですか？

あなたの表現は間違いではありませんが、非常に非効率です。

([A-Z,0-9]+_??)+[A-Z,0-9]$ 
     ^^^
     You |see those two, they are a lot of trouble together 
      | 
      These two ?? with the the other two + on the inside and outside, hell :) 

Answer 2

あなたはこの単純な正規表現を使用して同じ結果を得ることができます。

import timeit 

stmt = ''' 
import re 
reg = '^(?:[A-Z0-9][A-Z0-9_]*)?[A-Z0-9]$' 
p = re.compile(reg) 
p.match('%s') 
''' 

str_list = ['MY_HERO2', 'MY_SUPER_GREAT_UNBELIEVABLE_HERO', 'MY_SUPER_GREAT_UNBELIEVABLE HERO', 'MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO', 'MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO'] 

for s in str_list: 
    t = timeit.timeit(stmt%s, number=1000) 
    print '%s: %s' % (s, t) 

import re 
reg = '^(?:[A-Z0-9][A-Z0-9_]*)?[A-Z0-9]$' 
p = re.compile(reg) 
for s in str_list: 
    result = p.match(s) is not None 
    print '%s: %s' % (s, result) 

結果：

MY_HERO2: 0.00375986099243 
MY_SUPER_GREAT_UNBELIEVABLE_HERO: 0.00417900085449 
MY_SUPER_GREAT_UNBELIEVABLE HERO: 0.00534510612488 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO: 0.00419306755066 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO: 0.00567102432251 

MY_HERO2: True 
MY_SUPER_GREAT_UNBELIEVABLE_HERO: True 
MY_SUPER_GREAT_UNBELIEVABLE HERO: False 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG_HERO: True 
MY_SUPER_GREAT_UNBELIEVABLE_STRONG HERO: False