¿Cuál es la expresión regular más eficiente?

Question

Recientemente recibí algunos resultados de pruebas para solicitantes de empleo en los que una persona afirmó que la solución que dieron fue más eficiente (no diré cuál porque no quiero influir en las respuestas). Huelga decir que era escéptico, pero no sé lo suficiente sobre el funcionamiento interno de los compiladores de RE para comentar inteligentemente.

La pregunta era: dé una expresión regular para reconocer los números del 0 al 99 inclusive.

Las respuestas fueron:

[0-9]{1,2} 
[0-9]?[0-9] 
[0-9]|([0-9][0-9]) 

Me interesaría por qué ninguno de estos son más rápidos (o mejor de cualquier otro modo). Puntos de bonificación por proporcionar pruebas en lugar de conjeturas, pero seguiré conjeturando si lo haces sonar convincente :-)

Answer 1

La expresión [0-9]{1,2} debe ser el más rápido me imagino, aunque dependerá del motor específico.

Mi razonamiento es:

• [0-9] {1,2} - esto describe exactamente lo que desea hacer coincidir.
• [0-9]? [0-9] - esto podría dar como resultado un retroceso si falla la primera coincidencia.
• [0-9] | ([0-9] [0-9]) - esto requiere que el primer carácter se verifique dos veces si falla, y los paréntesis aquí son innecesarios y causan una captura innecesaria.

Estas son las iteraciones por segundo llegué al probar esto en .NET (sin RegexOptions.Compiled):

 
Regex      100% valid input 50% valid input 100% invalid input 
"^[0-9]{1,2}$"    749086    800313   870748 
"^[0-9]?[0-9]$"   731951    725984   740152 
"^(?:[0-9]|([0-9][0-9]))$" 564654    687248   870378 

Con RegexOptions.Compiled:

 
Regex      100% valid input 50% valid input 100% invalid input 
"^[0-9]{1,2}$"    1486212   1592535   1831843 
"^[0-9]?[0-9]$"   1301557   1448812   1559193 
"^(?:[0-9]|([0-9][0-9]))$" 1131179   1303213   1394146 

Y como un gráfico :

Nota: modifiqué cada expresión regular para requerir una coincidencia exacta en lugar de realizar una búsqueda.

Answer 2

Por lo menos en teoría, expresiones idénticas como estas producirán autómatas idénticos. Un matcher basado en DFA va a coincidir con un carácter a la vez y tiene las diferentes ramas posibles codificadas en sus estados (en lugar de tomar una rama a la vez y luego retroceder cuando falla), por lo que el rendimiento de cada uno será el mismo .

Las tres expresiones regulares habría que analizará esta DFA:

+---+ 0-9 +---+ 0-9 +---+ * .---. 
| A | --> | B | --> | C | --> (ERR) 
+---+  +---+  +---+  '---' 
    |  /\   | 
    | *  */ \ $  | $ 
    V  / \  V 
.---. /  \  .---. 
(ERR) <--'   '--> (ACC) 
'---'     '---' 

Estado A: Comienza estado. Va a B si ve un dígito, de lo contrario a un estado de ERROR.
Estado B: Un dígito que coincide hasta el momento. Se acepta EOL ($). Un dígito se mueve a C. Cualquier otra cosa es un ERROR.
Estado C: dos dígitos coincidentes. Se acepta EOL, cualquier otra cosa es un ERROR.

Esa es mi respuesta teórica del lenguaje. No puedo hablar con implementaciones de motor regex del mundo real. Estoy ignorando la semántica de captura de los paréntesis ya que supongo que ese no es el punto de la pregunta. Los autómatas tampoco manejan otros constructos "no teóricos" como codicia, anticipación, etc. Al menos no en la presentación de su libro de texto.

Answer 3

Si uno tiene que ser más rápido (probablemente dependerá del motor regex utilizado), entonces claramente el primero en mi opinión (que puede ser un DFA de tabla Morris-Pratt en contraste con los otros dos), como es probable que otros dos requieran retroceder o realizar trabajo adicional:

[0-9]?[0-9] - para la carcasa con un dígito, el motor será codicioso y coincidirá con el primer dígito, luego falla el segundo; dar marcha atrás y luego tener éxito

[0-9]|([0-9][0-9]) - un grupo de captura se utiliza aquí, lo que ralentiza las cosas

Answer 4

Esas expresiones regulares son tan triviales que no deberían importar. Sin embargo, si tuviera que elegir una implementación más eficiente, sería [0-9] {1,2} o [0-9] [0-9] ?, lo cual no está en sus elecciones, ya que no hay retroceso. necesario.

Answer 5

No tengo ni idea sobre las partes internas, pero ¿qué pasa con algunos pseudo bancos? : D

Python

import re 
import time 

regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"] 
numbers = [str(n) for n in range(0, 100)] 

result = None 

// determine loop overhead 
start = time.time() 
for e in xrange(0, 10000): 
    for n in numbers: 
     result = n 

loop = time.time() - start 


for i in regs: 
    r = re.compile(i) 
    now = time.time() 
    for e in xrange(0, 10000): 
     for n in numbers: 
      result = r.search(n) 

    print (time.time() - now) - loop 

resultados en segundos

0.874 
0.869 
0.809 

JavaScript

var regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"] 

var numbers = []; 
for(var n = 0; n < 100; n++) { 
    numbers.push(''+n); 
} 


// determine loop overhead 
var result = null; 
var start = new Date().getTime(); 
for(var e = 0; e < 10000; e++) { 
    for(var n = 0; n < 100; n++) { 
     result = numbers[n]; 
    } 
} 

// test regex 
var loop = new Date().getTime() - start; 
for(var i = 0; i < regs.length; i++) { 
    var r = new RegExp(regs[i]); 
    var now = new Date().getTime(); 
    for(var e = 0; e < 10000; e++) { 
     for(var n = 0; n < 100; n++) { 
      result = r.exec(numbers[n]); 
     } 
    } 
    console.log((new Date().getTime() - now) - loop); //using document.write here in Browsers 
} 

resultados en segundos

Node.js 
0.197 
0.193 
0.226 

Opera 11 
0.836 
0.408 
0.372 

Firefox 4 
2.039 
2.491 
2.488 

Entonces, ¿qué hemos aprendido? Bueno, Pythons parece ser bastante lento, y V8 parece ser bastante rápido.
Pero oye la banca siempre es divertido!

Actualización: La versión de Java

import java.util.regex.Pattern; 

public class Test { 
    public static void main(String args[]) { 
     test(); 
     test(); 
     test(); 
     test(); 
    } 

    public static void test() { 
     String regs[] = {"^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"}; 
     String numbers[] = new String[100]; 
     for(int n = 0; n < 100; n++) { 
      numbers[n] = Integer.toString(n); 
     } 

     // determine loop overhead 
     String nresult = ""; 
     long start = System.nanoTime(); 
     for(int e = 0; e < 10000; e++) { 
      for(int n = 0; n < 100; n++) { 
       nresult = numbers[n]; 
      } 
     } 

     long loop = System.nanoTime() - start; 

     boolean result = false; 
     for(int i = 0; i < regs.length; i++) { 
      Pattern p = Pattern.compile(regs[i]); 

      long now = System.nanoTime(); 
      for(int e = 0; e < 10000; e++) { 
       for(int n = 0; n < 100; n++) { 
        result = p.matcher(numbers[i]).matches(); 
       } 
      } 
      System.out.println(((System.nanoTime() - now) - loop)/1000000); 
     } 
     System.out.println(result); 
     System.out.println(nresult); 
    } 
} 

resultados en segundos (tiempos de la cuarta ejecución)

0.230 
0.262 
0.210 

Answer 6

Sin conocer el motor de expresiones regulares, ni siquiera se puede decidir si esos son correctos .

Por ejemplo, un POSIX ERE es de más larga más a la izquierda, no más a la izquierda más larga, para que elija el más largo de una serie de alternativas, y por lo tanto elegir una cadena a juego "ab" contra /a|ab/ coincidirá con la cadena completa, "ab". Pero un NFA de retroceso normal como lo ve más a menudo haría algo más allí: le importaría ordenar, por lo que emparejar la misma cadena "ab" con el mismo patrón /a|ab/ seleccionaría solo la parte inicial, "a".

La siguiente pregunta es el grupo de captura en el mismo patrón. Si son intencionales, son extraños, ya que mantiene números de dos dígitos pero no números de un dígito. Los otros patrones no hacen eso, sin embargo, se dice que son idénticos en el comportamiento. Así que voy a suponer que tienen un error aquí. De lo contrario, el uso de la memoria del grupo de captura, por supuesto, costará más para arrancar de lo que tomaría , no para hacerlo.

El siguiente problema es la falta de anclajes de ningún tipo. Nuevamente, no podemos saber si son correctos, porque no está claro cómo se vería el conjunto de entrada ni qué hace ese motor en particular con patrones sin anclaje. La mayoría de los motores buscarán en todas partes de la cadena, pero algunos de los menos amigables con los programadores agregarán "de manera útil" anclas de inicio de línea (BOL) y fin de línea (EOL) allí. En motores más habituales, donde esto no ocurre, un código postal en el medio de la línea también coincidiría, ya que cinco dígitos obviamente contienen subcadenas de uno y dos dígitos. Si desea anclas ^ y $, o anclajes \b, no puedo adivinar.

Así que tengo que hacer algunas conjeturas aquí. Voy a dejar los anclajes, pero voy a reordenar la rama de las tres versiones, porque de lo contrario nunca se puede hacer coincidir un número de dos dígitos con los tipos normales (no POSIX) de NFA de retroceso. La mayoría de las cosas se ejecutan.

Antes de siquiera considerar el tiempo, realmente puede pagar para ver qué tipo de programa construye el compilador de expresiones regulares a partir de esos patrones.

% perl -Mre=debug -ce '@pats = (qr/[0-9]{1,2}/, qr/[0-9]?[0-9]/, qr/[0-9][0-9]|[0-9]/)' 
Compiling REx "[0-9]{1,2}" 
Final program: 
    1: CURLY {1,2} (14) 
    3: ANYOF[0-9][] (0) 
    14: END (0) 
stclass ANYOF[0-9][] minlen 1 
Compiling REx "[0-9]?[0-9]" 
synthetic stclass "ANYOF[0-9][]". 
Final program: 
    1: CURLY {0,1} (14) 
    3: ANYOF[0-9][] (0) 
    14: ANYOF[0-9][] (25) 
    25: END (0) 
stclass ANYOF[0-9][] minlen 1 
Compiling REx "[0-9][0-9]|[0-9]" 
Final program: 
    1: BRANCH (24) 
    2: ANYOF[0-9][] (13) 
    13: ANYOF[0-9][] (36) 
    24: BRANCH (FAIL) 
    25: ANYOF[0-9][] (36) 
    36: END (0) 
minlen 1 
-e syntax OK 
Freeing REx: "[0-9]{1,2}" 
Freeing REx: "[0-9]?[0-9]" 
Freeing REx: "[0-9][0-9]|[0-9]" 

Realmente es una buena idea mirar los patrones compilados. Puede ser aún más instructivo observar el patrón compilado que se está ejecutando. Aquí vamos a ver tanto:

% perl -Mre=debug -e '"aabbbababbaaqcccaaaabcacabba" =~ /abc|bca|cab|caab|baac|bab|aaa|bbb/' 
Compiling REx "abc|bca|cab|caab|baac|bab|aaa|bbb" 
Final program: 
    1: TRIEC-EXACT[abc] (25) 
     <abc> 
     <bca> 
     <cab> 
     <caab> 
     <baac> 
     <bab> 
     <aaa> 
     <bbb> 
    25: END (0) 
stclass AHOCORASICKC-EXACT[abc] minlen 3 
Matching REx "abc|bca|cab|caab|baac|bab|aaa|bbb" against "aabbbababbaaqcccaaaabcacabba" 
Matching stclass AHOCORASICKC-EXACT[abc] against "aabbbababbaaqcccaaaabcacabba" (28 chars) 
    0 <> <aabbbababb>   | Charid: 1 CP: 61 State: 1, word=0 - legal 
    1 <a> <abbbababba>  | Charid: 1 CP: 61 State: 2, word=0 - legal 
    2 <aa> <bbbababbaa>  | Charid: 2 CP: 62 State: 11, word=0 - fail 
    2 <aa> <bbbababbaa>  | Fail transition to State: 2, word=0 - legal 
    3 <aab> <bbababbaaq>  | Charid: 2 CP: 62 State: 3, word=0 - fail 
    3 <aab> <bbababbaaq>  | Fail transition to State: 5, word=0 - legal 
    4 <aabb> <bababbaaqc>  | Charid: 2 CP: 62 State: 13, word=0 - legal 
    5 <aabbb> <ababbaaqcc> | Charid: 1 CP: 61 State: 14, word=8 - accepting 
Matches word #8 at position 2. Trying full pattern... 
    2 <aa> <bbbababbaa>  | 1:TRIEC-EXACT[abc](25) 
    2 <aa> <bbbababbaa>  | State: 1 Accepted: 0 Charid: 2 CP: 62 After State: 5 
    3 <aab> <bbababbaaq>  | State: 5 Accepted: 0 Charid: 2 CP: 62 After State: 13 
    4 <aabb> <bababbaaqc>  | State: 13 Accepted: 0 Charid: 2 CP: 62 After State: 14 
    5 <aabbb> <ababbaaqcc> | State: 14 Accepted: 1 Charid: 8 CP: 0 After State: 0 
            got 1 possible matches 
            only one match left: #8 <bbb> 
    5 <aabbb> <ababbaaqcc> | 25:END(0) 
Match successful! 
Freeing REx: "abc|bca|cab|caab|baac|bab|aaa|bbb" 

aquí el compilador tiene realmente inteligente sobre nosotros, y que se compilan en una estructura trie-Aho Corasick. Obviamente, esto va a funcionar de manera bastante diferente a como funcionaría un NFA retroactivo normal en el mismo programa.

De todos modos, aquí están los tiempos para sus patrones, o cerca de ellos. Agregué una formulación alternativa para el número dos, y cambié el orden de las alternativas en el número tres.

testing against short_fail 
       Rate  second  first  third second_alt 
second  9488823/s   --  -9%  -21%  -29% 
first  10475308/s  10%   --  -13%  -22% 
third  11998438/s  26%  15%   --  -11% 
second_alt 13434377/s  42%  28%  12%   -- 

testing against long_fail 
       Rate  second  first  third second_alt 
second  11221411/s   --  -3%  -5%  -5% 
first  11618967/s   4%   --  -1%  -1% 
third  11776451/s   5%   1%   --  -0% 
second_alt 11786700/s   5%   1%   0%   -- 
testing against short_pass 

       Rate  first second_alt  second  third 
first  11720379/s   --  -4%  -7%  -7% 
second_alt 12199048/s   4%   --  -3%  -4% 
second  12593191/s   7%   3%   --  -1% 
third  12663378/s   8%   4%   1%   -- 

testing against long_pass 
       Rate  third  second  first second_alt 
third  11135053/s   --  -1%  -5%  -8% 
second  11221655/s   1%   --  -4%  -7% 
first  11716924/s   5%   4%   --  -3% 
second_alt 12042240/s   8%   7%   3%   -- 

Eso fue producto de este programa:

#!/usr/bin/env perl 
use Benchmark qw<cmpthese>; 

$short_fail = "a" x 1; 
$long_fail = "a" x 600; 

$short_pass = $short_fail . 42; 
$long_pass = $long_fail . 42; 

for my $name (qw< short_fail long_fail short_pass long_pass >) { 
    print "\ntesting against $name\n"; 
    $_ = $$name;  
    cmpthese 0 => { 
     first  => '/[0-9]{1,2}/', 
     second  => '/[0-9]?[0-9]/', 
     second_alt => '/[0-9][0-9]?/', 
     third  => '/[0-9][0-9]|[0-9]/', 
    }  
} 

Aquí están los números con anclajes añadido:

testing against short_fail 
       Rate  first  second second_alt  third 
first  11720380/s   --  -3%  -4%  -11% 
second  12058622/s   3%   --  -1%  -9% 
second_alt 12180583/s   4%   1%   --  -8% 
third  13217006/s  13%  10%   9%   -- 
testing against long_fail 
       Rate  third  first second_alt  second 
third  11378120/s   --  -2%  -4%  -12% 
first  11566419/s   2%   --  -2%  -10% 
second_alt 11830740/s   4%   2%   --  -8% 
second  12860517/s  13%  11%   9%   -- 
testing against short_pass 
       Rate  second  third second_alt  first 
second  11540465/s   --  -5%  -5%  -7% 
third  12093336/s   5%   --  -0%  -3% 
second_alt 12118504/s   5%   0%   --  -2% 
first  12410348/s   8%   3%   2%   -- 
testing against long_pass 
       Rate  first  second second_alt  third 
first  11423466/s   --  -1%  -4%  -7% 
second  11545540/s   1%   --  -3%  -7% 
second_alt 11870086/s   4%   3%   --  -4% 
third  12348377/s   8%   7%   4%   -- 

Y aquí está el programa mínimamente modificado que produjo el segundo conjunto de números:

#!/usr/bin/env perl 
use Benchmark qw<cmpthese>; 

$short_fail = 1 . "a"; 
$long_fail = 1 . "a" x 600; 

$short_pass = 2; 
$long_pass = 42; 

for my $name (qw< short_fail long_fail short_pass long_pass >) { 
    print "testing against $name\n"; 
    $_ = $$name; 
    cmpthese 0 => { 
     first  => '/^(?:[0-9]{1,2})$/', 
     second  => '/^(?:[0-9]?[0-9])$/', 
     second_alt => '/^(?:[0-9][0-9]?)$/', 
     third  => '/^(?:[0-9][0-9]|[0-9])$/', 
    } 
} 

Answer 7

Al igual que C y ++i frente a i=i+1, un buen compilador de expresiones regulares debe compilar los tres de estos a exactamente el mismo autómata finito. Si no es así, lo consideraría un error.

(Excepción:. Si se habilita entre paréntesis marcado sub-expresión, la tercera, obviamente, recopilar la información para incluir el etiquetado adicional)