Syn*_*r0r 5 java optimization boolean-logic bytecode-manipulation
我有很多真/假结果保存为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();
}
基本上,Node是一个叶子,然后有一个条件号(匹配long []数组中的一个位)或者Node不是叶子,因此引用了几个子节点.
它们很简单,但它们允许表达复杂的布尔表达式.它很棒.
到目前为止一切都很好,一切都很好.但是我确实有一个问题:我需要评估很多表达式,确定它们是真还是假.基本上我需要对一个问题进行一些暴力计算,而这个问题除了暴力破解之外还没有比这更好的解决方案.
所以我需要走树然后回答,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"加速 - 将为每个树生成字节码,并将每个树的逻辑硬编码到一个类中.它应该工作得很好,因为我只会有一百棵左右的树(但是树木没有修复:我事先无法知道树木会是什么样子,否则简单地手工编写每棵树都是微不足道的).
除了为每棵树生成字节码之外还有什么想法？
现在,如果我想尝试字节码生成路由,我应该怎么做呢？
为了最大化捷径评估的机会，您需要进行自己的分支预测。
您可能想要对其进行分析，统计
然后，您可以相对于在分析步骤中找到的权重对树重新排序。如果您想要/需要特别聪明，您可以设计一种机制来在运行时检测特定数据集的权重，以便您可以动态地重新排序分支。
请注意，在后一种情况下，建议不要对实际树重新排序（相对于仍在执行时的存储效率和结果的正确性），而是设计一个能够本地排序的树节点访问者（遍历算法）根据“实时”权重来划分分支。
我希望这一切都有意义，因为我意识到散文版本很密集。然而，就像 Fermat 所说，代码示例太大，无法容纳在这个边距中:)