раз парсинг, два парсинг ... n парсинг!

[pronto]

Исследование функций с помощью компьютера - дело интересное. Однако, при близком рассмотрении оказалось, что во всем этом есть ньансы.
Для построения графика функции заданной в привычном виде, например, "y = sin(x/20)*40 + sin(x/9)*30" возникает необходимость многократного ее парсинга для различных значений аргумента x. Такой подход сводит на нет все попытки максимально ускорить процесс парсинга, и уже при ~1000 итераций построение графика занимает ~1 секунду.
График аналогичной функции заданной в коде программы, при ~10 000 итераций, что близко к требуемому, строится за ~30 миллисекунд. Вот и возникает справедливый вопрос. Как совместить удобство первого варианта со скоростью второго?

[tyomitch]

Написать свой компилятор. Либо взять чужой.

[Antonariy]

А если подключить ScriptControl? Передать в него цикл, содержащий исследуемую функцию, и объект, аккумулирующий результаты выполнения. Или вместо абстрактной коллекции объект, сразу строящий график. Хотя, если одна секунда это много, то в скрипте, вероятно, будет еще больше.

[pronto]

Про компилятор я думал, но дюже проблематично будет - ради интереса-то.

[Хакер]

Чем парсишь? Пробовал эвалютатор GSerg-а? Он быстрый... но бажный.

[tyomitch]

Он, кажется, правоассоциативный... Там 1-1-1 = 1

[GSerg]

бажный.

[Хакер]

Ну я имел ввиду не совсем то. Там при обработки длинных и много-скобко-содержащих выражений случалась ошибка Стек переполнен.

Могу выложить свой. Он без этих 2 ошибок но работает в 2-3 раза медленней.

Добавлено: "Медлено" понятие относительно. Выражение "1+2+3+4+5+...+5000" он подсчитывает за 300 мс.

[Efiop]

pronto, а есть код, чтоб посмотреть?

[pronto]

Есть, но не мой. Надо?

ЗЫ. Думаю, что надо. Поэтому...

[kuhtiov]

А вы не поясните (в целях повышения образованности), что такое парсинг?

[Viper]

В целях образованности: парсинг (parsing) есть синтаксический анализ какого-либо выражения. Ну например это может быть анализ математического выражения для его последующего вычисления.

[kuhtiov]

Ааааааа, спасибо за пояснение

[vvs_adm]

Ааааааа, спасибо за пояснение

Может мне еще кто-нибудь пояснит, зачем при построении графика функции её многократный [цитата автора] парсинг вместо одного? Или у автора y=Fx(x), где Fx=F(x)?

[Хакер]

vvs_adm
Он делает многократную эвалютацию, ибо функция у него не прямолинейная. Я бы автору посоветовал, написать свой парсер, да так, чтоб он всё что не зависит от X - парсил заранее.

Ну например.

Есть функция
F(x) = Sin(x) + ( X / ( 1 + 2 +3 ) )

так вот отсюда можно выдрать часть и посчитать для неё коэффициент, ещё до итерайий. А уж во время итерация парсить функцию Sin(x) + k*x

90% времени парсинга уходят не на вычисления а на сам парсинг.

И функция
F(x) = ((((((((((((((((((x + 5))))))))))))))))))
будет выполнять оооой, как долго, хотя эквивалент [x+5] выпролнится быстро.

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

[vvs_adm]

Жаль, что нихрена не понял На сегодня пива хватит. Но про многократный парсинг единственной бедной функции стоит еще раз подумать. Потому что пока все-таки не понял, зачем сто раз парсить функцию F(x)=sin(x)+x/(1+2+3), которая парсится всего один раз к виду например F(x)=x sin x 1 2 3 + + / + (ну может чуть ошибся [таки пиво, да и давно это было], но это приблизительно постфикная запись).

[Хакер]

Гм...

х каждый раз меняется...

Каждый раз считается заново Sin(x) и X / 6 - на это уходит кача времени. Но не конкретно на это, а но то, чтоб эвалютатор понял что нужно сделать именно это, а потом уже считал.

[vvs_adm]

Но не конкретно на это, а но то, чтоб эвалютатор понял что нужно сделать именно это.

Нормальный "эвалютатор" (смысл странного слова угадываем с помощью волшебного свойства самого автора) поймет это после первого парсинга функции. После чего функция превратится в дерево, в листья которой надо будет воткнуть Х. При желании можно просканить ветви дерева на предмет возмого предподсчета, дабы каждый раз не считать (1+2+3). Но пиво мне все таки все еще твердит - парсить функцию при подставлении очередного Х больше не надо :(

[Хакер]

Эвалютатор (от слова Eval***) не знает что в следующий раз он получит ту же функцию что и в прошлый раз. Эвалютатор просто тупо просчитывает выражение и забывает его.

[vvs_adm]

Для построения графика функции заданной в привычном виде, например, "y = sin(x/20)*40 + sin(x/9)*30" возникает необходимость многократного ее парсинга для различных значений аргумента x.

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

[Хакер]

Я про эвалютатор в принципе. А если некий модуль, что то ещё замониает, а в следующий раз вспоминает, и проверяет не то ли это, что он запомнил в прошлый раз... это уже не эвалютатор. Это уже AI.

[vvs_adm]

Нахрена такие извращения. Просто у эвалютатора есть (должно быть) два метода : 1) пропарсить 2) подставить в пропарсенную перед этим функцию значение х, у и еще одну неизвестную. И все. И теперь автору темы можно при построении графика функции парсить ее при каждом новом Х хоть четыре раза. Главное - не забыть подставить потом один раз Х.

[Хакер]

Эвалютатор работает так.

Сначала проверяет кол-во открытых закрытых скобочек. Если всё ок.

Рекурсивно подсчитывает.

Рекурсиваня функция выглядет так: ищет оператор с наибольшим приоритетом, подсчитывает. Если операнд - скобки - выполняет сама себя, передав в аргумент, выражение находящееся внутри скобок. И так пока выражение не преваратится в 1 число.

[vvs_adm]

Это твой эвалютатор Эвалютатор для построения графика функции работает так: 1) парсинг - построение дерева, где в вершине оператор, в листьях операнды (не надо уничтожать построенное дерево) 2) подстава в те листья, где не число, а Х, значение икса, после чего проход по дереву с вычислением получившегося выражения. Можно конечно при построении функции применять "одноразовый" эвалютатор, но зачем?

[pronto]

Даже и не представлял, что эта тема вызовет такое бурное обсуждение! Видно, многих, а не только меня, эта тема уже затрагивала в той или иной степени. Я уже перелистывал литературу по асму и там мне встречался пример "постфиксной" записи. Это и мат. сопроцессор наталкивают склониться к варианту компилирования функции. Но я абсолютно не представляю с какой стороны ко всему этому подходить!

[Viper]

"Вы еще подеритесь, горячие финские парни!"©

[jangle]

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

[pronto]

Да-а-а... Давненько я не захаживал сюда - некогда было. Но интерес к проблеме еще остался, как и сама проблема. Нарыл кучу материала по переводу в постфикс, изучил три готовых кода (хоть и медленных, но хоть каких-то) в процессе написания собственного кода сталкнулся с трудностями, пока непреодолимыми, которые связаны с частичной правильной работоспособностью алгоритма. В добавок ко всему он получился немногим более быстрым чем те, что уже есть ~750 мс (для тестового выражения "1+2+...+5000"). Поэтому, Хакер, если не трудно, то, пожалуйста, выложи свой парсер, который, как заявлено, работает в 2.5 раза быстрее - хоть посмотреть на сие чудо!

З.Ы. Если переложить его на другой язык (Си, PowerBasic), то можно ли добиться его ускорения и во сколько раз?

[Viper]

По-моему тема о скорости выполнения одного и того же алгоритма на разных языках многократно обсуждалась. Время выполнения зависит в основном от алгоритма.

[pronto]

Эт-то понятно. Я про "тупой" перенос алгоритма.