¿Cuál es la forma más rápida para comprobar si una cadena coincide con una expresión regular en Ruby?

Mi problema es que tengo que «egrep» a través de una enorme lista de cadenas para encontrar cuales son las que coincidan con una expresión regular que se da en tiempo de ejecución. Lo único que importa si la cadena coincide con la regexp, en donde no coincide, ni lo que el contenido de la coincidencia de los grupos es. Espero que esta hipótesis puede ser utilizado para reducir la cantidad de tiempo que mi código de pasar la coincidencia de regex.

Me carga la regexp con

pattern = Regexp.new(ptx).freeze

He encontrado que string =~ pattern es ligeramente más rápido que string.match(pattern).

Hay otros trucos o atajos que se pueden usar para hacer esta prueba aún más rápido?

  • Si usted no se preocupan por el contenido de los grupos de coincidencia, ¿por qué ellos? Usted puede hacer el regex más rápido por la conversión de ellos a la no captura.
  • Desde la regexp se proporciona en tiempo de ejecución, supongo que es sin restricciones, en cuyo caso puede haber referencias internas dentro de la reg-exp a agrupaciones, y por lo tanto la conversión de ellos a no captar mediante la modificación de la regexp podría modificar el resultado (a menos que usted, además, verificación de referencias internas, pero el problema se vuelve cada vez más complejo). Me parece curioso =~ sería más rápido que el de la cadena.partido.
  • ¿cuál es el beneficio de la congelación de la regexp aquí?
InformationsquelleAutor gioele | 2012-08-09

7 Comentarios

  1. 85

    Empezando con Ruby 2.4.0, usted puede usar RegExp#match?:

    pattern.match?(string)

    Regexp#match? aparezca explícitamente como una mejora de rendimiento en el notas de la versión para 2.4.0, ya que evita el objeto de las asignaciones realizadas por otros métodos, tales como Regexp#match y =~:

    Regexp#partido?

    Añadido Regexp#match?, que ejecuta un regexp partido sin crear una copia del objeto de referencia y el cambio de $~ para reducir la asignación de objetos.

    • Gracias por la sugerencia. He actualizado el punto de referencia de script y Regexp#match? es, de hecho, al menos el 50% más rápido que el de otras alternativas.
  2. 72

    Este es un simple punto de referencia:

    require 'benchmark'
    
    "test123" =~ /1/
    => 4
    Benchmark.measure{ 1000000.times { "test123" =~ /1/ } }
    =>   0.610000   0.000000   0.610000 (  0.578133)
    
    "test123"[/1/]
    => "1"
    Benchmark.measure{ 1000000.times { "test123"[/1/] } }
    =>   0.718000   0.000000   0.718000 (  0.750010)
    
    irb(main):019:0> "test123".match(/1/)
    => #<MatchData "1">
    Benchmark.measure{ 1000000.times { "test123".match(/1/) } }
    =>   1.703000   0.000000   1.703000 (  1.578146)

    Así =~ es más rápido, pero depende de lo que quieres tener un valor devuelto. Si usted sólo quiere comprobar si el texto contiene una expresión regular o no uso =~

    • Como escribí, ya he conseguido que =~ es más rápido que match, con un menor aumento significativo del rendimiento cuando se opera en más regex. Lo que me pregunto es si hay alguna forma extraña de hacer esta verificación, incluso más rápido, tal vez la explotación de algún extraño método en Regexp o alguna extraña construcción.
    • Yo creo que no hay otras soluciones
    • ¿Qué acerca de !("test123" !~ /1/)?
    • dos veces a la inversa no debe ser más rápido que "test123" =~ /1/
    • Estás en lo correcto. He probado. No.
    • /1/.match?("test123") es más rápido que "test123" =~ /1/ si es sólo para comprobar si el texto contiene una expresión regular o no.

  3. 39

    Esta es la referencia que he corrido después de encontrar algunos artículos en la red.

    Con 2.4.0 el ganador es re.match?(str) (según lo sugerido por @wiktor-stribiżew), en versiones anteriores, re =~ str parece ser más rápido, aunque str =~ re es casi tan rápido.

    #!/usr/bin/env ruby
    require 'benchmark'
    
    str = "aacaabc"
    re = Regexp.new('a+b').freeze
    
    N = 4_000_000
    
    Benchmark.bm do |b|
        b.report("str.match re\t") { N.times { str.match re } }
        b.report("str =~ re\t")    { N.times { str =~ re } }
        b.report("str[re]  \t")    { N.times { str[re] } }
        b.report("re =~ str\t")    { N.times { re =~ str } }
        b.report("re.match str\t") { N.times { re.match str } }
        if re.respond_to?(:match?)
            b.report("re.match? str\t") { N.times { re.match? str } }
        end
    end

    Los resultados de la resonancia magnética 1.9.3-o551:

    $ ./bench-re.rb  | sort -t $'\t' -k 2
           user     system      total        real
    re =~ str         2.390000   0.000000   2.390000 (  2.397331)
    str =~ re         2.450000   0.000000   2.450000 (  2.446893)
    str[re]           2.940000   0.010000   2.950000 (  2.941666)
    re.match str      3.620000   0.000000   3.620000 (  3.619922)
    str.match re      4.180000   0.000000   4.180000 (  4.180083)

    Los resultados de la resonancia magnética 2.1.5:

    $ ./bench-re.rb  | sort -t $'\t' -k 2
           user     system      total        real
    re =~ str         1.150000   0.000000   1.150000 (  1.144880)
    str =~ re         1.160000   0.000000   1.160000 (  1.150691)
    str[re]           1.330000   0.000000   1.330000 (  1.337064)
    re.match str      2.250000   0.000000   2.250000 (  2.255142)
    str.match re      2.270000   0.000000   2.270000 (  2.270948)

    Los resultados de la resonancia magnética 2.3.3 (hay una regresión en regex coincidencia, parece):

    $ ./bench-re.rb  | sort -t $'\t' -k 2
           user     system      total        real
    re =~ str         3.540000   0.000000   3.540000 (  3.535881)
    str =~ re         3.560000   0.000000   3.560000 (  3.560657)
    str[re]           4.300000   0.000000   4.300000 (  4.299403)
    re.match str      5.210000   0.010000   5.220000 (  5.213041)
    str.match re      6.000000   0.000000   6.000000 (  6.000465)

    Los resultados de la resonancia magnética 2.4.0:

    $ ./bench-re.rb  | sort -t $'\t' -k 2
           user     system      total        real
    re.match? str     0.690000   0.010000   0.700000 (  0.682934)
    re =~ str         1.040000   0.000000   1.040000 (  1.035863)
    str =~ re         1.040000   0.000000   1.040000 (  1.042963)
    str[re]           1.340000   0.000000   1.340000 (  1.339704)
    re.match str      2.040000   0.000000   2.040000 (  2.046464)
    str.match re      2.180000   0.000000   2.180000 (  2.174691)
    • Sólo para agregar una nota, literal formas son más rápidos que ellos. E. g. /a+b/ =~ str y str =~ /a+b/. Es válido incluso cuando se itera ellos a través de las funciones y veo que este lo suficientemente válidas como para considerar como mejor que el almacenamiento y la congelación de las expresiones regulares en una variable. He probado mi script con ruby 1.9.3p547, ruby 2.0.0p481 y ruby 2.1.4p265. Es posible que estas mejoras se hicieron en parches más recientes, pero no tengo ningún plan para poner a prueba con versiones anteriores/parches todavía.
    • Pensé !(re !~ str) puede ser más rápido, pero no lo es.
  4. 7

    Lo que acerca de re === str (el caso de comparar)?

    Ya que se evalúa a verdadero o falso y no tiene necesidad de almacenar los partidos, de regreso coincide con el índice y esas cosas, me pregunto si sería una manera aún más rápida de la coincidencia de =~.


    Ok, he probado esto. =~ es aún más rápido, incluso si usted tiene varias de captura de los grupos, sin embargo es más rápido que el resto de las opciones.

    Por CIERTO, qué bueno es freeze? No podía medir cualquier aumento en el rendimiento de la misma.

    • Los efectos de freeze no se mostrará en los resultados, ya que se produce antes de que el punto de referencia de bucles, y actúa sobre el mismo patrón.
  5. 4

    Dependiendo de lo complicado que la expresión regular, usted podría posiblemente solo uso simple cadena de rebanar. No estoy seguro acerca de la factibilidad de este para su aplicación o de si es o no realmente ofrece ninguna de las mejoras de velocidad.

    'testsentence'['stsen']
    => 'stsen' # evaluates to true
    'testsentence'['koala']
    => nil # evaluates to false
    • No puedo utilizar la cadena de rebanar porque la regexp se proporciona en tiempo de ejecución y no tengo ningún control sobre eso.
    • Puede utilizar la cadena de corte, no sólo rebanar el uso fijo de una cuerda. El uso de una variable en lugar de una cadena entre comillas y que todavía iba a trabajar.
  6. 3

    Lo que me pregunto es si hay alguna forma extraña de hacer esta verificación, incluso más rápido, tal vez la explotación de algún extraño método en Regexp o alguna extraña construcción.

    Regexp motores varían en la forma de implementar búsquedas, pero, en general, ancla sus patrones para la velocidad y evitar codiciosos partidos, especialmente cuando la búsqueda de cadenas largas.

    La mejor cosa a hacer, hasta que usted esté familiarizado con la forma en que un motor de obras, es hacer puntos de referencia y añadir/quitar los anclajes, tratar de limitar las búsquedas, utilizar comodines vs explícito de los partidos, etc.

    La Afrutado gema es muy útil para la rápida evaluación comparativa de las cosas, porque es inteligente. Ruby integrado en Referencia código también es útil, aunque usted puede escribir las pruebas que engañe por no tener cuidado.

    Yo he usado tanto en muchas de las respuestas aquí en Stack Overflow, así que usted puede buscar a través de mis respuestas y verá un montón de pequeños trucos y resultados para dar ideas de cómo escribir código más rápido.

    La cosa más importante a recordar es, es malo para prematuramente optimizar su código antes de saber dónde la lentitud ocurrir.

  7. 0

    Para completar Wiktor Stribiżew y Dougui respuestas yo diría que /regex/.match?("string") tan rápida como la "string".match?(/regex/).

    Ruby 2.4.0 (10 000 000 ~2 seg)

    2.4.0 > require 'benchmark'
     => true 
    2.4.0 > Benchmark.measure{ 10000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
     => #<Benchmark::Tms:0x005563da1b1c80 @label="", @real=2.2060338060000504, @cstime=0.0, @cutime=0.0, @stime=0.04000000000000001, @utime=2.17, @total=2.21> 
    2.4.0 > Benchmark.measure{ 10000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
     => #<Benchmark::Tms:0x005563da139eb0 @label="", @real=2.260814556000696, @cstime=0.0, @cutime=0.0, @stime=0.010000000000000009, @utime=2.2500000000000004, @total=2.2600000000000007> 

    Ruby 2.6.2 (100 000 000 ~20 seg)

    irb(main):001:0> require 'benchmark'
    => true
    irb(main):005:0> Benchmark.measure{ 100000000.times { /^CVE-[0-9]{4}-[0-9]{4,}$/.match?("CVE-2018-1589") } }
    => #<Benchmark::Tms:0x0000562bc83e3768 @label="", @real=24.60139879199778, @cstime=0.0, @cutime=0.0, @stime=0.010000999999999996, @utime=24.565644999999996, @total=24.575645999999995>
    irb(main):004:0> Benchmark.measure{ 100000000.times { "CVE-2018-1589".match?(/^CVE-[0-9]{4}-[0-9]{4,}$/) } }
    => #<Benchmark::Tms:0x0000562bc846aee8 @label="", @real=24.634255946999474, @cstime=0.0, @cutime=0.0, @stime=0.010046, @utime=24.598276, @total=24.608321999999998>

    Nota: el horario varía, a veces /regex/.match?("string") es más rápido y, a veces,"string".match?(/regex/), las diferencias tal vez sólo debido a la máquina de la actividad.

Dejar respuesta

Please enter your comment!
Please enter your name here