c++ - 如何优化此后缀表达式树以提高速度？

Question

感谢我在 this 中得到的帮助帖子:

我有一个漂亮、简洁的递归函数来按后缀顺序遍历树:

deque <char*> d;
void Node::postfix()
{
    if (left != __nullptr) { left->postfix(); } 
    if (right != __nullptr) { right->postfix(); } 
    d.push_front(cargo);
    return;
};

这是一个表达式树。分支节点是从数组中随机选择的运算符，叶节点是值或变量'x'，也是从数组中随机选择的。

char *values[10]={"1.0","2.0","3.0","4.0","5.0","6.0","7.0","8.0","9.0","x"};
char *ops[4]={"+","-","*","/"};

因为在它所属的遗传算法运行期间将被调用数十亿次，所以我想优化它以提高速度。我有很多关于这个主题的问题，我会在单独的帖子中提出。

首先是:我怎样才能访问每一个被发现的“ cargo ”。也就是说:我不想将“ cargo ”推到双端队列上，然后处理双端队列以获取值，而是立即开始处理它。

编辑:This问题表明，事后处理双端队列是更好的方法。

我还不知道 C++ 中的并行处理，但理想情况下这将在两个不同的处理器上同时完成。

在 python 中，我将函数设为生成器并使用 .next() 访问后续的“ cargo ”。

参见上面的编辑。

但我正在使用 C++ 来加速 Python 的实现。我在想这种树已经存在很长时间了，而且可能有人已经对其进行了优化。有任何想法吗？谢谢

Answer 1

当然，在您在这里进行优化之前，您首先要衡量成本开销，因为您的遗传算法下一代生产和突变可能会占用评估时间。

一旦您确定要优化...显而易见的答案是编译表达式(“尽可能多”)。幸运的是，有很多方法可以“编译”。

如果你在 Python 中实现这个，你可以让 Python(我不是专家)将构造的抽象语法树编译成一个函数，这可能会快很多，特别是如果 CPython 支持这个.

但是，您似乎是在 C++ 中实现它。在那种情况下，我不会像您定义的那样评估表达式树，因为这意味着大量的树遍历、间接函数调用等非常昂贵。

一个俗气的技巧是将实际表达式吐出为文本字符串，并在其周围添加适当的 C++ 函数体文本到一个文件中，然后在该文件上启动 C++ 编译器。您可以使用足够的脚本魔法自动执行所有的 spit-compile-relink，这样如果你很少这样做，这会起作用，你会尽快获得表达式评估机器可以做到。

假设您不想那样做，我很想在您开始评估过程之前遍历您的表达式树，并将该树“编译”为一组 Action 存储在称为“代码”的线性数组中。这些操作将由枚举定义:

enum actions {
   // general actions first
   pushx,  // action to push x on a stack
   push1,
   push2,  // action to push 2 on a stack
   ...
   pushN,
   add,
   sub,  
   mul,    // action multiply top two stack elements together
   div,
   ...
   // optimized actions
   add1,
   sub1,
   mul1,
   div1,   // action to divide top stack element by 1
   ...
   addN,
   subN,
   ...
   addx,
   subX,
   ...
 }

在本例中，我定义了实现下推堆栈表达式计算器的操作，因为这很容易理解。幸运的是，您的表达式词汇量非常有限，因此您的操作也可能非常有限(如果您有任意变量或常量，它们会更复杂)。

表达式 ((x*2.0)+x)-1 将由一系列 Action 执行

 pushx
 mul2
 addx
 sub1

可能很难比这更好。

人们可能会根据多寄存器 CPU 的模型定义操作来实现面向寄存器的表达式求值器；这将使执行速度更快(我猜是两倍，但前提是表达式变得非常复杂)。

你想要的是涵盖你需要做的最一般计算的 Action (这样你总是可以选择一个有效的 Action 序列，而不管你的原始表达式)和你遇到的表达式中经常出现的 Action (add1 在机器代码，不知道你的统计数据是什么样的，你说你正在进行遗传编程表明你不知道统计数据是什么，但你可以以某种方式测量它们或做出有根据的猜测)。

你的内部评估循环看起来像(这里的语法很草率):

float stack[max_depth];
stack_depth=0;
for (i=1;i<expression_length;i++)
{
   switch (code[i])  // one case for each opcode in the enum
   {
    case pushx: stack[stack_depth++]=x;
               break;
    case push1: stack[stack_depth++]=1;
               break;
           ...
    case add:   stack[stack_depth-1]+=stack[stack_depth];
               stack_depth--;
               break;
           ...
    case subx:  stack[stack_depth]-=x;
               break;
           ...
    }
}
// stack[1] contains the answer here

上面的代码为下推堆栈表达式计算器实现了一个非常快速的“线程解释器”。

现在“所有”你需要做的就是生成代码数组的内容。你可以这样做通过使用你原来的表达式树，执行你原来的递归表达式树遍历，但不是进行表达式评估，而是将你当前表达式评估器将执行的操作写入代码数组，并在你找到它们时吐出特殊情况操作(这相当于“窥孔优化”)。这是树的经典编译，您几乎可以在任何编译器书籍中找到更多关于如何执行此操作的信息。

是的，这是相当多的工作。但是后来，您决定运行一种计算成本非常高的遗传算法。