Najszybszy sposób na sprawdzenie, czy ciąg pasuje do wyrażenia regularnego w języku Ruby?

Jaki jest najszybszy sposób sprawdzenia, czy ciąg znaków pasuje do wyrażenia regularnego w Rubim?

Mój problem polega na tym, że muszę „egrepować” przez ogromną listę ciągów, aby znaleźć te, które pasują do wyrażenia regularnego podanego w czasie wykonywania. Dbam tylko o to, czy ciąg pasuje do wyrażenia regularnego, a nie do tego, gdzie pasuje, ani jaka jest zawartość pasujących grup. Mam nadzieję, że to założenie może posłużyć do skrócenia czasu spędzanego przez mój kod na dopasowywaniu wyrażeń regularnych.

Ładuję wyrażenie regularne z

pattern = Regexp.new(ptx).freeze

Odkryłem, że string =~ patternjest nieco szybszy niż string.match(pattern).

Czy istnieją inne sztuczki lub skróty, dzięki którym ten test będzie jeszcze szybszy?

Począwszy od Ruby 2.4.0, możesz używać RegExp#match?:

pattern.match?(string)

Regexp#match?jest wyraźnie wymieniony jako ulepszenie wydajności w informacjach o wydaniu 2.4.0 , ponieważ pozwala uniknąć alokacji obiektów wykonywanych innymi metodami, takimi jak Regexp#matchi =~:

Wyrażenie regularne # pasuje?
Dodano Regexp#match?, która wykonuje dopasowanie wyrażenia regularnego bez tworzenia obiektu odniesienia wstecznego i zmiany w $~celu zmniejszenia alokacji obiektu.

To jest prosty test porównawczy:

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)

Więc =~jest szybszy, ale zależy to od tego, co chcesz mieć jako zwracaną wartość. Jeśli chcesz tylko sprawdzić, czy tekst zawiera wyrażenie regularne, czy nie użyj=~

To jest test porównawczy, który sprawdziłem po znalezieniu kilku artykułów w sieci.

Z 2.4.0 zwycięzcą jest re.match?(str)(jak sugeruje @ wiktor-stribiżew), w poprzednich wersjach re =~ strwydaje się być najszybszy, chociaż str =~ rejest prawie tak samo szybki.

#!/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

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

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

Wyniki MRI 2.3.3 (wydaje się, że występuje regresja w dopasowywaniu wyrażeń regularnych):

$ ./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)

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

A co z re === str(porównanie przypadków)?

Ponieważ wartościuje jako prawda lub fałsz i nie ma potrzeby przechowywania dopasowań, zwracania indeksu dopasowania i tym podobnych rzeczy, zastanawiam się, czy byłby to jeszcze szybszy sposób dopasowania niż =~.

Ok, przetestowałem to. =~jest nadal szybszy, nawet jeśli masz wiele grup przechwytywania, jednak jest szybszy niż inne opcje.

BTW, co jest dobre freeze? Nie mogłem zmierzyć z tego żadnego wzrostu wydajności.

W zależności od tego, jak skomplikowane jest twoje wyrażenie regularne, możesz po prostu użyć prostego cięcia ciągów. Nie jestem pewien, czy jest to praktyczne w przypadku twojej aplikacji, ani czy rzeczywiście zapewniłoby to poprawę szybkości.

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

Zastanawiam się, czy istnieje jakiś dziwny sposób, aby to sprawdzić jeszcze szybciej, być może wykorzystując jakąś dziwną metodę w Regexp lub jakąś dziwną konstrukcję.

Silniki Regexp różnią się pod względem implementacji wyszukiwań, ale ogólnie zakotwiczają wzorce szybkości i unikają zachłannych dopasowań, zwłaszcza podczas wyszukiwania długich ciągów.

Najlepszą rzeczą do zrobienia, dopóki nie zaznajomisz się z działaniem konkretnego silnika, jest wykonanie testów porównawczych i dodawanie / usuwanie kotwic, próbowanie ograniczania wyszukiwań, używania symboli wieloznacznych zamiast dopasowań jawnych itp.

Owocowy klejnot jest bardzo przydatna do szybkiego benchmarkingu rzeczy, bo to mądry. Benchmark wbudowany w Ruby kod jest również przydatny, chociaż możesz pisać testy, które oszukują Cię, nie zachowując ostrożności.

Użyłem obu w wielu odpowiedziach tutaj w Stack Overflow, więc możesz przeszukać moje odpowiedzi i zobaczyć wiele małych sztuczek i wyników, które dają pomysły na pisanie szybszego kodu.

Najważniejszą rzeczą do zapamiętania jest to, że przedwczesna optymalizacja kodu jest zła, zanim dowiesz się, gdzie występują spowolnienia.

Aby uzupełnić odpowiedzi Wiktora Stribiżew i Dougui powiedziałbym, że /regex/.match?("string")tak szybko, jak"string".match?(/regex/) .

Ruby 2.4.0 (10000000 ~ 2 sekundy)

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

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>

Uwaga: czasy są różne, czasami /regex/.match?("string")są szybsze, a czasami "string".match?(/regex/)różnice mogą wynikać tylko z pracy maszyny.