2

パターンは、値と関数を持つハッシュです。例えば：

pattern = {a:1,b:2,c:function(x){ return x<5; }}

オブジェクトがパターンに一致するかどうかをチェックする関数があります。たとえば、obj.a == 1、obj.b == 2、obj.c <5の場合、オブジェクトは上記のパターンに一致します。いくつかのテスト：

matches(pattern,{a:1,b:3,c:2}) == false // because b != 2
matches(pattern,{a:1,b:2,c:7}) == false // because c >= 5
matches(pattern,{a:1,b:2,c:3}) == true //fine
matches(pattern,{a:1,b:2,c:2,d:4}) == true //no problems in having extras

一連のパターンがあり、オブジェクトがそれらのパターンのいずれかに一致するかどうかを調べたいとします。1つずつ確認することもできますが、このように、複雑さはO（n）になります。ここで、nはパターンの数です。パターンのセットを使用して他の構造を構築すると、これを最適化できると感じています。しかし、その構造がどうなるかはわかりません。考え？

4

1 に答える 1

3

決定木を作成できます(またはBDDデータ構造に最適化します)。これには、各オブジェクトの評価中に関連する各変数を 1 回だけ読み取る必要があります。

BDD は論理式を評価する方法です。あなたの場合、論理式は

pattern_1 OR pattern_2 OR pattern_3 OR .... OR pattern_n
于 2012-12-05T08:31:03.407 に答える