Jen*_*der 3 algorithm performance boolean scalability data-structures
我有一个庞大的布尔表达式集(20000).他们组成的AND,OR而NOT运营商和大量的布尔变量A1,A2,A3...(约1000).大多数表达式只包含5个,可能包含20个这些变量.
给定变量(A1 = true, A2 = false, A3 = false ...)的赋值,我必须找到那些求值的表达式false.
将针对多个(10-100)分配评估相同的表达式集
以此目的:
我应该如何将表达式存储在磁盘上,以便我可以快速加载和解析它们(我现在将它们作为一些专门的DSL或者或多或少规范化(和死慢)关系数据结构,但我可以改变它)
是否有一个快速的算法/数据结构来评估我可以使用的表达式？
JVM上的实现是否存在？
您可能希望将表达式转换为Conjunctive Normal Form并将其组合为类似术语.然后,您可以将表达式双向映射到一组术语,其中任何一个评估为false意味着整个表达式的计算结果为false.对于每个变量赋值,从一组表达式开始,计算CNF项,直到一个计算结果为false.如果该术语为false,则涉及该术语的所有表达式也将为false,因此也可以从集合中删除这些表达式.
如果没有查看表达式,这种方法是否适合您的情况是不可能的 - 使用1000个变量和20000个表达式,可能并不是因为它们有许多共同的CNF术语.
在Java之外,对于更多的表达式,DNF可能更有用,因为它在GPU上的实现是显而易见的.