优化布尔逻辑树评估

Question

我有很多真/假结果保存为 long[] 数组中的位。我确实有大量这样的东西（数以百万计的长头）。

例如，假设我只有五个结果，我会：

+----- condition 5 is true
|
|+---- condition 4 is false
||
||+--- condition 3 is true
|||
|||+-- condition 2 is true
||||
||||+- condition 1 is false
10110

我也有一些树代表这样的语句：

condition1 AND (condition2 OR (condition3 AND condition 4))

树非常简单但很长。它们基本上看起来像这样（下面是一个过度简化的例子，只是为了展示我所得到的）：

class Node {    
    int operator();
    List<Node> nodes;
    int conditionNumber();    
}

基本上，节点是一个叶子，然后有一个条件数（匹配 long[] 数组中的一位）或节点不是叶子，因此引用多个子节点。

它们很简单，但允许表达复杂的布尔表达式。效果很好。

到目前为止一切都很好，一切都很好。但是我确实有一个问题：我需要评估很多表达式，确定它们是真还是假。基本上，我需要对一个问题进行一些暴力计算，对于这个问题，没有比暴力破解更好的解决方案。

因此，我需要遍历树并根据树的内容和 long[] 的内容回答 true 或 false 。

我需要优化的方法如下所示：

boolean solve( Node node, long[] trueorfalse ) {
   ...
}

第一次调用时，node 是根节点，然后显然是子节点（是递归的，solve 方法调用自身）。

知道我只有几棵树（可能最多一百棵左右）但有数百万个 long[] 需要检查，我可以采取哪些步骤来优化它？

明显的递归解决方案传递参数（（子）树和 long[]，我可以通过不将其作为参数传递来摆脱 long[]），并且所有递归解决方案都非常慢我需要检查使用了哪个运算符（AND、OR 或 NOT 等），并且涉及大量 if/else 或 switch 语句。

我不是在寻找另一种算法（没有），所以我不是在寻找从 O(x) 到 O(y) 的算法，其中 y 小于 x。

我正在寻找的是“x倍”加速：如果我可以编写执行速度快5倍的代码，那么我将获得5倍的加速，仅此而已，我会对此感到非常满意。

到目前为止，我看到的唯一增强功能——我认为与我现在所拥有的相比，这将是一个巨大的“倍x”加速——是为每棵树生成字节码并具有逻辑对于每棵树都硬编码到一个类中。它应该工作得很好，因为我只会有一百棵左右的树（但树不是固定的：我无法提前知道树会是什么样子，否则简单地手动硬编码每棵树将是微不足道的）。

除了为每棵树生成字节码之外，还有什么想法吗？

现在如果我想尝试字节码生成路线，我应该怎么做？

Answer 1

为了最大化捷径评估的机会，您需要进行自己的分支预测。

您可能想要对其进行分析，计算

• 哪些 AND 分支计算结果为 false
• ，哪些 OR 分支结果为 true，

然后您可以相对于在分析步骤中找到的权重对树重新排序。如果您想要/需要特别聪明，您可以设计一种机制来在运行时检测特定数据集的权重，以便您可以动态地重新排序分支。

请注意，在后一种情况下，建议不要对实际树重新排序（相对于仍在执行时的存储效率和结果的正确性），而是设计一个树节点访问者（遍历算法） ）能够根据“实时”权重对分支进行本地排序。

我希望这一切都有意义，因为我意识到散文版本很密集。然而，就像 Fermat 所说，代码示例太大，无法容纳在这个边距中:)

Answer 2

在 C 语言中，有一种简单快速的方法来评估这样的布尔运算。假设你想评估 z=(x op y)，你可以这样做：

 z = result[op+x+(y<<1)];

所以 op 将是 4 的倍数来选择你的运算 AND、OR、XOR等等，您为所有可能的答案创建一个查找表。如果这个表足够小，您可以将其编码为单个值，并使用右移和掩码来选择输出位：

z = (MAGIC_NUMBER >> (op+x+(y<<1))) & 1;

这将是评估大量这些值的最快方法。当然，您必须将具有多个输入的操作拆分为每个节点只有 2 个输入的树。然而，没有简单的方法可以解决这个问题。您可以将树转换为列表，其中每个项目包含操作编号以及指向 2 个输入和输出的指针。一旦采用列表形式，您可以使用单个循环非常快速地遍历该行一百万次。

对于小树来说，这是一个胜利。对于具有短路的较大树来说，这可能不是一个胜利，因为需要评估的平均分支数量从 2 到 1.5，这对于大型树来说是一个巨大的胜利。 YMMV。

编辑：
再想一想，您可以使用诸如跳跃列表之类的东西来实现短路。每个操作（节点）将包括一个比较值和一个跳过计数。如果结果与比较值匹配，则可以绕过下一个跳过计数值。因此，列表将通过树的深度优先遍历来创建，并且第一个子节点将包含等于另一个子节点大小的跳过计数。这使每个节点评估变得更加复杂，但允许短路。仔细的实现可以在没有任何条件检查的情况下做到这一点（想想跳跃计数的 1 或 0 倍）。

Answer 3

我认为你的字节编码想法是正确的方向。
无论语言如何，我要做的就是编写一个预编译器。
它会遍历每棵树，并使用 print 语句将其转换为源代码，例如。

((word&1) && ((word&2) || ((word&4) && (word&8))))

每当树发生变化时，就可以动态编译，并加载生成的字节代码/dll，所有这些都需要不到一秒钟的时间。

问题是，目前你正在解释树的内容。
将它们转换成编译后的代码应该会使它们的运行速度提高 10-100 倍。

添加是为了回应您关于没有 JDK 的评论。然后，如果无法生成 Java 字节码，我会尝试编写自己的字节码解释器，并且运行速度尽可能快。它可能看起来像这样：

while(iop < nop){
  switch(code[iop++]){
    case BIT1: // check the 1 bit and stack a boolean
      stack[nstack++] = ((word & 1) != 0);
      break;
    case BIT2: // check the 2 bit and stack a boolean
      stack[nstack++] = ((word & 2) != 0);
      break;
    case BIT4: // check the 4 bit and stack a boolean
      stack[nstack++] = ((word & 4) != 0);
      break;
    // etc. etc.
    case AND: // pop 2 booleans and push their AND
      nstack--;
      stack[nstack-1] = (stack[nstack-1] && stack[nstack]);
      break;
    case OR: // pop 2 booleans and push their OR
      nstack--;
      stack[nstack-1] = (stack[nstack-1] || stack[nstack]);
      break;
  }
}

这个想法是让编译器将开关转换为跳转表，因此它以最少的周期数执行每个操作。
要生成操作码，您只需对树进行后缀遍历即可。

最重要的是，您也许可以通过对德摩根定律进行一些操作来简化它，这样您就可以一次检查多个位。