1

入力文字列を受け取り、一致するものが見つかるまでいくつかの正規表現を介して文字列を実行する関数があります。一致が見つかったら、元の文字列と一致の関数である出力を返します。だからルビーで：

str = "my very long original string ... millions of characters"
case str
  when regex1
    do_something1(str,$1)
  when regex2
    do_something2(str,$1)
  when regex3
    do_something3(str,$1)
  ...
  when regex100000
    do_something100000(str,$1)
  else
    do_something_else(str)
end

さて、Rubyは実際にこのスイッチループを最適化して、strが1回だけトラバースされるようにしていますか？そうでない場合は、コールバックが埋め込まれた1つの大きな長い正規表現を使用して、この機能をはるかに効率的に実行できます。このようなもの：

/(?<callback:do_something1>regex1)|
(?<callback:do_something2>regex2)|
(?<callback:do_something3>regex3)|
   ...
(?<callback:do_something100000>regex100000)/

これを行う技術はありますか？

4

1 に答える 1

6

Ruby 1.9の場合、正規表現で名前付きグループを使用する場合は、少し注意を払ってすべての正規表現を1つにまとめることができます。重労働を行うクラスは次のとおりです。

class BigPatternMatcher

  def initialize(patterns_and_functions, no_match_function)
    @regex = make_big_regex(patterns_and_functions)
    @no_match_function = no_match_function
  end

  def match(s, context)
    match = @regex.match(s)
    context.send(function_name(match), match)
  end

  private

  FUNC_GROUP_PREFIX = "func_"
  FUNC_GROUP_REGEX = /^#{FUNC_GROUP_PREFIX}(.*)$/

  def function_name(match)
    if match
      match.names.grep(FUNC_GROUP_REGEX).find do |name|
        match[name]
      end[FUNC_GROUP_REGEX, 1]
    else
      @no_match_function
    end
  end

  def make_big_regex(patterns_and_functions)
    patterns = patterns_and_functions.map do |pattern, function|
      /(?<#{FUNC_GROUP_PREFIX}#{function}>#{pattern.source})/
    end
    Regexp.union(patterns)
  end

end

これがどのように機能するかに戻ります。これを使用するには、正規表現のリストと、それぞれに対して呼び出す必要のある関数の名前が必要です。名前付きグループのみを使用してください。

PATTERNS_AND_FUNCTIONS = [
  [/ABC(?<value>\d+)/, :foo],
  [/DEF(?<value>\d+)/, :bar],
]

そして、一致するものがないときに呼び出される関数を含む関数：

def foo(match)
  p ["foo", match[:value]]
end

def bar(match)
  p ["bar", match[:value]]
end

def default(match)
  p ["default"]
end

そして最後に、これがその使用方法です。 BigPatternMatcher#match一致する文字列と、関数が呼び出されるオブジェクトを取得します。

matcher = BigPatternMatcher.new(PATTERNS_AND_FUNCTIONS, :default)
matcher.match('blah ABC1 blah', self)    # => ["foo", "1"
matcher.match('blah DEF2 blah', self)    # => ["bar", "2"]
matcher.match('blah blah', self)         # => ["default"]

それを機能させるトリックについては、フォールドの下を参照してください。

BigPatternMatcher#make_big_regexすべての正規表現を1つに結合し、それぞれを括弧で囲み|、たとえば、で区切ります。

/(ABC(?<value>\\d+))|(DEF(?<value>\\d+))/

しかし、それだけでは十分ではありません。部分式の1つが一致したときに、どれが一致したか、したがってどの関数を呼び出すかを識別するための何らかの方法が必要です。これを行うには、各部分式に独自の名前付きグループを作成します。名前は、呼び出す必要のある関数に基づいています。

/(?<func_foo>ABC(?<value>\\d+))|(?<func_bar>DEF(?<value>\\d+))/

それでは、一致から関数の呼び出しに至るまでの経緯を見てみましょう。与えられた文字列：

"blah ABC1 blah"

次に、マッチグループは次のとおりです。

#<MatchData "ABC1" func_foo:"ABC1" value:"1" func_bar:nil value:nil>

呼び出す関数を特定するには、「func_」で始まり、nil以外の値を持つ名前の一致を見つける必要があります。「func_」の後のグループ名の部分は、呼び出す関数に名前を付けます。

あなたの質問の簡単なテクニックに対してこれのパフォーマンスを測定することは読者のための練習です。

于 2012-07-04T20:25:56.277 に答える