Python regex lento quando gli spazi bianchi nella stringa

Question

Mi piacerebbe abbinare le stringhe, usando il modulo regex di Pythons.

Nel mio caso, voglio verificare che le stringhe inizino, finiscano e siano costituite da lettere maiuscole unite da "_". Ad esempio, la seguente stringa è valida: "MY_HERO2". Le seguenti stringhe non sono validi: "_MY_HREO2", "MY HERO2", "MY_HERO2_"

Per convalidare una stringa che uso questo codice:

import re 
my_string = "MY_HERO" 

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

Allora, qual è il mio problema? Convalidare la stringa lunga che contiene gli spazi bianchi è molto, molto lento. Come posso evitare questo? Il mio modello è sbagliato? Qual è la ragione di questo comportamento?

Ecco alcuni numeri:

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 

Grazie per i vostri anwsers e le risposte in anticipo. :-) Paul

Answer 1

Quindi qual è il mio problema?

Il problema è catastrophic backtracking. Il motore regex sta provando un sacco di variazioni che richiedono molto tempo.

Proviamo con un esempio piuttosto semplice: A_B D.

Il motore prima corrisponde A con [A-Z,0-9]+ allora la società cerca _?? ma dal momento che è facoltativa (pigro) salta per ora, e questo ha finito ([A-Z,0-9]+_??)+.

Ora il motore cerca di abbinare [A-Z,0-9] ma c'è una _ nella stringa in modo che non riesce e ora ha bisogno di fare marcia indietro, in modo che rientra ([A-Z,0-9]+_??)+ in cui non è riuscito l'ultima volta e cerca _?? e riesce.

Ora il motore esce ([A-Z,0-9]+_??)+ di nuovo e cerca di far corrispondere [A-Z,0-9] e ci si riesce, allora si cerca di abbinare end-of-string $ ma non riesce, ora fa marcia indietro ed entra ([A-Z,0-9]+_??)+ di nuovo.

spero di vedere dove questo sta andando come sto più livelli di scriverlo e non abbiamo ancora raggiunto il carattere di spazio -actually qualsiasi carattere non accettate nella vostra espressione regolare come # o %, ecc causerà questo, non solo lo spazio bianco - e questo è un piccolo esempio, nel caso delle tue stringhe lunghe, dovrà farlo centinaia e centinaia di volte fino a quando non sarà in grado di eguagliare l'intera stringa o fallirà, quindi la grande quantità di tempo.

La convalida della stringa lunga che contiene spazi bianchi è molto, molto lenta.

Ancora una volta a causa di backtracking e inferno di variazioni.

Come posso evitare questo?

È possibile utilizzare questa espressione regolare invece:

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

Questo assicura la stringa inizia con un numero di caratteri maiuscoli o seguita eventualmente da un _, ripetere questo una o più volte e solo assicurarsi che non v'è un maiuscolo o un numero alla fine.

Il mio schema è sbagliato? Qual è la ragione di questo comportamento?

L'espressione non è sbagliata, ma è altamente inefficiente.

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

È possibile ottenere lo stesso risultato utilizzando questa semplice espressione regolare:

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) 

Risultati:

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