评估数学表达式的最佳算法？

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

我将用Delphi或C#编写这个.我已经通过使用分流码算法编写了类似的东西,但每次我需要计算相同的公式时,我必须经历解析阶段.必须有更好的方法来做到这一点.

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

无论如何,它的工作原理可能对您有所帮助.表达式的递归下降解析很容易,通过构建树,您可以多次评估而无需重新解析.JclExprEval实际上为一个简单的堆栈机器生成代码,因此它可以比树解释更快地工作; 堆栈计算机在很大程度上将其内存操作限制为数组并使用开关用于操作码,而树解释遵循整个堆中的链接,并且通常使用虚拟调度(或双重调度)作为操作码,因此它们通常会变慢.

采用与JclExprEval解析相同的方法但用C#编写,并Expression像Marc建议的那样建立一个非常有效的方法.JIT编译的表达式应该比解释的表达式程序或树快得多,它们本身比解析快得多.

在C#with .NET 3.5中,您可以使用Expression它; 您可以构建一个参数化表达式,然后将其编译为委托.这正是我为Finguistics的数学方面所做的.如果你想要它,我仍然有我使用的解析代码......

我使用的主要技巧是保持委托类型已知,我使用数组作为输入类型 - 将不同的args视为arr [0],arr 1,arr [2]等.这意味着我可以编译为(例如) )a Func(取一个decimals 数组,返回a decimal).

一旦你打电话Compile(),这就好像你有代码直接做到这一点.

(编辑)

作为Expression以这种方式使用的简短示例(具有硬编码功能),请参见下文.我已经编写的解析器目前用作谓词检查器 - 即检查"？+(2*？ - ？)= 22 +？" - 但是改变它以返回结果并不难(并引入更多操作,比如sin/ pow/ etc - 可能是通过将它们直接映射到辅助对象上的公共方法(via Expression.Call)).

using System;
using System.Linq.Expressions;
static class Program
{
    static void Main()
    {
        var args = Expression.Parameter(typeof(float[]), "args");
        var x = Expression.ArrayIndex(args, Expression.Constant(0));
        var y = Expression.ArrayIndex(args, Expression.Constant(1));
        var add = Expression.Add(x, y);
        var lambda = Expression.Lambda>(add, args);

        Func func = lambda.Compile();
        Console.WriteLine(func.Call(1, 2));
        Console.WriteLine(func.Call(3, 4));
        Console.WriteLine(func.Call(5, 6));
    }

    static T Call(this Func func, params T[] args)
    { // just allows "params" usage...
        return func(args);
    } 
}