0

我什至不确定这是否适合提出这样的问题。

作为我的硕士论文的一部分，我正在做一些并行算法的事情。简单地说，我正在做的事情的一部分是并行评估数千个表达式树（表达式如sin(exp (x + y) * cos (z))）。我现在正在做的是将这些表达式树转换为前缀/后缀表达式，并使用常规方法（堆栈、递归等）评估它们。这些是我们在数据结构和基础计算机科学课程中学到的基本知识。

我想知道是否还有其他东西可以用来代替表达式树来处理表达式。我知道编译器在解析阶段大量使用表达式树，所以我假设没有表达式树的替代品（否则有人会在编译器中使用它）。
此类表达式是否有任何替代评估方法（而不是堆栈和递归）。更“并行”友好的东西？用堆栈解析这样的表达式是顺序的，并且会在并行系统中产生瓶颈。（我的工作也可以接受异国/怪异/理论方法 - 如果有的话）

4

1 回答 1

2

我认为评估表达式树是可并行的，您只是不要将它们转换为前缀或后缀形式。

例如，您给出的表达式的树如下所示：

   sin
    |
    *
   / \
 exp cos
  |   |
  +   z
 / \
x   y

当您遇到 时*，您可以评估exp一个线程上的cos子表达式和另一个线程上的子表达式。（假设您的编程语言支持它们，您可以在这里使用future来简化代码。）

尽管如果您的表达式真的像这个一样简单并且您有数千个表达式，那么我看不出您需要并行评估单个表达式的任何理由。对表达式本身进行并行处理应该绰绰有余（例如，对于 1000 个表达式和 2 个内核，在一个内核上计算 500，在另一个内核上计算其余部分）。

于 2013-05-23T11:55:42.623 回答