5

我有很多真/假结果保存为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[] 数组中的一位），要么节点不是叶子，因此引用了几个子节点。

它们很简单，但允许表达复杂的布尔表达式。它工作得很好。

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

所以我需要走树并true根据false树的内容和long[].

我需要优化的方法是这样的：

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 倍”加速——将为每棵树生成字节码，并将每棵树的逻辑硬编码到一个类中. 它应该工作得很好，因为我只会有一百多棵树（但树不是固定的：我无法提前知道树的外观，否则简单地手动对每棵树进行硬编码将是微不足道的）。

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

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

4

3 回答 3

3

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

你可能想分析它，统计

  • 哪个 AND 分支评估为假
  • 哪个 OR 分支结果为真

然后，您可以根据在分析步骤中找到的权重对树进行重新排序。如果你想/需要特别漂亮，你可以设计一种机制来检测运行时某个数据集的权重，这样你就可以动态地重新排序分支。

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

我希望所有这些都有意义，因为我意识到散文版本很密集。但是，就像 Fermat 所说的那样，代码示例太大而无法容纳此页边距:)

于 2011-04-11T12:47:25.080 回答
3

有一种简单快捷的方法可以在 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 倍）。

于 2011-04-11T17:14:51.790 回答
1

我认为您的字节编码想法是正确的方向。无论语言如何，我都会做的是编写一个预编译器。它会遍历每棵树，并使用打印语句将其翻译成源代码，例如。

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

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

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

于 2011-04-11T15:45:44.760 回答