Implementación más rápida para hacer varias sustituciones de cadenas en Python

¿Hay alguna manera recomendada de hacer varias sustituciones de cadenas que no sea 'reemplazar' el encadenamiento en una cadena (es decir, text.replace (a, b) .replace (c, d). reemplazar (e, f) ...)? ¿Cómo podría, por ejemplo, implementar una función rápida que se comporte como las llamadas htmlspecialchars de PHP en Python?Implementación más rápida para hacer varias sustituciones de cadenas en Python

Comparé (1) el método múltiple de 'reemplazar', (2) el método de expresión regular y (3) el método de Matt Anderson.

con n = 10 carreras, llegaron los resultados como sigue:

en 100 caracteres:

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

En 1000 caracteres:

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

En 10.000 caracteres:

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

Encendido 100000 personajes:

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

En 1,000,000 caracteres:

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

En 3,687,809 caracteres:

 
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) ]

así que felicitaciones a Matt para vencer el método de múltiples 'reemplazar' en una cadena de entrada bastante grande .

¿Alguien tiene ideas para golpearlo en una cuerda más pequeña?

Fuente

2010-08-05 OTZ

Buena discusión aquí http://stackoverflow.com/questions/3367809/efficiently-carry-out-multiple-string-replacements-how-to-create-lookup-table –

Tim, único comentario útil en la página es uno por Alex. Él da un ejemplo para el método de sustitución lineal de la expresión regular que he verificado que es más lento en un documento de tamaño de 3.5M con 5 pares de sustitución. Entonces no me da una nueva idea. – OTZ

¿Necesita que el resultado de la primera sustitución esté disponible para participar en la siguiente sustitución (como lo haría en su ejemplo de cambio de cadena)? ¿O desea que todas las sustituciones operen únicamente en el texto original? Si es lo último, ¿tiene algo en mente sobre cómo priorizarlos si la superposición o de lo contrario entran en conflicto? –

método Normalmente, .replace vence a todos los otros métodos. (Vea mis puntos de referencia arriba.)

Fuente

2010-08-30 10:14:05 OTZ

¿Qué tan rápido? Además, ¿qué tan grandes son tus cuerdas?

Hay un recipe bastante simple para construir una expresión regular para hacer el trabajo en otro sitio. Puede necesitar algunos ajustes para manejar metacaracteres de expresiones regulares; No miré muy de cerca.

Si eso no es lo suficientemente bueno, es probable que necesites escribir un código C, sinceramente. Puede construir una máquina de estado simple para hacer todos los reemplazos, y luego procesar cualquier byte de cadena por byte sin retroceder a lo largo de la máquina para realmente hacer el trabajo. Sin embargo, dudo que venzas al motor de expresiones regulares sin ir a C y optimizando eso.

Fuente

2010-08-05 01:02:06

"¿Qué tan rápido?" - al menos más rápido que el método de reemplazo de encadenamiento anterior. "qué tan grande" - hasta lo que permite la memoria RAM del sistema menos el espacio de memoria que usaría la 'función'. No estoy hablando de una cadena gigantesca de, por ejemplo, tamaño 4GiB. – OTZ

Basado en mi experimento con un tamaño de 3.5M de una cadena con 5 pares de sustitución, el método de expresión regular * siempre * tiene un peor rendimiento (1.285878 seg frente a 1.341442 seg), incluso con el almacenamiento en caché del objeto re resultante. Si aumento el número de pares de sustitución, la situación podría revertirse. Pero en condiciones normales, simplemente no sucede. Entonces, el método de expresión regular lineal en la receta en este caso no es utilizable. Mis pruebas fueron una versión más eficiente de eso, en realidad. – OTZ

Sí, ese método no es tan bueno. Con un poco de suerte, veremos una mejor respuesta pronto. Si no, puedo ver si la implementación de una máquina de estado en la parte superior de la interfaz de búfer de Python funciona mejor. –

¿Algo como el siguiente quizás? Divida el texto en partes con el primer elemento "de" que se va a reemplazar, luego divida recursivamente cada una de esas partes en subpartes con el siguiente elemento "de" que se va a reemplazar, y así sucesivamente, hasta que haya visitado todas sus sustituciones . Luego únete con el ítem de reemplazo "a" para cada función recursiva completa.

Tal vez un poco difícil de entender el siguiente código (fue para mí, y lo escribí), pero parece funcionar como se esperaba. No lo comparé, pero sospecho que sería razonablemente rápido.

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')

para:

barbarfoobarmoopmoop

Fuente

2010-08-05 05:26:02

Matt, gracias por la función. El método de "reemplazar" es mucho más rápido en una cadena más pequeña (cadenas <1M más o menos). He agregado los resultados de mi prueba a mi pregunta original. Quizás quieras revisarlo. – OTZ

Implementación más rápida para hacer varias sustituciones de cadenas en Python

Respuesta

Cuestiones relacionadas