java - 优化 boolean 逻辑树评估

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[] 数组中的一位)，要么节点不是叶子，因此引用多个子节点。

它们很简单，但可以表达复杂的 boolean 表达式。效果很好。

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

所以我需要遍历树并回答 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 倍” 加速——是为每棵树生成字节码，并且将每棵树的逻辑硬编码到一个类中。它应该工作得很好，因为我只会有一百棵左右的树(但树不是固定的:我无法提前知道树的样子，否则手动硬编码每棵树是微不足道的).

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

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

Answer 1

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

你可能想分析它，统计

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

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

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

我希望所有这些都是有道理的，因为我意识到散文版本很密集。然而，就像 Fermat 所说的那样，代码示例太大，无法放入这个边距:)