Najlepszy algorytm do oceny wyrażenia matematycznego?

Question

Jaki jest najlepszy algorytm oceny wyrażenia matematycznego? Chciałbym być w stanie zoptymalizować to trochę w tym sensie, że mogę mieć jedną formułę z różnymi zmiennymi, które być może będę musiał ocenić setki razy używając różnych zmiennych. Zasadniczo, jeśli uda mi się najpierw przeanalizować formułę, aby ją zoptymalizować, i wtedy mogę przekazywać zmienne do tej zoptymalizowanej wersji tyle razy, ile potrzebuję, za każdym razem, gdy generuje ona wynik dla mnie.

Napiszę to w Delphi lub C#. Napisałem już coś podobnego za pomocą algorytmu manewrowego, ale za każdym razem, gdy potrzebuję obliczyć tę samą formułę, muszę przejść przez etap analizy. Musi być lepszy sposób na zrobienie tego.

Answer 1

Jeśli chcesz to zrobić z Delphi, można spojrzeć w jaki sposób jednostka JclExprEval działa, część JEDI Code Library. Napisałem to kilka lat temu (jest to trochę nadmiarowe); analizuje funkcje i zmienne i może przekazać ci wskaźnik metody, który szybko ocenia wyrażenie. Przekaż zmienne przez odniesienie i możesz je zmienić bezpośrednio, a ponownie obliczone wyrażenie zostanie odpowiednio obliczone.

W każdym przypadku pomocne mogą być podstawy działania. Analiza składniowa wyrażeń rekursywnych jest łatwa, a budując drzewo można wielokrotnie oceniać bez ponownego analizowania. JclExprEval faktycznie generuje kod prostego komputera stosu, dzięki czemu może pracować trochę szybciej niż interpretacja drzewa; Maszyny stosu w dużym stopniu ograniczają operacje związane z pamięcią do tablic i używają przełączników dla opkodów, podczas gdy interpretacja drzewa podąża za łączami w całej stercie i często używa wirtualnej wysyłki (lub podwójnej wysyłki) dla kodów opcyjnych, więc zwykle kończą się one wolniej.

Przyjmując to samo podejście, co JclExprEval w parsowaniu, ale napisane w C#, i budowanie Expression, jak sugeruje Marc, jest kolejnym całkowicie poprawnym podejściem. Wyrażenie skompilowane przez JIT powinno być trochę szybsze niż zinterpretowany program do wyrażania lub drzewo, które same są dużo szybsze niż parsowanie.

Answer 2

W języku C# z .NET 3.5 można do tego celu użyć Expression; możesz zbudować sparametryzowane wyrażenie, a następnie skompilować je do delegata. Dokładnie to zrobiłem dla aspektu matematycznego Finguistics. Nadal mam kod parsowania użyłem, jeśli chcesz ...

Główną sztuczką, której użyłem było to, aby utrzymać typ delegata znany, użyłem tablicy jako typ wejścia - traktowanie różnych argumentów jako arr [0] , arr 1, arr [2] itd. Oznacza to, że mogę skompilować (na przykład) Func<decimal[], decimal> (pobiera tablicę z decimal s, zwraca decimal).

Po wywołaniu Compile(), jest to portmonetka tak, jakbyś miał kod, aby zrobić to bezpośrednio.

(edit)

jako krótki przykład użycia Expression w ten sposób (z twardym kodowane funkcji), patrz poniżej. Analizator składni, który napisałem już obecnie działa jako sprawdzianpredykatu - tj. Aby sprawdzić, czy "? + (2 *? -?) = 22 +?" - ale nie byłoby trudno go zmienić, aby zamiast tego zwrócić wynik (i wprowadzić więcej operacji, takich jak sin/pow/etc - prawdopodobnie przez mapowanie ich bezpośrednio do publicznych metod na obiekcie pomocniczym (przez 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); 
    } 
}