110

文字列がRubyの正規表現と一致するかどうかを確認する最速の方法は何ですか?

私の問題は、文字列の膨大なリストを「egrep」して、実行時に指定された正規表現に一致するものを見つける必要があることです。文字列が正規表現と一致するかどうかだけに関心があり、一致する場所や一致するグループの内容は気にしません。この仮定を使用して、コードが正規表現の照合に費やす時間を短縮できることを願っています。

正規表現をロードします

pattern = Regexp.new(ptx).freeze

string =~ patternよりもわずかに速いことがわかりましたstring.match(pattern)。

このテストをさらに高速化するために使用できる他のトリックやショートカットはありますか?

4

7 に答える 7

77

これは簡単なベンチマークです。

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)

その=~方が高速ですが、戻り値として何を持ちたいかによって異なります。テキストに正規表現が含まれているかどうかを確認したいだけの場合は、=~

于 2012-08-09T17:03:49.367 に答える
44

これは、ネット上でいくつかの記事を見つけた後に実行したベンチマークです。

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)
于 2012-08-10T19:41:00.243 に答える
7

re === str（ケース比較）はどうですか？

true または false に評価され、一致を保存したり、一致インデックスを返したりする必要がないため、よりも高速な一致方法になるのではないかと思います=~。

わかりました、私はこれをテストしました。=~複数のキャプチャ グループがある場合でも高速ですが、他のオプションよりも高速です。

ところで、何が良いですfreezeか？それによるパフォーマンスの向上は測定できませんでした。

于 2013-05-10T21:23:30.067 に答える
5

正規表現の複雑さによっては、単純な文字列スライスを使用することもできます。あなたのアプリケーションにとってこれが実用的かどうか、または実際に速度が向上するかどうかはわかりません。

'testsentence'['stsen']
=> 'stsen' # evaluates to true
'testsentence'['koala']
=> nil # evaluates to false
于 2012-08-09T15:56:54.240 に答える
3

私が疑問に思っているのは、このチェックをさらに高速にする奇妙な方法があるかどうかです。おそらく、Regexp の奇妙な方法や奇妙な構造を利用することです。

正規表現エンジンは、検索の実装方法が異なりますが、一般に、速度のためにパターンを固定し、特に長い文字列を検索する場合は貪欲な一致を回避します。

特定のエンジンの仕組みに慣れるまでは、ベンチマークを実行してアンカーを追加/削除したり、検索を制限したり、ワイルドカードと明示的な一致を使用したりすることをお勧めします。

Fruity gem はスマートであるため、すばやくベンチマークを行うのに非常に役立ちます。Ruby に組み込まれているBenchmarkコードも便利ですが、注意しないとだまされるようなテストを書くこともできます。

私はここ Stack Overflow の多くの回答で両方を使用したので、私の回答を検索すると、より高速なコードを作成する方法のアイデアを得るために多くの小さなトリックと結果が表示されます。

覚えておくべき最大のことは、スローダウンがどこで発生するかを知る前にコードを時期尚早に最適化するのは良くないということです。

于 2014-10-03T23:51:43.203 に答える