Помогите решить такую задачу:
В программе происходят вычисления по разным формулам
( Например (v1*v2)/v3+6 и значение переменных v1, v2, v3 )
Функция проводит синтаксический анализ формулы и строит что-то (это главный вопрос), что в последствии программой воспринимается, как алгоритм рассчета с переменными v1,v2...
В результате получаем какое-то число...
Надо, чтобы подобная функция проводила анализ шаблона формулы один раз, чтобы потом просто подставлять туда переменные и вычислять арифметическое выражение...
Т.е.:
??? f(char par[]) — функчия разбора синтаксиса
{
return ???;
}//Должна запускаться один раз и скорость работы не важна
int f1(???,int a, int b, int c)
{
с=..Только арифмитические действия над a, b и с по какому-то правилу ???
return c;
}//Для этой функции необходима максимальная скорость вычисления
Что использовать в качестве "???"
Помогите!!!
Зарание огромное спасибо...
Всё может быть... и не всё ещё было!
Re: Частые вычисления по неопределенной формуле!!!
Здравствуйте, GrayWizard, Вы писали:
GW>Помогите решить такую задачу: GW>В программе происходят вычисления по разным формулам GW>( Например (v1*v2)/v3+6 и значение переменных v1, v2, v3 ) GW>Функция проводит синтаксический анализ формулы и строит что-то (это главный вопрос), что в последствии программой воспринимается, как алгоритм рассчета с переменными v1,v2... GW>В результате получаем какое-то число... GW>Надо, чтобы подобная функция проводила анализ шаблона формулы один раз, чтобы потом просто подставлять туда переменные и вычислять арифметическое выражение... GW>Т.е.: GW>??? f(char par[]) — функчия разбора синтаксиса GW>{ GW> return ???; GW>}//Должна запускаться один раз и скорость работы не важна
GW>int f1(???,int a, int b, int c) GW>{ GW> с=..Только арифмитические действия над a, b и с по какому-то правилу ??? GW> return c; GW>}//Для этой функции необходима максимальная скорость вычисления
GW>Что использовать в качестве "???" GW>Помогите!!! GW>Зарание огромное спасибо...
Дерево, что же еще! Строишь дерево разбора, узлами которого являются операции, числа и переменные. Потои в функции, вычисляющей значение, просто на место переменных ставишь нужные числа.
Re: Частые вычисления по неопределенной формуле!!!
Здравствуйте, GrayWizard, Вы писали:
GW>Помогите решить такую задачу: GW>В программе происходят вычисления по разным формулам
переводишь формулу в обратную польскую запись и потом в польской записи подставляешь значения. Вычисления значения формулы в таким виде будут идти максимально быстро
GW>( Например (v1*v2)/v3+6 и значение переменных v1, v2, v3 )
(v1*v2)/v3+6 => v1 v2 * v3 / 6 +
сооветственно, подставляем v1 v2 v3 и считаем (обычным стековым методом)
Re: Частые вычисления по неопределенной формуле!!!
Здравствуйте, _temp_, Вы писали:
__>Дерево, что же еще! Строишь дерево разбора, узлами которого являются операции, числа и переменные. Потои в функции, вычисляющей значение, просто на место переменных ставишь нужные числа.
Дерево слишьком медленно считать. Обратная польская запись быстрее.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Частые вычисления по неопределенной формуле!!!
Здравствуйте, c-smile, Вы писали:
CS>Только твой double calculate() (байткод стековая машина) теоретически медленнее чем прямое исполнения дерева операций.
С какой это радости оно медленней?
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: Частые вычисления по неопределенной формуле!!!
Здравствуйте, c-smile, Вы писали:
CS>Что конкретно там медленно: compilation или evaluation? CS>Насколько я могу судить визально evaluation там сделана классически. Быстрее можно но не намного.
Я его очень давно тестил и цифры уже не помню. Но он слил моему аналогу (тогда я прикаловался с конечными автоматами) и там и там. Причем слил в разы.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Частые вычисления по неопределенной формуле!!!
Круто.
WH>А считать быстрее у тебя врятли получится.
ИМХО можно. Если вместо token.kind иметь указатель на функцию получающую в качестве аргумента ссылку на стек. Таким образом можно избавится от switch'а.
... << RSDN@Home 1.1.3 beta 2 >>
Re[3]: Частые вычисления по неопределенной формуле!!!
Здравствуйте, Рома Мик, Вы писали:
WH>>А считать быстрее у тебя врятли получится. РМ>ИМХО можно. Если вместо token.kind иметь указатель на функцию получающую в качестве аргумента ссылку на стек. Таким образом можно избавится от switch'а.
Не думаю что будет быстрее. (автору темы важна скорость)
Вот во что превращается второй вариант. ИМХО косвенные вызовы тут все испортят.
?calculate@calculator2@@QAENXZ PROC NEAR ; calculator2::calculate, COMDAT
; _this$ = ecx
; 11 : if(tokens.empty())
mov edx, DWORD PTR [ecx+4]
push esi
mov esi, DWORD PTR [ecx]
cmp esi, edx
jne SHORT $L112887
; 12 : return 0;
fld QWORD PTR __real@0000000000000000
pop esi
; 31 : }
ret 0
$L112887:
; 13 : double* s=&stack[0]-1;
mov eax, DWORD PTR [ecx+12]
; 14 : for(size_t i=0, count=tokens.size();i<count;++i)
sub edx, esi
sar edx, 4
sub eax, 8
test edx, edx
jbe SHORT $L112893
push ebx
push edi
xor edi, edi
mov ebx, edx
$L112891:
; 15 : switch(tokens[i].kind)
mov edx, DWORD PTR [ecx]
mov esi, DWORD PTR [edx+edi]
add edx, edi
cmp esi, 8
ja SHORT $L112892
jmp DWORD PTR $L127305[esi*4]
$L112898:
; 16 : {
; 17 : case token_kind_variable: *++s=*tokens[i].variable; break;
mov edx, DWORD PTR [edx+8]
fld QWORD PTR [edx]
add eax, 8
jmp SHORT $L127304
$L112899:
; 18 : case token_kind_const: *++s=tokens[i].value; break;
fld QWORD PTR [edx+8]
add eax, 8
jmp SHORT $L127304
$L112900:
; 19 :
; 20 : case token_kind_op_add: s[-1]=s[-1]+s[0];--s; break;
fld QWORD PTR [eax]
add eax, -8 ; fffffff8H
fadd QWORD PTR [eax]
fstp QWORD PTR [eax]
jmp SHORT $L112892
$L112901:
; 21 : case token_kind_op_sub: s[-1]=s[-1]-s[0];--s; break;
fld QWORD PTR [eax-8]
add eax, -8 ; fffffff8H
fsub QWORD PTR [eax+8]
fstp QWORD PTR [eax]
jmp SHORT $L112892
$L112902:
; 22 : case token_kind_op_mul: s[-1]=s[-1]*s[0];--s; break;
fld QWORD PTR [eax]
add eax, -8 ; fffffff8H
fmul QWORD PTR [eax]
fstp QWORD PTR [eax]
jmp SHORT $L112892
$L112903:
; 23 : case token_kind_op_div: s[-1]=s[-1]/s[0];--s; break;
fld QWORD PTR [eax-8]
add eax, -8 ; fffffff8H
fdiv QWORD PTR [eax+8]
fstp QWORD PTR [eax]
jmp SHORT $L112892
$L112904:
; 24 :
; 25 : case token_kind_op_neg: s[0]=-s[0]; break;
fld QWORD PTR [eax]
fchs
jmp SHORT $L127304
$L112905:
; 26 :
; 27 : case token_kind_fn_sin: s[0]=sin(s[0]); break;
fld QWORD PTR [eax]
fsin
jmp SHORT $L127304
$L112906:
; 28 : case token_kind_fn_cos: s[0]=cos(s[0]); break;
fld QWORD PTR [eax]
fcos
$L127304:
fstp QWORD PTR [eax]
$L112892:
; 14 : for(size_t i=0, count=tokens.size();i<count;++i)
add edi, 16 ; 00000010H
dec ebx
jne SHORT $L112891
pop edi
pop ebx
$L112893:
; 29 : }
; 30 : return s[0];
fld QWORD PTR [eax]
pop esi
; 31 : }
ret 0
npad 2
$L127305:
DD $L112900
DD $L112901
DD $L112902
DD $L112903
DD $L112904
DD $L112898
DD $L112899
DD $L112905
DD $L112906
?calculate@calculator2@@QAENXZ ENDP; calculator2::calculate
Хотя с указателем на функцию будет болие гибкое решение.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Частые вычисления по неопределенной формуле!!!
Здравствуйте, GrayWizard, Вы писали:
GW>Помогите решить такую задачу: GW>В программе происходят вычисления по разным формулам GW>( Например (v1*v2)/v3+6 и значение переменных v1, v2, v3 ) GW>Функция проводит синтаксический анализ формулы и строит что-то (это главный вопрос), что в последствии программой воспринимается, как алгоритм рассчета с переменными v1,v2... GW>В результате получаем какое-то число... GW>Надо, чтобы подобная функция проводила анализ шаблона формулы один раз, чтобы потом просто подставлять туда переменные и вычислять арифметическое выражение... GW>Т.е.: GW>??? f(char par[]) — функчия разбора синтаксиса GW>{ GW> return ???; GW>}//Должна запускаться один раз и скорость работы не важна
GW>int f1(???,int a, int b, int c) GW>{ GW> с=..Только арифмитические действия над a, b и с по какому-то правилу ??? GW> return c; GW>}//Для этой функции необходима максимальная скорость вычисления
GW>Что использовать в качестве "???" GW>Помогите!!! GW>Зарание огромное спасибо...
Есть вариант использовать, псевдокомпиляцию.
Разделим анализ строки и вычисления результата. Анализатор формирует последовательный массив операций в вычисляемом порядке и кодирует по типам операций ( получить переменную 1, * 2, + 3 и т д ). А также массив переменных (a-0,b-1,c-2);
Пример строка «a*b+c» декодируется так “ab*c+” -> a(1,v[0]); b(1,v[1]); *(2,a,b); c(1,v[2]); +(3,*,c)
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, c-smile, Вы писали:
CS>>Только твой double calculate() (байткод стековая машина) теоретически медленнее чем прямое исполнения дерева операций. WH>С какой это радости оно медленней?
Медленнее но "тильке трошки-трошки".
На самом деле ты прав наверное. Надо еще раз проверять.
С учетом function callв моем случае может и медленнее мой вариант.
И чтоб два раза не всавать — я был проверял executable goto в GCC, ну дык он мне дал 7% увеличение быстродействия в среднем при исполненни байткода по сравнению со switch.
Re[5]: Частые вычисления по неопределенной формуле!!!
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, WolfHound, Вы писали:
... WH> typedef void(CALCULATOR3_CALL_CONVERSION *operation_fn_t)(double*&, token const&);
...
Может здесь передавать указатель на какую то структуру состояния, вместо двух параметров? Интересно, замедлит это или наоборот ускорит? Но, по моему, это более симпатичнее.
Что то вроде:
class process { ... };
typedef void(CALCULATOR3_CALL_CONVERSION *operation_fn_t)(process &);
Тогда сдвиг итератора i WH> for(std::vector<token>::iterator i=tokens.begin(), e=tokens.end();i!=e;++i)
можно вынести в функции, если вынести i в процесс (это может быть полезно если в дальнейшем совершенствовать этот калькулятор, например сделать оператор if в выражениях). И условие выхода сделать в виде флага, а функция устанавливающая этот флаг пусть находиться в самом конце вектора tokens.
P.S. Не компилировал, просто высказал идею.
class process
{
...
std::vector<token>::iterator i;
bool do_continue;
...
void loop(std::vector<token> &X)
{
do_continue = true;
i = X.begin();
do { i->operation_fn(*this); } while(do_continue);
}
/* должна находиться в конце списка команд, как минимум */static void CALCULATOR3_CALL_CONVERSION token_end(process &this_){ this_->do_continue = false; }
};
Здравствуйте, sergey_shandar, Вы писали:
_>Может здесь передавать указатель на какую то структуру состояния, вместо двух параметров? Интересно, замедлит это или наоборот ускорит? Но, по моему, это более симпатичнее.
ИМХО симпатичнее всего ( но не быстрее, видимо ) иметь
Здравствуйте, Рома Мик, Вы писали:
РМ>Здравствуйте, sergey_shandar, Вы писали:
_>>Может здесь передавать указатель на какую то структуру состояния, вместо двух параметров? Интересно, замедлит это или наоборот ускорит? Но, по моему, это более симпатичнее. РМ>ИМХО симпатичнее всего ( но не быстрее, видимо ) иметь РМ>
Я предлагаю больше информации передавать команде, т.е. полное состояние, ссылку на процесс, а не только на стек. Так что так будет более функционально:
А замена виртуальной функции на указатель на функцию это всего лишь оптимизация, которая мало затрагивает возможности реализации. Но это уже больше к философии и к субъективности восприятия индивидуумами, а не к алгоритмам