110

检查字符串是否与 Ruby 中的正则表达式匹配的最快方法是什么？

我的问题是我必须通过一个巨大的字符串列表“egrep”来查找哪些与运行时给出的正则表达式匹配。我只关心字符串是否匹配正则表达式，而不关心匹配的位置，也不关心匹配组的内容是什么。我希望这个假设可以用来减少我的代码匹配正则表达式所花费的时间。

我加载正则表达式

pattern = Regexp.new(ptx).freeze

我发现它string =~ pattern比string.match(pattern).

是否有其他技巧或捷径可以让这个测试更快？

4

7 回答 7

122

从 Ruby 2.4.0 开始，您可以使用RegExp#match?：

pattern.match?(string)

Regexp#match?在2.4.0 的发行说明中明确列为性能增强，因为它避免了由其他方法执行的对象分配，例如Regexp#match和=~：

正则表达式#匹配？
添加Regexp#match?，它执行正则表达式匹配而不创建反向引用对象并更改$~以减少对象分配。

于 2017-03-16T12:30:24.637 回答
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 回答
0

要完成Wiktor Stribiżew和Dougui的答案，我会说/regex/.match?("string")大约"string".match?(/regex/).

Ruby 2.4.0（10 000 000 ~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>

Ruby 2.6.2 (100 000 000 ~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/)，差异可能只是由于机器活动。

于 2017-12-04T22:08:23.697 回答