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

感谢我在 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 实现。我想这种树已经存在很长时间了，可能已经有人对其进行了优化。有任何想法吗？谢谢

最佳答案

假设处理 cargo 足够昂贵，锁定互斥锁相对便宜，您可以在将项目放入队列时使用单独的线程来访问队列。

线程 1 将执行您当前的逻辑，但它会在添加项目之前锁定队列的互斥锁，然后将其解锁。

然后线程 2 将永远循环，检查队列的大小。如果它不为空，则锁定队列，拉出所有可用 cargo 并进行处理。重复循环。如果没有 cargo 可用，则 sleep 一小段时间并重复。

如果锁定太昂贵，您可以建立一个队列队列:首先将 100 个项目放入一个 cargo 队列，然后将该队列放入一个锁定队列(如第一个示例)。然后开始一个新的“本地”队列并继续。

关于c++ - 如何优化此后缀表达式树以提高速度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2772817/