Implementazione più rapida per eseguire più sostituzioni di stringhe in Python

Question

Esiste un modo consigliato di eseguire più sostituzioni di stringhe oltre a fare "sostituisci" concatenamento su una stringa (ad es. Text.replace (a, b) .replace (c, d). sostituire (e, f) ...)? Come implementeresti, ad esempio, una funzione veloce che si comporta come htmlspecialchars di PHP in Python?

Ho confrontato (1) più metodo "replace", (2) il metodo di espressione regolare e (3) il metodo di Matt Anderson.

con n = 10 prove, il risultato è venuto nel modo seguente:

su 100 caratteri:

 
TIME: 0 ms [ replace_method(str) ] 
TIME: 5 ms [ regular_expression_method(str, dict) ] 
TIME: 1 ms [ matts_multi_replace_method(list, str) ] 

su 1000 caratteri:

 
TIME: 0 ms [ replace_method(str) ] 
TIME: 3 ms [ regular_expression_method(str, dict) ] 
TIME: 2 ms [ matts_multi_replace_method(list, str) ] 

On 10000 caratteri:

 
TIME: 3 ms [ replace_method(str) ] 
TIME: 7 ms [ regular_expression_method(str, dict) ] 
TIME: 5 ms [ matts_multi_replace_method(list, str) ] 

Acceso 100000 personaggi:

 
TIME: 36 ms [ replace_method(str) ] 
TIME: 46 ms [ regular_expression_method(str, dict) ] 
TIME: 39 ms [ matts_multi_replace_method(list, str) ] 

On 1000000 personaggi:

 
TIME: 318 ms [ replace_method(str) ] 
TIME: 360 ms [ regular_expression_method(str, dict) ] 
TIME: 320 ms [ matts_multi_replace_method(list, str) ] 

Su 3.687.809 caratteri:

 
TIME: 1.277524 sec [ replace_method(str) ] 
TIME: 1.290590 sec [ regular_expression_method(str, dict) ] 
TIME: 1.116601 sec [ matts_multi_replace_method(list, str) ] 

quindi complimenti a Matt per battere il metodo più 'sostituire' su un gran stringa di input .

Qualcuno ha idee per batterlo su una stringa più piccola?

Answer 1

metodo Normalmente, .Sostituire batte tutti gli altri metodi. (Vedi i miei benchmark sopra.

Answer 2

Quanto veloce? Inoltre, quanto sono grandi le tue corde?

C'è un semplice recipe per la creazione di un'espressione regolare per eseguire il lavoro su un altro sito. Potrebbe essere necessario qualche ritocco per gestire i metacaratteri regex; Non ho guardato troppo da vicino.

Se ciò non è abbastanza, probabilmente è necessario scrivere un codice C, onestamente. È possibile creare una macchina a stati semplice per eseguire tutte le sostituzioni e quindi elaborare qualsiasi stringa byte per byte senza eseguire il backtracking lungo la macchina per eseguire effettivamente il lavoro. Tuttavia, dubito che batterai il motore regex senza andare a C e ottimizzandolo.

Answer 3

Qualcosa come il seguente, forse? Suddividi il testo in pezzi con il primo oggetto "da" da sostituire, quindi dividi ricorsivamente ciascuna di queste parti in sotto-parti con il successivo oggetto "da" da sostituire, e così via, finché non avrai visitato tutte le tue sostituzioni . Quindi unire con l'elemento di sostituzione "a" per ciascuno come completa la funzione ricorsiva.

Un po 'difficile da avvolgere la testa sul seguente codice forse (era per me, e l'ho scritto), ma sembra funzionare come previsto. Non ho fatto un benchmark, ma ho il sospetto che sarebbe ragionevolmente veloce.

def multi_replace(pairs, text): 
    stack = list(pairs) 
    stack.reverse() 
    def replace(stack, parts): 
     if not stack: 
      return parts 
     # copy the stack so I don't disturb parallel recursions 
     stack = list(stack) 
     from_, to = stack.pop() 
     #print 'split (%r=>%r)' % (from_, to), parts 
     split_parts = [replace(stack, part.split(from_)) for part in parts] 
     parts = [to.join(split_subparts) for split_subparts in split_parts] 
     #print 'join (%r=>%r)' % (from_, to), parts 
     return parts 
    return replace(stack, [text])[0] 


print multi_replace(
    [('foo', 'bar'), ('baaz', 'foo'), ('quux', 'moop')], 
    'foobarbaazfooquuxquux') 

Per:

barbarfoobarmoopmoop