优化布尔逻辑树计算-解网

问：

我有很多真/假结果保存为数组中的位。我确实有大量的这些（数以百万计的多头）。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[] 数组中的一个位），或者节点不是叶子，因此引用几个子节点。

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

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

因此，我需要走一走树并回答，或者根据树的内容和内容来回答。truefalselong[]

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

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

其中，在第一次调用时，是根节点，然后显然是子节点（递归的，该方法调用自身）。nodesolve

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

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

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

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

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

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

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

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;
  }
}

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

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

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

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

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

优化布尔逻辑树计算

Optimizing boolean logic tree evaluation

评论

评论

评论

评论