2

現在、私はこの手法を使用して、検索から不要な単語を削除しています。

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

私の同僚は、正規表現の交換がより速くなると言っています。これは本当ですか？もしそうなら、なぜですか？

4

3 に答える 3

4

正規表現を使用している場合は、を使用して無視されたすべての単語を1つの正規表現に結合することになりますRegexp.union。2つの理由から、それを使用した方が速い場合があります。

1）Ruby内で反復は必要ありません。正規表現の一致では、問題の単一の正規表現内の代替を調べる必要がありますが、これはCで実装された鬼車の正規表現エンジンによって行われます。これは、ソリューションで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, '')

鬼車の正規表現エンジンがどれほど賢いのかはわかりませんが、優れたDFAベースのエンジンは、そのような正規表現をステートマシンにコンパイルして、単一の線形パスオーバーを行いますstring（バックトラックはありません）。正規表現をネイティブコードに直接コンパイルする場合は、なおさらです（ただし、鬼車はそうではありません。内部でバイトコードを使用します）。このようなタスクの場合、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無視された単語のリスト内の各単語からインスタンスを作成すると、追加のオーバーヘッドが発生しますが、使用gsubするには元の文字列のみが必要です。

ただし、無視されたすべての単語にカスタム正規表現を記述できるパターンがあることがわかっている場合は、IGNORED_WORDS配列のループを回避できます。これは間違いなく高速です。（O(1)の代わりにO(n)、正確にnはの数です。）IGNORED_WORDS

于 2012-10-08T21:40:45.087 に答える