Maneira mais rápida de verificar se uma string corresponde a uma regexp em ruby?

Qual é a maneira mais rápida de verificar se uma string corresponde a uma expressão regular em Ruby?

Meu problema é que preciso "egrep" por meio de uma lista enorme de strings para descobrir quais são as que correspondem a um regexp fornecido em tempo de execução. Eu só me preocupo se a string corresponde ao regexp, não onde ela corresponde, nem qual é o conteúdo dos grupos correspondentes. Espero que essa suposição possa ser usada para reduzir a quantidade de tempo que meu código gasta combinando expressões regulares.

Eu carrego o regexp com

pattern = Regexp.new(ptx).freeze

Eu descobri que string =~ patterné um pouco mais rápido do que string.match(pattern).

Existem outros truques ou atalhos que podem ser usados ​​para tornar este teste ainda mais rápido?

A partir do Ruby 2.4.0, você pode usar RegExp#match?:

pattern.match?(string)

Regexp#match?está explicitamente listado como um aprimoramento de desempenho nas notas de versão do 2.4.0 , pois evita alocações de objetos realizadas por outros métodos, como Regexp#matche =~:

Regexp # match?
Adicionado Regexp#match?, que executa uma correspondência de regexp sem criar um objeto de referência anterior e alterar $~para reduzir a alocação de objeto.

Esta é uma referência simples:

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)

Portanto, =~é mais rápido, mas depende do que você deseja ter como valor de retorno. Se você deseja apenas verificar se o texto contém um regex ou não use=~

Este é o benchmark que fiz depois de encontrar alguns artigos na rede.

Com 2.4.0 o vencedor é re.match?(str)(como sugerido por @ wiktor-stribiżew), nas versões anteriores, re =~ strparece ser o mais rápido, embora str =~ reseja quase tão 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

Resultados MRI 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)

Resultados MRI 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)

Resultados MRI 2.3.3 (há uma regressão na correspondência de regex, ao que 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)

Resultados MRI 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)

E sobre re === str(comparação de caso)?

Uma vez que é avaliado como verdadeiro ou falso e não há necessidade de armazenar correspondências, retornar o índice de correspondência e outras coisas, me pergunto se seria uma maneira ainda mais rápida de correspondência do que =~.

Ok, eu testei isso. =~ainda é mais rápido, mesmo se você tiver vários grupos de captura, no entanto, é mais rápido do que as outras opções.

BTW, o que é bom freeze? Não consegui medir nenhum aumento de desempenho com isso.

Dependendo de quão complicada é sua expressão regular, você poderia usar apenas o fatiamento de string simples. Não tenho certeza sobre a praticidade disso para sua aplicação ou se ele realmente ofereceria melhorias de velocidade.

'testsentence'['stsen']
=> 'stsen' # evaluates to true
'testsentence'['koala']
=> nil # evaluates to false

O que estou pensando é se existe alguma maneira estranha de tornar essa verificação ainda mais rápida, talvez explorando algum método estranho no Regexp ou alguma construção estranha.

Os motores Regexp variam em como implementam pesquisas, mas, em geral, ancoram seus padrões para velocidade e evitam correspondências gananciosas, especialmente ao pesquisar strings longas.

A melhor coisa a fazer, até que você esteja familiarizado com o funcionamento de um determinado mecanismo, é fazer benchmarks e adicionar / remover âncoras, tentar limitar as pesquisas, usar curingas vs. correspondências explícitas, etc.

A gema Fruity é muito útil para avaliar rapidamente as coisas, porque é inteligente. O código Benchmark embutido do Ruby também é útil, embora você possa escrever testes que o enganam por não serem cuidadosos.

Usei ambos em muitas respostas aqui no Stack Overflow, então você pode pesquisar minhas respostas e verá muitos pequenos truques e resultados para lhe dar ideias de como escrever código mais rápido.

A coisa mais importante a lembrar é que é ruim otimizar prematuramente seu código antes de saber onde ocorrem as lentidões.

Para completar as respostas de Wiktor Stribiżew e Dougui, eu diria isso /regex/.match?("string")tão rápido quanto "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>

Obs: o tempo varia, às vezes /regex/.match?("string")é mais rápido e às vezes "string".match?(/regex/), as diferenças podem ser apenas devido à atividade da máquina.