我有很多作为位保存在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”速度提升--是为每个树生成字节码,并将每个树的逻辑硬编码到类中。 这应该能很好地工作,因为我只会有一百个左右的树(但树不固定:我事先无法知道树的外观,否则手动硬编码每个树将变得微不足道)。
除了为每个树生成字节码之外,还有什么想法?
现在,如果我想尝试字节码生成路线,我应该怎么做呢?