Лучший алгоритм для оценки математического выражения?

Question

Какой лучший алгоритм для оценки математического выражения? Я хотел бы иметь возможность немного оптимизировать это в том смысле, что у меня может быть одна формула с различными переменными, которые мне, возможно, придется оценивать сотни раз с использованием различных переменных. Таким образом, в принципе, если я смогу сначала проанализировать формулу, чтобы она каким-то образом была оптимизирована, а затем я мог бы передавать переменные в эту оптимизированную версию столько раз, сколько мне нужно, каждый раз, когда она дает результат для меня.

Я напишу это либо в Delphi, либо в C #. Я уже написал нечто подобное, используя алгоритм шунтирования, но каждый раз, когда мне нужно вычислить одну и ту же формулу, мне приходится проходить этап синтаксического анализа. Должен быть лучший способ сделать это.

Answer 1

Если вы хотите сделать это с Delphi, вы можете посмотреть, как работает модуль JclExprEval, часть библиотеки кодов JEDI . Я написал это несколько лет назад (это немного перегружено); он анализирует функции и переменные и может вернуть вам указатель на метод, который быстро вычисляет выражение. Передайте переменные по ссылке, и вы можете изменить их напрямую, и пересчитанное выражение будет рассчитано соответствующим образом.

В любом случае, основы того, как это работает, могут быть вам полезны. Синтаксический анализ выражений с рекурсивным спуском является простым, и, построив дерево, вы можете вычислять несколько раз без повторного анализа. JclExprEval фактически генерирует код для простой стековой машины, так что он может работать немного быстрее, чем интерпретация дерева; стековые машины в основном ограничивают свои операции с памятью массивами и используют переключатели для кодов операций, в то время как интерпретация дерева следует ссылкам по всей куче и часто использует виртуальную диспетчеризацию (или двойную диспетчеризацию) для кодов операций, поэтому они обычно заканчиваются медленнее.

Использование того же подхода, что и JclExprEval при разборе, но написанного на C #, и создание Expression, как предлагает Марк, - еще один совершенно правильный подход. JIT-скомпилированное выражение должно быть немного быстрее, чем интерпретируемая программа или дерево выражений, которые сами по себе намного быстрее, чем синтаксический анализ.

Answer 2

В C # с .NET 3.5 вы можете использовать Expression для этого; Вы можете построить параметризованное выражение и затем скомпилировать его в делегат. Это именно то, что я сделал для математического аспекта Finguistics . У меня все еще есть код разбора, который я использовал, если хотите ...

Основной трюк, который я использовал, заключался в том, что для того, чтобы тип делегата был известен, я использовал массив в качестве типа ввода - обрабатывая различные аргументы как arr [0], arr 1 , arr [2] и т. Д. Это означает, что я мог бы скомпилировать (например) в Func<decimal[], decimal> (принимает массив decimal s, возвращает decimal).

После того, как вы позвонили Compile(), это очень печально, как если бы у вас был код, чтобы сделать это напрямую.

(редактировать)

В качестве краткого примера использования Expression таким образом (с жестко закодированной функцией) см. Ниже. Парсер, который я уже написал , в настоящее время работает как предикат , т. Е. Чтобы проверить, что "? + (2 *? -?) = 22 +?" - но было бы нетрудно изменить его так, чтобы он вместо этого возвращал результат (и вводил больше операций, таких как sin / pow / etc) - предположительно, отображая их напрямую в публичные методы объекта-помощника (через 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);
    } 
}