基于栈的表达式求值在数学解析中的效率

Question

我需要为学术目的编写一个应用程序，可以绘制用户输入的表达式，例如：f(x) = 1 - exp(3^(5*ln(cosx)) + x)

我选择使用Shunting-Yard算法将表达式转换为逆波兰表达式，并将原始函数（如“cos”）视为一元运算符。这意味着上面的函数将被转换为一系列标记，例如：

1, x, cos, ln, 5, *,3, ^, exp, -

问题在于为了绘制函数，我必须多次评估它，因此对每个输入值应用堆栈评估算法将非常低效。

我该如何解决这个问题？我需要放弃逆波兰表达式的想法吗？

- Davide Valdo

---

@Dave：你打算用什么编程语言来完成这个任务？ - t0mm13b

如果他用PERL做的话，他可以直接使用eval() :-) - Paul

你认为堆栈评估算法为什么会非常低效？你有计时吗？使用堆栈算法生成一系列执行步骤如何？ - David Thornley

我不明白为什么这个方法效率低下。除了像一个答案建议的那样动态生成和编译C代码之外，你必须将表达式存储在某种数据结构中。逆波兰数组似乎是最有效的数据结构。调用脚本语言只会做同样的事情。 - Austin Taylor

“逆波兰表达式的‘堆栈求值算法’正是计算机使用的算法，也是编译器生成目标代码的算法。如果它效率低下，那么这种情况就不会存在。” - user207421

Answer 1

“LOTS of times”指的是多少次？一百万次吗？

输入的函数种类是什么？我们可以假设它们是连续的吗？

你尝试过测量你的代码表现吗？

（对不起，一开始就问了这么多问题！）

你可以尝试下面简要描述的两种方法（或两种都尝试）（也可能有更多方法）：

1) 解析树。

您可以创建一个解析树。然后进行大多数编译器用于优化表达式的操作，如常量折叠、公共子表达式消除（可以通过链接公共表达式子树并缓存结果来实现），等等。

然后，您可以使用惰性求值技术来避免整个子树。例如，如果您有一棵树

    *
   / \
  A   B

当A的值为0时，你可以完全避免评估B，因为你“知道”结果是0。使用逆波兰表示法，你将错失惰性评估。

2) 插值

假设你的函数是连续的，你可以使用多项式插值来高度精确地近似你的函数。这样，你只需要进行几次复杂的函数计算（基于你选择的多项式阶数），然后就可以快速地进行多项式计算。

要创建初始数据集，你可以只使用方法1或坚持使用逆波兰表示法，因为你只需要生成一些值。

因此，如果使用插值，你可以保留你的逆波兰表示法...

希望有所帮助！

- Aryabhatta

---

"LOTS of times" 意味着如果我的图形X从-10到15，我会执行以下操作：h = 0.001; for (x = -10; x <= 15; x += 0.001) { y = expression.evaluate(x); // 绘制结果 }这将包含25,000个函数调用，而且每次调整绘图大小时都必须重新绘制。无论如何，我认为解析树可能是正确的方法。谢谢您的帮助。 - Davide Valdo

我认为，多项式插值比转向解析树更可能给出显著结果，而且付出的努力可能是值得的（实际上，将会有免费的软件包可用于此）。顺便问一下，为什么重绘会导致重新评估？难道你不能只是存储它们并再次使用吗？ - Aryabhatta

为什么你想要25000个x来制作你的图，而屏幕可能只有1920x1080呢？或者你的媒体是其他的吗？ - Paul

Answer 2

为什么要重复发明轮子？使用快速脚本语言吧。将像lua这样的东西集成到您的代码中所需的时间非常短，且速度非常快。

通常情况下，您可以将表达式进行字节编译，这应该会产生非常快的代码，对于简单的1D图形来说速度足够快了。

我推荐使用lua，因为它很快，并且比任何其他脚本语言更容易与C/C++集成。另一个不错的选择是Python，但是虽然它更为人所知，但我发现它更难集成。

- Michael Anderson

Answer 3

为什么不保留一个解析树（我宽泛地使用“树”这个词，对于您的情况，它是一系列操作），并相应地标记输入变量？（例如，对于输入x、y、z等，用0注释“x”表示第一个输入变量，“y”用1表示第二个输入变量，以此类推。）

这样，您可以解析表达式一次，保留解析树，接受输入数组，并将解析树应用于求值。

如果您担心评估步骤（与解析步骤相比）的性能方面，除非您进入矢量化（一次在输入向量上应用解析树）或将操作硬编码到固定函数中，否则我认为您不会做得更好。

- Jason S

---

我明白你的意思，但我已经通过将RPN标记保留在我的“Function”类（基本上是解析树）中来解决了第一个问题。实际上，问题仅涉及评估例程的性能。 - Davide Valdo

Answer 4

我所做的是使用逆波兰表达式算法生成RPN。然后，我将RPN“编译”成可以重复执行（解释性地）的令牌化形式，无需重新解析表达式。

- anon

---

这正是我打算做的，只是我担心评估步骤的性能。 - Davide Valdo

Answer 5

Michael Anderson建议使用Lua。如果您想尝试仅针对此任务使用Lua，请查看我的ae库。

- lhf

Answer 6

一种优化方法是用值数组替换堆栈，并将求值器实现为三地址机，其中每个操作从两个（或一个）位置加载并保存到第三个位置。这可以生成非常紧凑的代码：

struct Op {
  enum {
    add, sub, mul, div,
    cos, sin, tan,
   //....
  } op;
  int a, b, d;
}

void go(Op* ops, int n, float* v) {
  for(int i = 0; i < n; i++) {
    switch(ops[i].op) {
      case add: v[op[i].d] = v[op[i].a] + v[op[i].b]; break;
      case sub: v[op[i].d] = v[op[i].a] - v[op[i].b]; break;
      case mul: v[op[i].d] = v[op[i].a] * v[op[i].b]; break;
      case div: v[op[i].d] = v[op[i].a] / v[op[i].b]; break;
      //...
    }
  }
}

从逆波兰表达式到三地址码的转换应该很容易，因为三地址码是一种泛化的形式。

- BCS

Answer 7

在哪方面效率低下？有机器时间和程序员时间。有没有标准来确定它需要以特定的复杂度运行得有多快？完成任务并继续下一个任务重要还是（完美主义者有时永远无法完成）？

对于每个输入值，都必须执行所有这些步骤。是的，您可以拥有一种启发式方法来扫描操作列表并稍微清理它一下。是的，您可以将其中的一些编译成汇编代码，而不是调用+、*等作为高级函数。您可以将矢量化（对一系列值执行所有'+'然后所有'*'等操作）与逐个值执行整个过程进行比较。但是你需要吗？

我的意思是，如果在gnuplot或Mathematica中绘制函数会发生什么？

- Paul

---

我相信这些应用程序使用更复杂和精细的解析技术。堆栈评估算法是O(n)，但由于表达式必须经常进行评估（例如每次调整绘图大小），因此必须优化算法。 - Davide Valdo

向量化是一个真正的宝石，如果你知道所有的x，当你想要y时。或者你可以输入一个等间距的x序列，取出y并进行插值。 - Paul

Answer 8

你对RPN的简单解释应该可以很好地工作，特别是因为它包含了：

• 数学库函数，如cos、exp和^(pow，涉及对数)

• 符号表查找

希望你的符号表（像x这样的变量）会很短而简单。

库函数很可能是你最耗时的部分，所以除非你的解释器编写得很差，否则这不会成为问题。

然而，如果你真的需要速度，你可以将表达式转换为C代码，即时编译并链接成dll文件，然后加载它（大约需要一秒钟）。这样做，再加上数学函数的记忆化版本，可以给你最佳的性能。

P.S. 对于解析，你的语法相当基本，因此一个简单的递归下降解析器（大约一页代码，O(n)与shunting-yard相同）应该可以很好地工作。实际上，你可能只需在解析时计算结果（如果数学函数占用了大部分时间），而不必担心解析树、RPN或任何其他东西。

- Mike Dunlavey

Answer 9

我认为这个基于逆波兰表达式的库可以满足需求：http://expressionoasis.vedantatree.com/

我在我的计算器项目中使用过它，效果很好。它小巧简单，但可扩展性强。

- Kaouni