Эффективность оценки выражений на основе стека для математического анализа

Question

Я должен написать для академических целей приложение, которое отображает пользовательские выражения, такие как: f (x) = 1 - exp (3 ^ (5 * ln (cosx)) + x)

Подход, который я выбрал для написания парсера, заключается в преобразовании выражения в RPN с помощью алгоритма Шунтирования-Ярда, рассматривая примитивные функции, такие как "cos", как унарные операторы. Это означает, что написанная выше функция будет преобразована в серию токенов, например:

1, x, cos, ln, 5, *,3, ^, exp, -

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

Answer 1

Сколько стоит "много раз"? Миллион?

Какие функции можно вводить? Можем ли мы предположить, что они непрерывны?

Вы пытались измерить, насколько хорошо работает ваш код?

(Извините, начал с вопросов!)

Вы можете попробовать один из двух подходов (или оба), кратко описанных ниже (возможно, их гораздо больше):

1) Разобрать деревья.

Вы можете создать дерево разбора. Затем выполните то, что делает большинство компиляторов, чтобы оптимизировать выражения, свертывание констант, исключение общих подвыражений (чего можно достичь, связав вместе поддеревья общих выражений и кэшируя результат) и т. Д.

Тогда вы можете использовать ленивые методы оценки, чтобы избежать целых поддеревьев. Например, если у вас есть дерево

    *
   / \
  A   B

где A оценивается в 0, вы можете полностью избежать оценки B, поскольку вы знаете результат равен 0. С RPN вы проиграете в ленивой оценке.

2) Интерполяция

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

Чтобы создать начальный набор данных, вы можете просто использовать подход 1 или просто придерживаться своего RPN, поскольку вы будете генерировать только несколько значений.

Так что, если вы используете интерполяцию, вы можете оставить свой RPN ...

Надеюсь, это поможет!

Answer 2

Зачем изобретать велосипед? Вместо этого используйте быстрый язык сценариев. Интеграция чего-то вроде lua в ваш код займет очень мало времени и будет очень быстрой.

Обычно вы можете скомпилировать выражение в байтах, и это должно привести к тому, что код будет работать очень быстро, конечно же, достаточно быстро для простых одномерных графиков.

Я рекомендую lua как быстрый и интегрироваться с C / C ++ проще, чем любой другой язык сценариев. Другим хорошим вариантом будет python, но, хотя он более известен, мне было сложнее интегрировать.

Answer 3

Майкл Андерсон предложил Луа . Если вы хотите попробовать Lua только для этой задачи, посмотрите мою библиотеку ae .

Answer 4

Я использую алгоритм шунтирования для создания RPN. Затем я «компилирую» RPN в токенизированную форму, которую можно выполнять (интерпретативно) несколько раз без повторного анализа выражения.

Answer 5

Почему бы не обходить дерево разбора (я свободно использую «дерево», в вашем случае это последовательность операций) и соответственно отмечать входные переменные? (например, для входов x, y, z и т. д. отметьте «x» 0 для обозначения первой входной переменной, «y» 1 для обозначения 2-й входной переменной и т. д.)

Таким образом, вы можете один раз проанализировать выражение, сохранить дерево разбора, получить массив входных данных и применить дерево разбора для оценки.

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

Answer 6

Одной из оптимизаций будет замена стека массивом значений и реализация оценщика в виде трехадресного механизма , где каждая операция загружается из двух (или одного) местоположений и сохраняет в третье. Это может сделать для очень жесткого кода:

struct Op {
  enum {
    add, sub, mul, div,
    cos, sin, tan,
   //....
  } op;
  int a, b, d;
}

void go(Op* ops, int n, float* v) {
  for(int i = 0; i < n; i++) {
    switch(ops[i].op) {
      case add: v[op[i].d] = v[op[i].a] + v[op[i].b]; break;
      case sub: v[op[i].d] = v[op[i].a] - v[op[i].b]; break;
      case mul: v[op[i].d] = v[op[i].a] * v[op[i].b]; break;
      case div: v[op[i].d] = v[op[i].a] / v[op[i].b]; break;
      //...
    }
  }
}

Преобразование из RPN в 3-адрес должно быть простым, поскольку 3-адрес является обобщением.

Answer 7

Я думаю, что эта библиотека на основе RPN может служить цели: http://expressionoasis.vedantatree.com/

Я использовал его с одним из моих проектов калькулятора, и он работает хорошо. Это маленький и простой, но расширяемый.

Answer 8

Ваша простая интерпретация RPN должна работать просто отлично, тем более что она содержит

• функции математической библиотеки, такие как cos, exp и ^ (pow, включая журналы)

• поиск в таблице символов

Надеюсь, ваша таблица символов (с такими переменными, как x) будет короткой и простой.

Библиотечные функции, скорее всего, будут самыми трудоемкими, поэтому, если ваш интерпретатор плохо написан, это не будет проблемой.

Если, однако, вам действительно нужно идти на скорости, вы можете преобразовать выражение в код на C, скомпилировать и связать его в dll на лету и загрузить его (занимает около секунды) , Это, плюс запомненные версии математических функций, может дать вам лучшую производительность.

P.S. Для синтаксического анализа ваш синтаксис довольно ванильный, поэтому простой синтаксический анализатор с рекурсивным спуском (около страницы кода, O (n) такой же, как shunting-yard) должен работать просто отлично. На самом деле, вы можете просто вычислить результат при разборе (если математические функции занимают большую часть времени), и не беспокоиться о деревьях разбора, RPN и других подобных вещах.

Answer 9

Неэффективно в каком смысле? Есть машинное время и программистское время. Есть ли стандарт того, как быстро он должен работать с определенным уровнем сложности? Что важнее завершить задание и перейти к следующему (перфекционисты иногда никогда не заканчивают)?

Все эти шаги должны выполняться для каждого входного значения. Да, у вас может быть эвристика, которая сканирует список операций и немного его очищает. Да, вы можете скомпилировать некоторые из них до сборки вместо вызова +, * и т. Д. В качестве функций высокого уровня. Вы можете сравнить векторизацию (выполнение всех +, затем всех * и т. Д. С вектором значений) с выполнением всей процедуры для одного значения за раз. Но нужно ли это?

Я имею в виду, что, по-вашему, произойдет, если вы создадите функцию в gnuplot или Mathematica?