c# - ¿El mejor algoritmo para evaluar una expresión matemática?

algorithm delphi

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í.

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

En C # con .NET 3.5, puede usar Expression para esto; 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 quieres ...

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 pude compilar (por ejemplo) ) a Func<decimal[], decimal> (toma una matriz de decimal , devuelve un decimal ).

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

(editar)

Como un breve ejemplo del uso de Expression de esta manera (con una función codificada), consulte a continuación. El analizador que ya he escrito funciona actualmente como un corrector de predicados , es decir, para verificar que "? + (2 *? -?) = 22 +?" - pero no sería difícil cambiarlo para devolver el resultado (e introducir más operaciones, como sin / pow / etc - presumiblemente al mapearlas 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);
    } 
}

Answer 2

Si desea hacerlo con Delphi, podría analizar cómo funciona la unidad JclExprEval , que forma parte de la Biblioteca de códigos JEDI . 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.

Tomar el mismo enfoque que JclExprEval en el análisis, pero escrito en C #, y crear una 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.