¿Mejor algoritmo para evaluar una expresión matemática?

Question

¿Cuál es el mejor algoritmo para evaluar una expresión matemática? Me gustaría poder optimizar esto un poco en el sentido de que puedo tener una fórmula con varias variables, que puedo necesitar para evaluar cientos de veces con diferentes variables. Entonces, básicamente, si puedo analizar inicialmente la fórmula para que esté optimizada de alguna manera, y luego puedo pasar las variables a esta versión optimizada tantas veces como lo necesite, cada vez que produzca un resultado para mí.

Voy a escribir esto en Delphi o C#. Ya he escrito algo similar usando el algoritmo de yarda de maniobras, pero cada vez que necesito calcular la misma fórmula, tengo que pasar por la etapa de análisis sintáctico. Debe haber una mejor manera de hacer esto.

Answer 1

Si quiere hacerlo con Delphi, usted podría mirar en cómo funciona la unidad JclExprEval, parte de la JEDI Code Library. Lo escribí hace varios años (está un poco sobrediseñado); analiza funciones y variables y puede devolverte un puntero de método que evalúa la expresión rápidamente. Pase las variables por referencia, y puede cambiarlas directamente y la expresión reevaluada se calculará en consecuencia.

En cualquier caso, los conceptos básicos de cómo funciona pueden ser útiles para usted. El análisis de expresiones de descendencia recursiva es fácil, y al construir un árbol puede evaluar varias veces sin volver a analizar. JclExprEval en realidad genera código para una máquina de pila simple, por lo que puede funcionar un poco más rápido que la interpretación de árbol; las máquinas apiladoras restringen en gran medida sus operaciones de memoria a matrices y usan conmutadores para códigos de operación, mientras que la interpretación de árbol sigue enlaces en todo el montón y a menudo utiliza despacho virtual (o doble despacho) para códigos de operación, por lo que generalmente terminan más despacio.

Tomando el mismo enfoque que JclExprEval en el análisis, pero escrito en C#, y construyendo un Expression, como sugiere Marc, es otro enfoque perfectamente válido. La expresión compilada JIT debe ser bastante más rápida que un árbol o programa de expresión interpretado, que a su vez es mucho más rápido que el análisis.

Answer 2

En C# con .NET 3.5, se puede utilizar para este Expression; puedes construir una expresión parametrizada y luego compilarla a un delegado. Esto es exactamente lo que hice para el aspecto matemático de Finguistics. Todavía tengo el código de análisis que usé si lo deseas ...

El truco principal que utilicé fue que para mantener el tipo de delegado conocido, utilicé una matriz como tipo de entrada - tratando diferentes argumentos como arr [0] , arr 1, arr [2] etc. Esto significa que podría compilar a (por ejemplo) un Func<decimal[], decimal> (toma una matriz de decimal s, devuelve un decimal).

vez que haya llamado Compile(), esto es pertty tanto como si tuviera código para hacerlo directamente.

(edit)

Como un breve ejemplo de la utilización de Expression de esta manera (con una función de codificación fija), véase más adelante. El analizador ya he escrito actualmente funciona como un predicado corrector - es decir, para comprobar que "+ (2 *? -?)?? = 22 +" - pero no sería difícil cambiarlo para devolver el resultado (e introducir más operaciones, como sin/pow/etc - supuestamente asignándolas directamente a métodos públicos en un objeto auxiliar (a través de 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<Func<float[], float>>(add, args); 

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

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