评估数学表达式的最佳算法? [英] Best algorithm for evaluating a mathematical expression?

问题描述

评估数学表达式的最佳算法是什么?我希望能够稍微优化一下，因为我可能有一个包含各种变量的公式，我可能需要使用不同的变量对其进行数百次评估.所以基本上，如果我可以最初解析公式，以便以某种方式对其进行优化，然后我可以根据需要多次将变量传递给这个优化版本，每次都会为我生成结果.

What's the best algorithm for evaluating a mathematical expression? I'd like to be able to optimize this a little in the sense that I may have one formula with various variables, which I may need to evaluate hundreds of times using different variables. So basically if I can initially parse the formula so that it is optimized in some way, and I can then pass in the variables to this optimized version as many times as I need, each time it produces a result for me.

我将使用 Delphi 或 C# 编写此代码.我已经使用调车码算法写过类似的东西，但是每次我需要计算相同的公式时，我都必须经过解析阶段.必须有更好的方法来做到这一点.

I'll be writing this in either Delphi or C#. I have already written something similar by using the shunting yard algorithm, but each time I need to calculate the same formula, I'm having to go through the parsing stage. There must be a better way to do this.

推荐答案

如果你想用 Delphi 来做，你可以看看 JclExprEval 单元是如何工作的，它是 JEDI 代码库.我几年前写的(有点过度设计)；它解析函数和变量，并可以返回一个快速计算表达式的方法指针.通过引用传入变量，你可以直接改变它们，重新计算的表达式会相应地计算.

If you want to do it with Delp you could look into how the JclExprEval unit works, part of the JEDI Code Library. I wrote it several years ago (it's a little over-engineered); it parses functions and variables and can hand you back a method pointer which evaluates the expression quickly. Pass the variables in by reference, and you can change them directly and the re-evaluated expression will be calculated accordingly.

无论如何，其工作原理的基础知识可能对您有所帮助.表达式的递归下降解析很容易，通过构建一棵树，您可以多次求值而无需重新解析.JclExprEval 实际上为一个简单的堆栈机生成代码，因此它的工作速度比树解释快一点；堆栈机器在很大程度上将它们的内存操作限制在数组，并使用开关操作码，而树解释遵循整个堆的链接，并且经常对操作码使用虚拟分派(或双分派)，因此它们通常最终会变慢.

In any case, the basics of how it works may be helpful for you. Recursive-descent parsing of expressions is easy, and by building a tree you can evaluate multiple times without re-parsing. JclExprEval actually generates code for a simple stack machine, so that it can work a little faster than tree interpretation; stack machines largely restrict their memory operations to arrays and use switches for opcodes, while tree interpretation follows links throughout the heap and often uses virtual dispatch (or double-dispatch) for opcodes, so they usually end up slower.

在解析中采用与 JclExprEval 相同的方法，但用 C# 编写，并像 Marc 建议的那样构建 Expression，是另一种完全有效的方法.JIT 编译的表达式应该比解释的表达式程序或树快很多，它们本身比解析要快得多.

Taking the same approach as JclExprEval in parsing but written in C#, and building up an Expression, like Marc suggests, is another perfectly valid approach. The JIT-compiled expression ought to be quite a bit faster than an interpreted expression program or tree, which themselves are a lot faster than parsing.

这篇关于评估数学表达式的最佳算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！