[ruby] 문자열이 루비의 정규 표현식과 일치하는지 확인하는 가장 빠른 방법은 무엇입니까?

문자열이 Ruby의 정규 표현식과 일치하는지 확인하는 가장 빠른 방법은 무엇입니까?

내 문제는 런타임에 주어진 정규 표현식과 일치하는 문자열을 찾기 위해 거대한 문자열 목록을 통해 “egrep”해야한다는 것입니다. 나는 문자열이 정규 표현식과 일치하는지 여부, 일치하는 위치 또는 일치하는 그룹의 내용이 무엇인지에만 관심이 있습니다. 이 가정이 내 코드가 정규 표현식과 일치하는 시간을 줄이는 데 사용될 수 있기를 바랍니다.

정규식을로드합니다.

pattern = Regexp.new(ptx).freeze

나는 것으로 나타났습니다 string =~ pattern약간 빠르게보다 string.match(pattern).

이 테스트를 더 빠르게하는 데 사용할 수있는 다른 트릭이나 단축키가 있습니까?



답변

Ruby 2.4.0부터 다음을 사용할 수 있습니다 RegExp#match?.

pattern.match?(string)

Regexp#match?및 다음 과 같은 다른 방법에 의해 수행되는 객체 할당을 방지하기 때문에 2.4.0 릴리스 노트 에서 성능 향상으로 명시 적으로 나열됩니다 .Regexp#match=~

Regexp # match? 역 참조 객체를 생성하지 않고 객체 할당을 줄이기 위해 변경하지 않고 정규 표현식 일치를 실행하는을
추가했습니다 .Regexp#match?$~


답변

이것은 간단한 벤치 마크입니다.

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)

따라서 =~더 빠르지 만 반환 값으로 원하는 것을 결정합니다. 텍스트에 정규식이 포함되어 있는지 확인하려면=~


답변

이것은 인터넷에서 몇 가지 기사를 찾은 후에 실행 한 벤치 마크입니다.

2.4.0에서 승자는 re.match?(str)(@ wiktor-stribiżew가 제안한대로) 이전 버전에서 re =~ str가장 빠르지 만 str =~ re거의 비슷합니다.

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

결과 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)

결과 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)

결과 MRI 2.3.3 (정규식 일치에 회귀가있는 것 같습니다) :

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

결과 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)


답변

무엇에 대해 re === str(대소 비교)?

true 또는 false로 평가되고 일치 항목을 저장하고 일치 인덱스를 반환 할 필요가 없기 때문에 .NET보다 훨씬 빠른 일치 방법이 아닐까요 =~?


좋아, 나는 이것을 테스트했다. =~캡처 그룹이 여러 개인 경우에도 여전히 빠르지 만 다른 옵션보다 빠릅니다.

BTW, 무슨 소용이 freeze있습니까? 성능 향상을 측정 할 수 없었습니다.


답변

정규식이 얼마나 복잡한 지에 따라 간단한 문자열 슬라이싱을 사용할 수 있습니다. 이 응용 프로그램의 실용성 또는 실제로 속도 향상을 제공하는지 여부는 확실하지 않습니다.

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


답변

내가 궁금한 것은이 검사를 더 빠르게 만드는 이상한 방법이 있는지, 아마도 Regexp의 이상한 방법이나 이상한 구조를 이용하는 것입니다.

Regexp 엔진은 검색을 구현하는 방법에 따라 다르지만 일반적으로 패턴을 속도에 고정하고 특히 긴 문자열을 검색 할 때 탐욕스러운 일치를 피하십시오.

특정 엔진이 작동하는 방식에 익숙해 질 때까지 가장 좋은 방법은 벤치 마크를 수행하고 앵커를 추가 / 제거하고 검색을 제한하고 와일드 카드와 명시 적 일치를 사용하는 것입니다.

과일 이 똑똑하기 때문에 보석은 빠르게 벤치마킹 것들에 대한 매우 유용합니다. 루비의 빌트인 벤치 마크 코드도 유용하지만주의하지 않으면 속이는 테스트를 작성할 수 있습니다.

여기 Stack Overflow의 많은 답변에서 두 가지를 모두 사용 했으므로 내 답변을 검색하고 더 빠른 코드를 작성하는 방법에 대한 아이디어를 제공하는 많은 작은 트릭과 결과를 볼 수 있습니다.

기억해야 할 가장 큰 점은 속도 저하가 발생하는 위치를 알기 전에 코드를 조기에 최적화하는 것은 좋지 않다는 것입니다.


답변

완료하려면 Wiktor Stribiżew을 하고 Dougui은 내가 그 말을 대답 /regex/.match?("string")에 대해 최대한 빨리 "string".match?(/regex/).

루비 2.4.0 (10000000 ~ 2 초)

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> 

루비 2.6.2 (100000000 ~ 20 초)

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>

참고 : 시간은 다양하며 때로는 /regex/.match?("string")더 빠르며 때로는 "string".match?(/regex/)기계 활동으로 인해 차이가있을 수 있습니다.