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

99

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?

ruby  regex  performance 
— gioele
źródło
Jeśli nie obchodzi Cię zawartość pasujących grup, dlaczego je masz? Możesz przyspieszyć wyrażenie regularne, konwertując je na nieprzechwytywane.
— Mark Thomas,
1
Ponieważ wyrażenie regularne jest dostarczane w czasie wykonywania, zakładam, że jest ono nieograniczone, w którym to przypadku mogą występować odwołania wewnętrzne w wyrażeniu regularnym do grup, a zatem przekonwertowanie ich na nieprzechwytywane przez modyfikację wyrażenia regularnego może zmodyfikować wynik (chyba że dodatkowo sprawdź odwołania wewnętrzne, ale problem staje się coraz bardziej złożony). Uważam, że to ciekawe = ~ byłoby szybsze niż string.match.
— djconnel,
jaka jest korzyść z zamrożenia wyrażenia regularnego w tym miejscu?
— Hardik,

Odpowiedzi:

106

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.

— Wiktor Stribiżew
źródło
6
Dziękuję za sugestię. Zaktualizowałem skrypt testowy i Regexp#match?rzeczywiście jest co najmniej o 50% szybszy niż inne alternatywy.
— gioele
74

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=~

— Dougui
źródło
2
Jak już napisałem, stwierdziłem, że =~jest szybszy niż matchprzy mniej dramatycznym wzroście wydajności podczas pracy na większych wyrażeniach regularnych. 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ę.
— gioele
Myślę, że nie ma innych rozwiązań
— Dougui
O co chodzi !("test123" !~ /1/)?
— ma11hew28
1
@MattDiPasquale, dwa razy odwrotność nie powinna być szybsza niż"test123" =~ /1/
— Dougui
1
/1/.match?("test123")jest szybszy, niż "test123" =~ /1/gdyby służył tylko do sprawdzenia, czy tekst zawiera wyrażenie regularne, czy nie.
— noraj
42

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)
— gioele
źródło
Dla przypomnienia, dosłowne formy są szybsze niż te. Np /a+b/ =~ stra str =~ /a+b/. Jest poprawny nawet podczas iteracji po funkcjach i wydaje mi się, że jest na tyle ważny, że można go uznać za lepszy niż przechowywanie i zamrażanie wyrażeń regularnych w zmiennej. Przetestowałem mój skrypt z Rubim 1.9.3p547, Ruby 2.0.0p481 i Ruby 2.1.4p265. Możliwe, że te ulepszenia zostały wprowadzone w późniejszych łatach, ale nie planuję jeszcze testować ich z wcześniejszymi wersjami / łatkami.
— konsolebox
Myślałem, że !(re !~ str)może być szybszy, ale tak nie jest.
— ma11hew28
7

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.

— Heiko
źródło
Efekty freezenie pojawią się w wynikach, ponieważ występuje przed pętlami wzorcowymi i działa na sam wzorzec.
— Tin Man
5

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
— jimmydief
źródło
Nie mogę używać cięcia ciągów, ponieważ wyrażenie regularne jest dostarczane w czasie wykonywania i nie mam nad tym żadnej kontroli.
— gioele
Możesz użyć krojenia ciągów, ale nie krojenia przy użyciu stałego ciągu. Użyj zmiennej zamiast ciągu znaków w cudzysłowach i nadal będzie działać.
— Tin Man
3

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.

— Blaszany Człowiek
źródło
0

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.

— noraj
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.