优化布尔逻辑树计算

6

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

除了为每个树生成字节码之外,还有什么想法?

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


对于好奇的人,我的 Node 实现与这个差不多:https://dev59.com/I0rSa4cB1Zd3GeqPXpvU - SyntaxT3rr0r
一个显而易见的事情是尽早进行短路运算(例如,FALSE AND 任何东西都是 FALSE,TRUE OR 任何东西都是 TRUE)。我假设你已经在这方面做到了? - Jeff Foster
1
@Jeff Foster:好的,我正在做 :) 但是有些树可能相对较大,由许多OR语句组成,只有很少的AND语句,因此即使使用短路计算,我仍然希望改进这个问题。 :) - SyntaxT3rr0r
如果您认为将树预编译成字节码是可行的,那么请尽可能地生成机器指令(使用JNI在C中)。在汇编语言中,bool域足够简单,可以使风险/收益权衡达到工作状态,我个人认为。 - sehe
您是否正在使用多组值评估同一棵树? - phkahler
3个回答

4
为了最大化快捷评估的机会,您需要进行自己的分支预测。
您可能希望对其进行分析,统计:
- 哪些AND分支计算为false - 哪些OR分支计算为true 然后,您可以根据在分析步骤中找到的权重重新排序树。如果您想/需要特别聪明,可以设计一种机制,在运行时检测某个数据集的加权值,以便您可以动态地重新排序分支。
请注意,在后一种情况下,建议不要重新排序实际的树(考虑存储效率和执行时结果的正确性),而是设计一个树节点访问者(遍历算法),能够根据“活”权重本地排序分支。
我希望这一切都有意义,因为我意识到散文版本很密集。但是,就像费马定理一样,代码示例太大了,无法放入此边距中 :)

很棒的答案,但是......长long[]数组和树都是动态生成的。您建议的分析仍然适用吗?例如,我可以将其与字节码生成相结合吗? - SyntaxT3rr0r
事物的动态性使得一般情况下很难进行任何预测。你可能会从仅优化恒定性能成本(即按原样编译为字节码/汇编)中获得更好的成本效益。 - sehe

3

在C语言中,有一种简单快速的方法来评估布尔运算,比如这样的操作:假设你想要计算z=(x op y),你可以这样做:

 z = result[op+x+(y<<1)];

所以如果要选择AND、OR、XOR等操作,OP值必须是4的倍数。你需要为所有可能的答案创建一个查找表。如果这个表足够小,你可以将其编码成一个单一的值,并使用右移和掩码来选择输出位:

z = (MAGIC_NUMBER >> (op+x+(y<<1))) & 1;

那将是评估大量这些的最快方法。当然,您必须将具有多个输入的操作拆分为每个节点仅具有2个输入的树形结构。没有简单的方法来短路此过程。但是,您可以将树转换为列表,其中每个项目包含操作号和指向2个输入和输出的指针。一旦以列表形式呈现,您就可以使用单个循环非常快地通过该行一百万次。

对于小树,这是胜利的。对于具有短路的较大树,这可能不是胜利,因为需要评估的平均分支数从2增加到1.5,这对于大树来说是一个巨大的胜利。你的情况可能会有所不同。
编辑: 经过深思熟虑,您可以使用类似跳表的东西来实现短路。每个操作(节点)都将包括比较值和跳过计数。如果结果匹配比较值,则可以绕过接下来的跳过计数值。因此,该列表将从树的深度优先遍历中创建,并且第一个子元素将包括与另一个子元素大小相等的跳过计数。这会使每个节点评估变得更加复杂,但允许短路。谨慎的实现可以在不进行任何条件检查的情况下完成它(考虑跳过计数的1或0倍)。

这种东西让我非常怀念我的汇编和C语言时代。可惜我现在“被困在Java中” :( 但是对于这个绝对好的答案,点赞+1! - SyntaxT3rr0r
@SyntaxT3rr0r:谢谢。我曾经用过这个来进行数字逻辑模拟。请看编辑部分,了解如何使用列表进行短路测试;-) - phkahler

1

我认为你的字节编码想法是正确的方向。 无论使用哪种语言,我会编写一个预编译器。 它将遍历每个树,并使用打印语句将其转换为源代码,例如。

((word&1) && ((word&2) || ((word&4) && (word&8))))

每当树发生变化时,它可以即时编译,并加载生成的字节码/dll,这一切只需要不到一秒钟。

问题在于,目前您正在解释树的内容。将它们转换为已编译的代码应该使它们运行速度提高10-100倍。

针对您在评论中提到没有JDK的情况,我建议尝试编写自己的字节码解释器,以尽可能快的速度运行。它可能看起来像这样:

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

这个想法是让编译器将开关转换为跳转表,以便用最少的周期执行每个操作。要生成操作码,只需对树进行后缀遍历。

除此之外,你可能可以通过对德摩根定律进行一些操作来简化它,这样你就可以一次检查多个位。


好的,谢谢 :) 那我就尝试学习Java的ASM字节码库,看看会有什么结果 :) - SyntaxT3rr0r
@SyntaxT3rr0r:你可以这样做,但我不会。我会生成源代码,让编译器生成低级别的东西。这样已经足够快了。 - Mike Dunlavey
很遗憾,我可能无法完全控制这台机器上安装的JDK(如果有的话),它将在其上运行 :( - SyntaxT3rr0r
@SyntaxT3rr0r:好的,这会让事情变得更加困难。Java字节码将是您的下一个最佳选择。如果您无法做到这一点,那么您可能需要制作自己的解释器,就像我上面所概述的那样。 - Mike Dunlavey
我喜欢你的编辑...但是我检查了一下,Java的ASM库似乎只有50 KB。我现在不知道哪个更好。我会评估两个选项:) 但我认为,出于方便起见,我会先从你在编辑中建议的开始。 :) - SyntaxT3rr0r

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接