Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Интерпретатор математических формул

Автор: psyco 26.4.2011, 23:28

Здравствуйте! Пишу интерпретатор математических выражений. Входные данные - текст формулы и аргумент х, в котором нужно найти значение этой функции. Вкратце покажу как реализовал(C#):

Код


string RPNConvert(string s);              /*преобразовывает входную строку в обратную польскую нотацию*/
double RPNSolve(string s);                /*вычисляет конечное значение с обратной польской нотации*/
string Constants(string s,double x);  /*во входной строке ищет константы, вырезает их и вставляет вместе них числа*/
string TAFT(string s);                         /*во входной строке ищет математические функции(тригоном., арифм.), делит на _функцию и _аргумент,вызывает саму себя с аргументом _аргумент */
double RPNCore(string s,double x);   /*принимает входную строку и число х, выдает f(x)*/

1. Входная строка и аргумент х поступают на RPNCore
2. RPNCore вызывает Constants, заменяя все символьные константы на числа
3. RPNCore вызывает TAFT, заменяя все символьные функции на числа
4. RPNCore вызывает RPNConvert, преобразовывая строку в обратную польскую нотацию
5. RPNCore вызывает RPNSolve, вычисляя по обратной польской нотации значение функции в точке х.
На примере: x+sin(pi*x), в точке x=1
1.
2. x+sin(pi*x)->1+sin(3.14*1)
3. 1+sin(3.14*1)->1+0
4. 1+0-> 1 0 +
5. 1 0 + -> 1
Все работает, как мог оптимизовал. Среднее время нахождения результата простеньких выражений порядка 5-10мс (знаю, много).
Проблема состоит в том, что при табуляции математического выражения и входного аргумента х, например х=[-10,10], с количеством точек n=500, программа работает около 15 сек !!! Табуляция происходит так: вызываю RPNCore с текстом математического выражения и х=-10, записываю первое значения, увеличиваю х: х=-9.96 вызываю RPNCore, записываю следующее значение и т.д.
Подскажите, пожалуйста, как можно было бы ускорить работу? (может быть через многопоточность, или все намного проще?) Заранее благодарен!

Автор: Pavia 27.4.2011, 05:32

Переводишь строку во внутреннее представления в котором легко производить вычисления.
RPNCore - выкинуть из цикла. Парсинг самое медленное, его надо выполнять один раз, оставить только вычисления.

Цитата

5-10мс (знаю, много).

медленно должно быть раз в 100 быстрее. Возьми профайлер и посмотри что тормозит. А потом оптимизируй.

Автор: psyco 27.4.2011, 12:07

Цитата

Переводишь строку во внутреннее представления в котором легко производить вычисления.

Это конечно самый оптимальный вариант, но как это реализовать я не представляю. Насколько я понимаю нужно строку перевести в формат функции, а потом ее табулировать. Можете подсказать какие-то основные идет насчет этого? Спасибо

Автор: Sartorius 27.4.2011, 13:54

http://msdn.microsoft.com/en-us/library/bb397951.aspx