Powtórzenie języka Python powolne, gdy spacje w ciągach znaków

Question

Chciałbym dopasować ciągi znaków, używając modułu regex Pythons.

W moim przypadku chcę sprawdzić, czy ciągi rozpoczynają się, kończą i składają się z wielkich liter połączonych przez "_". Jako przykład można podać następujący ciąg: "MY_HERO2". Następujące ciągi nie są ważne: "_MY_HREO2", "MY HERO2", "MY_HERO2_"

Aby sprawdzić poprawność ciąg używam tego kodu:

import re 
my_string = "MY_HERO" 

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

Więc jaki jest mój problem? Sprawdzanie poprawności długich ciągów zawierających białe spacje jest bardzo, bardzo powolne. Jak mogę tego uniknąć? Czy mój wzorzec jest zły? Jaki jest powód takiego zachowania?

Oto niektóre numery:

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 

Dzięki za anwsers i odpowiedzi wyprzedzeniem. :-) Paul

Answer 1

Jaki jest mój problem?

Problem dotyczy catastrophic backtracking. Silnik regex próbuje całej gamy wariacji, co zajmuje dużo czasu.

Spróbujmy tego na całkiem prostym przykładzie: A_B D.

Silnik pierwsze mecze A z [A-Z,0-9]+ to teraz próbuje _?? ale ponieważ jest to opcja (leniwy) pomija go teraz, a ten zakończył ([A-Z,0-9]+_??)+.

Teraz silnik próbuje dopasować [A-Z,0-9] ale jest _ w łańcuchu więc nie powiedzie się i teraz musi wracać, więc ponownie wkracza ([A-Z,0-9]+_??)+ gdzie nie udało się po raz ostatni i próbuje _?? i uda.

Teraz silnik wychodzi ([A-Z,0-9]+_??)+ ponownie i próbuje dopasować [A-Z,0-9] i to się uda, to próbuje dopasować end-of-ciąg $ ale nie powiedzie się, teraz to cofa się i wchodzi ([A-Z,0-9]+_??)+ ponownie.

Mam nadzieję, że widać, gdzie to będzie jak ja warstwowych z pisania i nie osiągnęły jeszcze znak spacji -actually dowolny znak nie są akceptowane w regex takich jak # lub % itp spowoduje to, nie tylko biały znak - i jest to mały mały przykład, w przypadku twoich długich łańcuchów, będzie musiał to zrobić setki razy, aż będzie w stanie dopasować cały ciąg lub zawodzi, stąd ogromna ilość czas.

Walidacja długiego łańcucha zawierającego białe spacje jest bardzo, bardzo powolna.

Znów to ze względu na cofanie i piekło zmian.

Jak mogę tego uniknąć?

Można użyć tej regex zamiast:

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

Gwarantuje ciąg rozpoczyna się od wielkiej litery lub liczby, a następnie opcjonalnie _ powtórzyć to raz lub kilka razy i po prostu upewnij się, że jest wielką lub numer na końcu.

Czy mój wzór jest nieprawidłowy? Jaki jest powód takiego zachowania?

Twoje wyrażenie nie jest złe, ale jest wysoce nieefektywne.

([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

Można osiągnąć ten sam efekt za pomocą tego prostego wyrażenia regularnego:

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) 

wyniki:

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