regex '|' operatore vs esecuzioni separate per ogni sottoespressione

Question

Ho una stringa abbastanza grande (~ 700k) rispetto alla quale ho bisogno di eseguire 10 regex e contare tutte le corrispondenze di qualsiasi regex. Il mio impl veloce e sporco doveva fare qualcosa come re.search ('(expr1) | (expr2) | ...'), ma mi stavo chiedendo se avremmo visto qualche guadagno in termini di prestazioni confrontando in un ciclo invece:

In altre parole, voglio mettere a confronto le prestazioni di:

def CountMatchesInBigstring(bigstring, my_regexes): 
    """Counts how many of the expressions in my_regexes match bigstring.""" 
    count = 0 
    combined_expr = '|'.join(['(%s)' % r for r in my_regexes]) 
    matches = re.search(combined_expr, bigstring) 
    if matches: 
    count += NumMatches(matches) 
    return count 

vs

def CountMatchesInBigstring(bigstring, my_regexes): 
    """Counts how many of the expressions in my_regexes match bigstring.""" 
    count = 0 
    for reg in my_regexes: 
    matches = re.search(reg, bigstring) 
    if matches: 
     count += NumMatches(matches) 
    return count 

smetto di essere pigro ed eseguire alcuni test di domani (e dopo i risultati), ma mi chiesi se la risposta salterà a qualcuno che in realtà capisce come funzionano le regex :)

Answer 1

Sospetto che la regex faccia anche ciò che si sta tentando di fare ... solo molto meglio :)

quindi il "|" vincerebbe

Answer 2

Le due cose daranno risultati leggermente diversi, a meno che non sia garantito che una corrispondenza corrisponda a una e una sola regex. Altrimenti se qualcosa corrisponde a 2 verrà contato due volte.

In teoria, la soluzione deve essere più rapida (se l'espressione si escludono a vicenda) perché il compilatore regex dovrebbe essere in grado di creare una macchina dello stato di ricerca più efficiente, quindi è necessario un solo passaggio. Mi aspetto che la differenza sia piccola, a meno che le espressioni non siano molto simili.

Inoltre, se si trattasse di una stringa enorme (più grande di 700k), potrebbero esserci dei guadagni dal fare un passaggio, e quindi sarebbe necessario un minor numero di scambi di memoria (su disco o cache della cpu).

La mia scommessa è nei tuoi test, ma non è davvero evidente. Sono interessato al risultato effettivo - per favore pubblica i risultati.

Answer 3

Sono d'accordo con amartynov ma volevo aggiungere che si potrebbe anche prendere in considerazione la compilazione della regex prima (re.compile()), esp. nella seconda variante, come in questo caso, potresti risparmiare un po 'di tempo di configurazione nel ciclo. Forse puoi misurare anche tu mentre ci sei.

Il motivo per cui penso che l'unico scatto funzioni meglio è che presumo che sia completamente eseguito nello spazio C e non tanto il codice Python deve essere interpretato.

Ma non vedo l'ora dei numeri.

Answer 4

Una singola compilazione e ricerca dovrebbe produrre risultati più rapidi, su una scala inferiore di espressioni il guadagno potrebbe essere trascurabile ma più si corre attraverso il guadagno maggiore. Pensalo come compilando una volta e confrontando vs compilando 10 volte e corrispondenti.

Answer 5

Credo che la vostra prima implementazione sarà più veloce:

• Uno dei principi fondamentali per le prestazioni Python è "logica passare al livello C" - che significa funzioni incorporate (scritto in C) sono più veloci rispetto alle implementazioni di puro Python. Quindi, quando il loop viene eseguito dal modulo Regex integrato, dovrebbe essere più veloce
• Una espressione regolare può cercare più pattens in un passaggio, il che significa che deve solo scorrere il contenuto del file una volta, mentre più regex avrà leggere l'intero file più volte.

Answer 6

Per capire come funziona il modulo re - compila _sre.c in modalità debug (metti #define VERBOSE a 103 righe in _sre.c e ricompila python). Dopo questo si ammala vedere qualcosa di simile:

 

>>> import re 
>>> p = re.compile('(a)|(b)|(c)') 
>>> p.search('a'); print '\n\n'; p.search('b') 
|0xb7f9ab10|(nil)|SEARCH 
prefix = (nil) 0 0 
charset = (nil) 
|0xb7f9ab1a|0xb7fb75f4|SEARCH 
|0xb7f9ab1a|0xb7fb75f4|ENTER 
allocating sre_match_context in 0 (32) 
allocate/grow stack 1064 
|0xb7f9ab1c|0xb7fb75f4|BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab20|0xb7fb75f4|MARK 0 
|0xb7f9ab24|0xb7fb75f4|LITERAL 97 
|0xb7f9ab28|0xb7fb75f5|MARK 1 
|0xb7f9ab2c|0xb7fb75f5|JUMP 20 
|0xb7f9ab56|0xb7fb75f5|SUCCESS 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab1c|0xb7fb75f4|JUMP_BRANCH 
discard data from 0 (32) 
|0xb7f9ab10|0xb7fb75f5|END 




|0xb7f9ab10|(nil)|SEARCH 
prefix = (nil) 0 0 
charset = (nil) 
|0xb7f9ab1a|0xb7fb7614|SEARCH 
|0xb7f9ab1a|0xb7fb7614|ENTER 
allocating sre_match_context in 0 (32) 
allocate/grow stack 1064 
|0xb7f9ab1c|0xb7fb7614|BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab20|0xb7fb7614|MARK 0 
|0xb7f9ab24|0xb7fb7614|LITERAL 97 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab1c|0xb7fb7614|JUMP_BRANCH 
allocating sre_match_context in 32 (32) 
|0xb7f9ab32|0xb7fb7614|MARK 2 
|0xb7f9ab36|0xb7fb7614|LITERAL 98 
|0xb7f9ab3a|0xb7fb7615|MARK 3 
|0xb7f9ab3e|0xb7fb7615|JUMP 11 
|0xb7f9ab56|0xb7fb7615|SUCCESS 
discard data from 32 (32) 
looking up sre_match_context at 0 
|0xb7f9ab2e|0xb7fb7614|JUMP_BRANCH 
discard data from 0 (32) 
|0xb7f9ab10|0xb7fb7615|END 

>>>          
 

Answer 7

Il meno passa la meglio: Sarà sufficiente utilizzare più memoria, che non è in genere un problema.

Se qualcosa può essere lasciato all'interprete da gestire, troverà sempre una soluzione più veloce (sia in tempo per implementare che tempo per l'esecuzione) che la tipica controparte umana.