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

假设我有一组模式，我想找出一个对象是否与这些模式中的任何一个匹配。我可以一一检查，但是这样一来，我就有了 O(n) 复杂度，其中 n 是模式的数量。我有一种感觉，如果我使用这组模式来构建一些其他结构，这可以优化；但我不确定那个结构可能是什么。想法？

4

1 回答 1

3

您可以创建决策树（或将其优化为BDD数据结构）。这需要在评估每个对象期间仅读取每个相关变量一次。

BDD 是一种评估逻辑公式的方法，在您的情况下，逻辑公式是

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