2

现在，我正在使用这种技术从搜索中删除不需要的单词：

IGNORED_WORDS.each { |e| params[:query].gsub!(e,'') }

我的同事告诉我，正则表达式替换会更快。这是真的吗？如果是，为什么？

4

3 回答 3

4

如果您正在使用正则表达式，您将使用 将所有被忽略的单词组合成一个正则表达式Regexp.union，并且有两个原因可以想到为什么使用它可能会更快。

1) Ruby 中不需要迭代。正则表达式匹配必须查看有问题的单个正则表达式中的备选方案，但这是由用 C 实现的 Oniguruma 正则表达式引擎完成的。这比使用您的解决方案在 Ruby 中迭代每个被忽略的单词要快。

2）由于您将使用一个将所有单词作为替代词的正则表达式，因此一旦使用某个替代词成功，特定位置的匹配就会停止，并且忽略的单词列表中的其他替代词将不会在该位置匹配.

并且 2) 意味着您可以通过按照出现在文本中的可能性顺序重新排列被忽略的单词来提高速度。

编辑对不起，2）可能没有多大意义，因为它比其他方法更快，因为在您的其他方法中，gsub！将从原始字符串中删除匹配的单词，因此位于该位置的子字符串将不会与后面的单词匹配。在这方面，应该没有区别。但是，如果您在不替换的情况下进行匹配，例如计算被忽略的单词等，那么正则表达式方法在这方面也更快。

于 2012-10-08T22:10:40.150 回答
2

正如@sawa 刚才所说，找到您的任何一个IGNORED_WORDS（如果数组很大）的更快方法是执行以下操作：

# just compile the regexp once, then use it as many times as you want
IGNORED = Regexp.union(*IGNORED_WORDS)

# then inside a method somewhere...
string.gsub!(IGNORED, '')

我不知道 Oniguruma 正则表达式引擎有多聪明，但是一个好的基于 DFA 的引擎会将这样的正则表达式编译到一个状态机中，该状态机进行一次线性传递string（从不回溯）。如果它将正则表达式直接编译为本机代码，那就更好了（但 Oniguruma 没有——它在内部使用字节码）。对于这样的任务，基于 DFA 的引擎会很糟糕——没有显式的字符串操作调用会触及它。

于 2012-10-08T22:17:41.850 回答
1

看起来天真的正则表达式并不快：

require "benchmark"

IGNORED_WORDS = ["foo", "bar"]

def regex
  my_string = "I foo'd her right in the bar last night!"
  IGNORED_WORDS.each { |e| my_string.gsub! Regexp.new(Regexp.escape(e)), '' }
end

def non_regex
  my_string = "I foo'd her right in the bar last night!"
  IGNORED_WORDS.each { |e| my_string.gsub!(e, '') }
end

puts "With regex:    ", Benchmark.measure { (1..100000).each { regex } }
#   1.750000   0.010000   1.760000 (  1.780110)
puts "Without regex: ", Benchmark.measure { (1..100000).each { non_regex } }
#   1.580000   0.000000   1.580000 (  1.592312)

Regex在这种情况下，从忽略单词列表中的每个单词创建一个实例会产生额外的开销，而 usinggsub只需要原始字符串。

但是，如果您知道所有被忽略的单词都有一个可以编写自定义正则表达式的模式，那么您可以避免循环遍历IGNORED_WORDS数组 - 这肯定会更快。（O(1)而不是，确切地说O(n)，n是 的数量。）IGNORED_WORDS

于 2012-10-08T21:40:45.087 回答