Python, il modo più veloce per scorrere le espressioni regolari ma fermarsi alla prima corrispondenza

Question

Ho una funzione che restituisce True se una stringa corrisponde almeno a un'espressione regolare in un elenco e False in caso contrario. La funzione è chiamata abbastanza spesso che la prestazione è un problema.

Quando si esegue attraverso cProfile, la funzione sta spendendo circa il 65% di il suo tempo facendo corrispondenze e il 35% del suo tempo scorrere l'elenco.

Penso che ci sarebbe un modo di usare map() o qualcosa del genere ma non posso pensare a un modo per farlo smettere di iterare dopo aver trovato una corrispondenza.

C'è un modo per rendere la funzione più veloce mentre continua a restituire dopo aver trovato la prima corrispondenza?

def matches_pattern(str, patterns): 
    for pattern in patterns: 
     if pattern.match(str): 
      return True 
    return False 

Answer 1

La prima cosa che viene in mente sta spingendo l'anello al lato C utilizzando un generatore di espressione:

def matches_pattern(s, patterns): 
    return any(p.match(s) for p in patterns) 

Probabilmente non lo fai anche bisogno di una funzione separata per quello.

Un'altra cosa che dovresti provare è creare un regex singolo, composito usando l'operatore di alternanza |, in modo che il motore abbia la possibilità di ottimizzarlo per te. È inoltre possibile creare la regex dinamicamente da un elenco di modelli di stringa, se ciò è necessario:

def matches_pattern(s, patterns): 
    return re.match('|'.join('(?:%s)' % p for p in patterns), s) 

Naturalmente è necessario avere le espressioni regolari in forma di stringa per questo al lavoro. Basta profilare entrambi e verificare quale sia più veloce :)

Si potrebbe anche voler dare un'occhiata a general tip for debugging regular expressions in Python. Questo può anche aiutare a trovare opportunità di ottimizzazione.

UPDATE: ero curioso e ho scritto un po 'di riferimento:

import timeit 

setup = """ 
import re 
patterns = [".*abc", "123.*", "ab.*", "foo.*bar", "11010.*", "1[^o]*"]*10 
strings = ["asdabc", "123awd2", "abasdae23", "fooasdabar", "111", "11010100101", "xxxx", "eeeeee", "dddddddddddddd", "ffffff"]*10 
compiled_patterns = list(map(re.compile, patterns)) 

def matches_pattern(str, patterns): 
    for pattern in patterns: 
     if pattern.match(str): 
      return True 
    return False 

def test0(): 
    for s in strings: 
     matches_pattern(s, compiled_patterns) 

def test1(): 
    for s in strings: 
     any(p.match(s) for p in compiled_patterns) 

def test2(): 
    for s in strings: 
     re.match('|'.join('(?:%s)' % p for p in patterns), s) 

def test3(): 
    r = re.compile('|'.join('(?:%s)' % p for p in patterns)) 
    for s in strings: 
     r.match(s) 
""" 

import sys 
print(timeit.timeit("test0()", setup=setup, number=1000)) 
print(timeit.timeit("test1()", setup=setup, number=1000)) 
print(timeit.timeit("test2()", setup=setup, number=1000)) 
print(timeit.timeit("test3()", setup=setup, number=1000)) 

L'uscita sulla mia macchina:

1.4120500087738037 
1.662621021270752 
4.729579925537109 
0.1489570140838623 

Quindi any non sembra essere più veloce di quanto il tuo approccio originale . Costruire una regex anche dinamicamente non è molto veloce. Ma se riesci a creare un regex in anticipo e ad usarlo più volte, ciò potrebbe migliorare le prestazioni. Puoi anche adattare questo benchmark per testare altre opzioni :)

Answer 2

Il modo per farlo più veloce è quello di combinare tutte le regex in uno con "|" tra di loro, poi fare una regex partita chiamata. Inoltre, ti consigliamo di compilarlo una volta per essere sicuro di evitare la compilazione regex ripetuta.

Ad esempio:

def matches_pattern(s, pats): 
    pat = "|".join("(%s)" % p for p in pats) 
    return bool(re.match(pat, s)) 

Questo è per pats come stringhe, non compilato modelli. Se davvero avete solo regex compilati, quindi:

def matches_pattern(s, pats): 
    pat = "|".join("(%s)" % p.pattern for p in pats) 
    return bool(re.match(pat, s)) 

Answer 3

In aggiunta alle eccellenti risposte sopra, assicurati di confrontare l'output di re.corrisponde a Nessuno:

>>> timeit('None is None') 
0.03676295280456543 
>>> timeit('bool(None)') 
0.1125330924987793 
>>> timeit('re.match("a","abc") is None', 'import re') 
1.0200879573822021 
>>> timeit('bool(re.match("a","abc"))', 'import re') 
1.134294033050537