Manipulación de cadenas frente a Regexps

Question

A menudo nos dicen que las Regexps son lentas y deben evitarse siempre que sea posible.

Sin embargo, teniendo en cuenta la sobrecarga de hacer un poco de manipulación de cadenas a uno mismo ( no estamos hablando de errores algoritmo - esto es un asunto diferente), especialmente en PHP o Perl (tal vez Java) ¿cuál es la límite, en ¿En qué caso podemos considerar la manipulación de cuerdas como una mejor alternativa? ¿Qué expresiones regulares son particularmente codiciosas para la CPU?

Por ejemplo, para el siguiente, en C++, Java, PHP o Perl, ¿Qué le recomendaría

Las expresiones regulares, probablemente sería más rápido:

• s/abc/def/g o una solución basada ... while((i=index("abc",$x)>=0) ...$y .= substr()...?
• s/(\d)+/N/g o un algoritmo de exploración

Pero ¿qué pasa con

• una validación de expresiones regulares de correo electrónico?
• s/((0|\w)+?[xy]*[^xy]){2,7}/u/g

no habría hecho a mano y un algoritmo específico de ser más rápido (más de tiempo para escribir)?

edición

El punto de la cuestión es determinar qué tipo de expresión regular mejor sería volver a escribir específicamente para un problema dado a través de la manipulación de cadenas?

Edit2

Una aplicación común es la expresión regular Perl. Por ejemplo, en Perl, que requiere saber cómo se implementan, ¿qué tipo de regexp se debe evitar, porque la implementación hará que el proceso sea largo e ineficaz? Puede que no sea una expresión regular compleja ...

edición de julio de 2011 (basado en los comentarios)

No estoy diciendo que todas las expresiones regulares son lentos. Se sabe que algunos patrones de expresiones regulares particulares son lentos, debido a su procesamiento particular y debido a su implementación.
En las implementaciones recientes de Perl/PHP, por ejemplo, lo que se sabe que es bastante lento, ¿y debería evitarse?
Se espera la respuesta de personas que ya hicieron su propia investigación (profiler ...) y que pueden proporcionar un tipo de pautas generales sobre lo que se recomienda/evitar.

Answer 1

Una buena característica de manipular texto con expresiones regulares es que los patrones son de alto nivel y declarativos. Esto deja a la implementación un espacio considerable para la optimización, como factorizar el prefijo común más largo o usar Boyer-Moore para cadenas estáticas. La notación concisa hace que los expertos lean más rápidamente. Entiendo lo que de inmediato

if (s/^(.)//) { 
    ... 
} 

está haciendo, y index($_, 0, 1) = "" parece ruidoso en comparación.

En lugar del límite inferior, la consideración importante para las expresiones regulares es límite superior. Es una herramienta poderosa, por lo que las personas creen que es capaz de extraer correctamente tokens de XML, direcciones de correo electrónico o programas C++ y no se dan cuenta de que es necesaria una herramienta aún más poderosa, como un analizador sintáctico.

Answer 2

¿Quién dijo que las expresiones regulares eran lentas? Al menos en Perl, tienden a ser el método preferido para manipular cadenas.

Las expresiones regulares son malas en algunos aspectos, como la validación del correo electrónico porque el tema es demasiado complejo, no porque sea lento. A proper email validation regex tiene más de 6.000 caracteres de longitud, y ni siquiera maneja todos los casos (primero debe quitar los comentarios).

Al menos en Perl 5, si tiene una gramática, probablemente no se debería analizar con una expresión regular.

También debe volver a escribir una expresión regular como función personalizada si la expresión regular ha crecido hasta el punto en que ya no se puede mantener fácilmente (consulte el ejemplo anterior de validación de correo electrónico) o si muestra que la expresión regular es el componente lento de su código .

Parece preocupado por la velocidad de la expresión regular frente al algoritmo personalizado, pero eso no es una preocupación válida hasta que demuestre que es con un generador de perfiles. Escribe el código de la manera más fácil de mantener. Si una expresión regular es clara, utiliza una expresión regular. Si un algoritmo personalizado es claro, entonces use un algoritmo personalizado. Si descubre que está consumiendo mucho tiempo después de crear un perfil de su código, comience a buscar alternativas.

Answer 3

Las expresiones regulares nunca serán más rápidas que un algoritmo hecho a mano para un propósito muy específico. Peor aún, en PHP deben compilarse la primera vez que se usan (una caché se usa luego).

Sin embargo, son ciertamente más concisos. Además, la escritura de algoritmos personalizados suele ser más lenta que las expresiones regulares porque el motor de expresiones regulares suele implementarse en un lenguaje de bajo nivel, con menos sobrecarga en las funciones de llamada, etc.

Por ejemplo, preg_replace('/a/', 'b', $string) es casi seguro más rápido que el bucle PHP a través de la cadena. Pero esto es una penalización constante en el tiempo de ejecución y, a veces, las expresiones regulares, debido al retroceso, pueden tener un comportamiento asintótico mucho peor.

Se le recomienda encarecidamente saber cómo se implementan las expresiones regulares para que pueda saber cuándo está escribiendo las ineficientes.

Answer 4

Regexes no son lentos. Pero la implementación puede ser lenta, principalmente porque a menudo se interpreta y se vuelve a compilar cada vez que se usan. Pero una buena biblioteca de expresiones regulares le permite usar versiones compiladas. Ellos son bastante rápidos.

Answer 5

Algunas expresiones regulares son extremadamente rápidas y la diferencia entre la expresión regular y una solución personalizada puede ser insignificante (o no vale la pena molestar a nadie).

Los casos donde las expresiones regulares son lentas, sin embargo, es cuando excessive backtracking occurs. Las expresiones regulares se analizan de izquierda a derecha y tienen el potencial de hacer coincidir el texto en más de una forma. Entonces, si alcanzan un punto donde el motor se da cuenta de que el patrón no va a coincidir con la cadena de prueba, entonces puede comenzar más de e intentar hacer coincidir de otra manera. Este retroceso repetido suma y ralentiza el algoritmo.

A menudo, la expresión regular se puede reescribir para obtener un mejor rendimiento. Pero lo último en rendimiento sería escribir su propio analizador optimizado para la tarea específica. Al escribir su propio analizador, puede, por ejemplo, analizar de izquierda a derecha mientras mantiene una memoria (o estado). Si utiliza esta técnica en el código de procedimiento, a menudo puede lograr el efecto que está buscando en una sola pasada y sin la lentitud de retroceder.

Me enfrenté a esta decisión a principios de este año. De hecho, la tarea en cuestión estaba en el margen exterior de lo que era posible con expresiones regulares. Al final, decidí escribir mi propio analizador, un autómata de inserción integrado, que es increíblemente eficiente para lo que estaba tratando de hacer. La tarea, dicho sea de paso, fue construir algo que pueda analizar expresiones regulares y proporcionar una sugerencia de código similar a Intellisense para ellas.

Es algo irónico que yo no usar expresiones regulares para analizar las expresiones regulares, pero se puede leer acerca de la idea detrás de todo aquí ... http://blog.regexhero.net/2010/03/code-hinting-for-regular-expressions.html

Answer 6

qué tipo de expresión regular sería mejor volver a escribirse específicamente para un problema dado a través de la manipulación de cadenas?

Fácil.

1. Determine si alguna vez necesita volver a escribir algo.
   (la respuesta positiva sería aproximadamente 1 por 10000 secuencias de comandos, análisis masivo de texto, recurso crítico)
2. Haz perfil posibles soluciones.
3. uso que usted para un problema dado

Como para el resto de 9999 casos que no pierda su tiempo con un problema de este tipo y el uso poco lo que quiera más trajes.

Cada vez que se hace una pregunta de este tipo, es extremadamente útil recordar que, por defecto, todos los códigos extra-optimizados y superrápidos que se analizan char por char en cada solicitud del usuario. No hay expresiones regulares que rompan el cerebro, ni manipulaciones de cuerda desviadas, sino solo viejos y buenos dibujos una por una.