optimization - 复杂的 bool 表达式优化，范式？

Question

我正在开发一个流规则引擎，我的一些客户有几百条规则，他们想对到达系统的每个事件进行评估。规则是纯(即无副作用) bool 表达式，它们可以任意深度嵌套。
客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式计算在内部 AST 上使用解释器，我还没有开始考虑 codegen。
与往常一样，树中的某些谓词的计算成本比其他谓词要便宜得多，而且我一直在寻找一种算法或数据结构，可以更容易地找到便宜的谓词，并且可以有效地解释为控制整个表达。我对这种模式的心理标题是“一直到根的 AND”，即所有祖先都是 AND 的任何谓词都可以解释为控制。
尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我还是无法从行业中的常见做法到我的特定用例关闭循环。我发现似乎相关的一件事是 Analysis and optimization for boolean expression indexing但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。
我一直半开玩笑地向我的团队提到，这些天我们将需要一个 SAT 求解器。 😅 我想编写一个递归算法来遍历树并跟踪每个祖先是 AND 还是 OR 可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。 :)
编辑:与几个 friend 交谈后，我想我可能有一个解决方案的草图!

将表达式转换为联合范式，根据定义，其中每个节点都处于有效的短路位置。

使用 Tseitin 算法尽量避免因 CNF 变换而导致的表达式大小指数膨胀

对于树中的每个 AND，按成本升序排序(即最便宜的在左边)

？？？

利润!^Weval 像往常一样:)

Answer 1

您应该认真考虑编译规则(和谓词)。对于同样的事情，解释器比机器代码慢 10-50 倍。如果规则集不经常更改，这是一个好主意。如果规则可以动态更改甚至是一个好主意，因为在实践中它们仍然不会很快更改，尽管现在您的规则编译器已经在线。呃，只是让一个更大的应用程序和内存不再是一个问题了。
使用单个机器指令的 bool 表达式评估甚至更好。任何复杂的 bool 方程都可以在叶值上的单个机器指令的无分支序列中编译。没有分支，没有缓存未命中；东西运行得非常快。现在，如果您有昂贵的谓词，您可能希望使用分支编译代码以跳过不影响表达式结果的子树，如果它们包含昂贵的谓词。
在合理范围内，您可以生成任何等效形式(我会为使用 CNF 的想法尖叫到深夜，因为它总是对您产生影响)。您真正想要的是与客户端提供的等效的最短 bool 方程(最深的表达式树)，因为这将执行最少的机器指令。这听起来可能很疯狂，但您可能会考虑生成详尽的搜索代码，例如，从字面上尝试每一种有可能起作用的组合，尤其是当方程中的运算符数量相对较少时。在将 bool 方程合成为门时，VLSI 世界一直在努力进行各种优化。您应该查看 Espresso 色调 bool 逻辑优化器 ( https://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer )
可能会插入您进行表达式评估的一件事是谓词的成本。如果我有公式 A 和 B，并且我知道评估 A 的成本很高 和 通常返回true，然后很明显我想评估B和A。
您应该考虑公共(public)子表达式评估，以便任何公共(public)子项只计算一次。当有昂贵的谓词时，这一点尤其重要；你永远不想两次评估同一个昂贵的谓词。
大约 20 年前，我在 PLC 仿真器中实现了这些技巧(这些基本上是机器，用于评估告诉工厂执行器何时移动的 bool 方程桶)，使用 x86 机器指令进行 AND/OR/NOT，用于罗克韦尔自动化。它超越了 Rockwell 的“顶级”PLC，后者具有定制硬件，但本质上是一个解释器。
您还可以考虑对方程进行增量评估。基本思想不是一遍又一遍地重新评估所有方程，而是仅重新评估那些输入改变的方程。细节太长，无法在此处包含，但我当时所做的一项专利解释了如何做到这一点。见 https://patents.google.com/patent/US5623401A/en?inventor=Ira+D+Baxter&oq=Ira+D+Baxter