ルールリストに対するtclの効率的な文字列検索

Question

文字列がルールのリストと一致するかどうかを検証しようとしています。これらのリスト項目の一致する例えば は、一致ルールのそれに対して：

set ListToCheck [list abc_123 def_123 ghi_456 abc_345 xyz_987] 

set RulesToCheck [list *_123 abc_*] 

は、私は最終的には、文字列の長いリストをチェックするルールの多くの数十の長いリストを持っているし、常に成長します。私は最初の試合だけが欲しい。

私が思いついた方法は少し軽い力のようです。もっと洗練された方法が必要だと思っていました

set match 0 
set matchedrule {} 
set matchdict {} 
foreach value $ListToCheck { 
    foreach rule $RulesToCheck { 
     if {[string match $rule $value] == 1} { 
      set match 1 
      set matchedrule $rule 
      break 
     } 
    } 
    <take some action on the $value and $rule matched here> 
    ... 
} 

これが最善の方法ですか？私はよりよい方法があるべきであるように感じる。

Answer 1

ルールが実際にグロブパターンで記述されている場合、一致するルールを最適化するために行うことができる膨大な量はありません。まあ、すべてのマッチング理論と賢明な書き直しとすべてを取得しない限り、それは難しいです。

あなたはです。少し速いマッチャーを作るためにいくつかのことを行います。 警告！次のコード生成が含まれています。

# Build a lambda that uses [switch -glob] 
set ruleset {} 
foreach rule $RulesToCheck { 
    lappend ruleset $rule [list return [list 1 $rule]] 
} 
set matcher [list value "switch -glob -- \$value [list $ruleset];return {0 {}}"] 

# Now we can use the lambda term as much as we want 
foreach value $ListToCheck { 
    lassign [apply $matcher $value] match matchedrule 
    # take some action on the $value and $rule matched here 
    # ... 
    # I tested with: 
    # if {$match} {puts "$value was matched by $matchedrule"} 
} 

applyにで行くことを必要とする費用で（私はこのコードを時限いませんでしたが、それは幾分良好バイトコードを生成しますようチェックするためのルールやアイテムの合理的な数のために、それはより良い行う必要がありますそれぞれが一致します。これは手続きを呼び出すほど高価です）。

Answer 2

別のアプローチは、単一のREにグロブパターンのコレクションを変換することです。

# Note that this is Tcl 8.6 syntax - both [lmap] and [string cat] are used 
# Rewriting into 8.5 syntax is left as an exercise 
set RE [string cat "(" [join [lmap s $RulesToCheck { 
    # Assuming you've not got any [...] bits in your glob pattern... 
    string cat "^" [string map {* .* ? . \\ {\\}} $s] "$" 
}] ")|("] ")"] 

foreach value $ListToCheck { 
    set matchinfo [regexp -inline -indices -- $RE $value] 
    if {[llength $matchinfo]} { 
     foreach pattern $RulesToCheck idxs [lrange $matchinfo 1 end] { 
      if {[lindex $idxs 0] >= 0} { 
       puts "matched $pattern against $value" 
       break 
      } 
     } 
    } 
} 

これは、ラムダを構築した私の以前の回答よりもどのような状況で効率的かはわかりません。マッチが発生した決定のコストは、それ自体が刺激される可能性が高いと思われる（一致率が十分に低いと十分なパターンが複雑な場合ものの、その後多分 ...）