7

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

我选择编写解析器的方法是使用 Shunting-Yard 算法转换 RPN 中的表达式，将像“cos”这样的原始函数视为一元运算符。这意味着上面编写的函数将转换为一系列标记，例如：

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

问题是要绘制函数，我必须多次评估它，因此对每个输入值应用堆栈评估算法效率非常低。我该如何解决这个问题？我必须忘记 RPN 的想法吗？

4

9 回答 9

3

“很多次”是多少？一百万？

可以输入什么样的功能？我们可以假设它们是连续的吗？

您是否尝试过衡量您的代码的执行情况？

（对不起，从问题开始！）

您可以尝试下面简要描述的两种方法之一（或两者）（可能还有更多）：

1）解析树。

您可以创建一个解析树。然后做大多数编译器所做的优化表达式、常量折叠、公共子表达式消除（您可以通过将公共表达式子树链接在一起并缓存结果来实现）等。

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

    *
   / \
  A   B

其中 A 评估为 0，您可以完全避免评估 B，因为您知道结果为 0。使用 RPN，您将失去惰性评估。

2) 插值

假设您的函数是连续的，您可以使用Polynomial Interpolation以高精度逼近您的函数。这样，您可以对函数进行几次复杂的计算（根据您选择的多项式次数），然后在其余时间进行快速多项式计算。

要创建初始数据集，您可以只使用方法 1 或坚持使用您的 RPN，因为您只会生成几个值。

所以如果你使用插值，你可以保持你的 RPN ......

希望有帮助！

于 2010-02-10T21:07:10.090 回答
2

为什么要重新发明轮子？请改用快速脚本语言。将 lua 之类的东西集成到您的代码中将花费很少的时间并且非常快。

您通常可以对表达式进行字节编译，这应该会导致代码运行得非常快，对于简单的一维图来说肯定足够快。

我推荐 lua 速度快，并且比任何其他脚本语言更容易与 C/C++ 集成。另一个不错的选择是 python，但虽然它更广为人知，但我发现集成起来更棘手。

于 2010-02-10T22:37:28.503 回答
1

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

这样，您可以解析一次表达式，保留解析树，获取输入数组，然后应用解析树进行评估。

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

于 2010-02-10T19:56:48.390 回答
1

我所做的是使用分流算法来生成 RPN。然后，我将 RPN “编译”为可以重复执行（解释性）而不重新解析表达式的标记化形式。

于 2010-02-10T22:45:36.653 回答
1

Michael Anderson 建议使用Lua。如果你想尝试 Lua 来完成这个任务，请参阅我的ae库。

于 2010-02-20T00:11:35.463 回答
0

什么意义上的低效？有机器时间和程序员时间。是否有标准以特定复杂程度运行它需要多快？完成任务并继续下一个任务是否更重要（完美主义者有时永远不会完成）？

所有这些步骤都必须针对每个输入值进行。是的，您可以有一个启发式方法来扫描操作列表并对其进行一些清理。是的，您可以将其中的一些编译成程序集，而不是调用 +、* 等作为高级函数。您可以将向量化（执行所有 + 和所有 * 等，与值向量）与一次针对一个值执行整个过程进行比较。但是你需要吗？

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

于 2010-02-10T20:11:01.353 回答
0

您对 RPN 的简单解释应该可以正常工作，尤其是因为它包含

  • 数学库函数，如cos,exp和^(pow, 涉及日志)

  • 符号表查找

希望您的符号表（其中包含诸如 x 之类的变量）将简短而简单。

库函数很可能是你最耗时的，所以除非你的解释器写得不好，否则不会有问题。

但是，如果您真的要追求速度，您可以将表达式转换为 C 代码，即时编译并将其链接到 dll 中并加载它（大约需要一秒钟）。再加上数学函数的记忆版本，可以为您提供最佳性能。

PS 对于解析，您的语法非常简单，因此一个简单的递归下降解析器（大约一页代码，O(n) 与 shunting-yard 相同）应该可以正常工作。实际上，您可能只能够在解析时计算结果（如果数学函数占用大部分时间），而不必为解析树、RPN 等任何东西而烦恼。

于 2010-02-12T02:20:29.707 回答
0

我认为这个基于 RPN 的库可以达到目的：http ://expressionoasis.vedantatree.com/

我将它与我的一个计算器项目一起使用，效果很好。它小而简单，但可扩展。

于 2010-10-29T18:37:10.707 回答
0

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

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

从 RPN 到 3-address 的转换应该很容易，因为 3-address 是一种概括。

于 2010-10-30T02:03:59.237 回答