Частые вычисления по неопределенной формуле!!!
От: GrayWizard Россия  
Дата: 22.04.04 05:58
Оценка:
Помогите решить такую задачу:
В программе происходят вычисления по разным формулам
( Например (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: Частые вычисления по неопределенной формуле!!!
От: _temp_  
Дата: 22.04.04 06:55
Оценка:
Здравствуйте, 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: Частые вычисления по неопределенной формуле!!!
От: ch00k  
Дата: 22.04.04 07:54
Оценка:
Здравствуйте, GrayWizard, Вы писали:

GW>Помогите решить такую задачу:

GW>В программе происходят вычисления по разным формулам

переводишь формулу в обратную польскую запись и потом в польской записи подставляешь значения. Вычисления значения формулы в таким виде будут идти максимально быстро


GW>( Например (v1*v2)/v3+6 и значение переменных v1, v2, v3 )


(v1*v2)/v3+6 => v1 v2 * v3 / 6 +

сооветственно, подставляем v1 v2 v3 и считаем (обычным стековым методом)
Re: Частые вычисления по неопределенной формуле!!!
От: c-smile Канада http://terrainformatica.com
Дата: 22.04.04 15:56
Оценка:
Здравствуйте, GrayWizard, Вы писали:

http://www.rsdn.ru/article/files/Classes/tparser.xml
Автор(ы): Александр Шаргин
Дата: 9.04.2001
Re[2]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 23.04.04 21:10
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>http://www.rsdn.ru/article/files/Classes/tparser.xml
Автор(ы): Александр Шаргин
Дата: 9.04.2001

Он очень медленный.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 23.04.04 21:10
Оценка:
Здравствуйте, _temp_, Вы писали:

__>Дерево, что же еще! Строишь дерево разбора, узлами которого являются операции, числа и переменные. Потои в функции, вычисляющей значение, просто на место переменных ставишь нужные числа.

Дерево слишьком медленно считать. Обратная польская запись быстрее.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 23.04.04 21:10
Оценка: 23 (3)
Здравствуйте, GrayWizard, Вы писали:

GW>Помогите решить такую задачу:

хъ
GW>Зарание огромное спасибо...
А как тебе такое решение
#include <iostream>

#include <string>
#include <vector>
#include <map>

#include <boost/spirit.hpp>
namespace spirit=boost::spirit;
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
namespace lm=boost::lambda;
using lm::_1;
using lm::_2;
using lm::_3;

#include <math.h>

struct calculator 
{
    calculator()
        :grammar(*this)
    {}
    double& variable(std::string const& name)
    {
        double& ref=variables[name];
        if(double** ptr=find(variables_p, name.c_str()))
            *ptr=&ref;
        else
            add(variables_p, name.c_str(), &ref);
        return ref;
    }
    bool parse(std::string const& str)
    {
        tokens.clear();
        return spirit::parse(str.c_str(), grammar, spirit::space_p).full;
    }
    double calculate()
    {
        if(tokens.empty())
            return 0;
        stack.clear();
        for(size_t i=0;i<tokens.size();++i)
            switch(tokens[i].kind)
            {
            case token_kind_op_add:
                stack.end()[-2]=stack.end()[-2]+stack.end()[-1];
                stack.pop_back();
                break;
            case token_kind_op_sub:
                stack.end()[-2]=stack.end()[-2]-stack.end()[-1];
                stack.pop_back();
                break;
            case token_kind_op_mul:
                stack.end()[-2]=stack.end()[-2]*stack.end()[-1];
                stack.pop_back();
                break;
            case token_kind_op_div:
                stack.end()[-2]=stack.end()[-2]/stack.end()[-1];
                stack.pop_back();
                break;

            case token_kind_op_neg:
                stack.back()=-stack.back();
                break;

            case token_kind_variable:
                stack.push_back(*tokens[i].variable);
                break;
            case token_kind_const:
                stack.push_back(tokens[i].value);
                break;

            case token_kind_fn_sin:
                stack.back()=sin(stack.back());
                break;
            case token_kind_fn_cos:
                stack.back()=cos(stack.back());
                break;
            }
        return stack[0];
    }
private:
    typedef char const* iter_t;
    enum token_kind
    {token_kind_op_add
    ,token_kind_op_sub
    ,token_kind_op_mul
    ,token_kind_op_div

    ,token_kind_op_neg

    ,token_kind_variable
    ,token_kind_const

    ,token_kind_fn_sin
    ,token_kind_fn_cos

    };
    struct token
    {
        token(token_kind _kind)
            :kind(_kind)
        {}
        token(double _value)
            :kind(token_kind_const)
            ,value(_value)
        {}
        token(double* _variable)
            :kind(token_kind_variable)
            ,variable(_variable)
        {}
        token_kind kind;
        union
        {
            double value;
            double* variable;
        };
    };
    std::vector<token> tokens;
    std::vector<double> stack;
    spirit::symbols<double*> variables_p;
    std::map<std::string, double> variables;

    void token_add(iter_t, iter_t)
    {
        tokens.push_back(token_kind_op_add);
    }
    void token_sub(iter_t, iter_t)
    {
        tokens.push_back(token_kind_op_sub);
    }
    void token_mul(iter_t, iter_t)
    {
        tokens.push_back(token_kind_op_mul);
    }
    void token_div(iter_t, iter_t)
    {
        tokens.push_back(token_kind_op_div);
    }

    void token_neg(iter_t, iter_t)
    {
        tokens.push_back(token_kind_op_neg);
    }

    void token_fn_sin(iter_t, iter_t)
    {
        tokens.push_back(token_kind_fn_sin);
    }
    void token_fn_cos(iter_t, iter_t)
    {
        tokens.push_back(token_kind_fn_cos);
    }

    void token_variable(double* var)
    {
        tokens.push_back(var);
    }
    void token_const(double val)
    {
        tokens.push_back(val);
    }
private:
    struct calculator_grammar
        :spirit::grammar<calculator_grammar>
    {
        calculator& owner;
        calculator_grammar(calculator& _owner)
            :owner(_owner)
        {}
        template <typename ScannerT>
        struct definition
        {
            definition(calculator_grammar const& self_)
            {
                using namespace spirit;
                calculator& self=self_.owner;
                expression
                    =   term
                        >> *(   ('+' >> term)[lm::bind(&calculator::token_add, &self, _1, _2)]
                            |   ('-' >> term)[lm::bind(&calculator::token_sub, &self, _1, _2)]
                            )
                    ;

                term
                    =   factor
                        >> *(   ('*' >> factor)[lm::bind(&calculator::token_mul, &self, _1, _2)]
                            |   ('/' >> factor)[lm::bind(&calculator::token_div, &self, _1, _2)]
                            )
                    ;

                factor
                    =   real_p[lm::bind(&calculator::token_const, &self, _1)]
                    |    self.variables_p[lm::bind(&calculator::token_variable, &self, _1)]

                    |   (str_p("sin") >> '(' >> expression >> ')')[lm::bind(&calculator::token_fn_sin, &self, _1, _2)]
                    |   (str_p("cos") >> '(' >> expression >> ')')[lm::bind(&calculator::token_fn_cos, &self, _1, _2)]

                    |   '(' >> expression >> ')'
                    |   ('-' >> factor)[lm::bind(&calculator::token_neg, &self, _1, _2)]
                    |   ('+' >> factor)
                    ;
            }

            spirit::rule<ScannerT> expression, term, factor;

            spirit::rule<ScannerT> const&
            start() const { return expression; }
        };
    };
    calculator_grammar grammar;
};

int main()
{
    calculator calc;
    double& asd=calc.variable("asd");
    double& qwe=calc.variable("qwe");
    double& asd1=calc.variable("asd");
    double& qwe1=calc.variable("qwe");
    std::string str="-sin(asd-qwe)*3";
    if (calc.parse(str))
    {
        std::cout << "Parsing succeeded\n";
        asd=345;
        qwe=234;
        std::cout << calc.calculate()<<"\n";
        asd1=123;
        qwe1=234;
        std::cout << calc.calculate()<<"\n";
    }
    else
        std::cout << "Parsing failed\n";
    return 0;
}

Парсинг не особо быстрый хотя тоже не тормоз. И имеет огромный плюс: очень легко модифицируется. А считать быстрее у тебя врятли получится.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Частые вычисления по неопределенной формуле!!!
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.04 21:38
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, c-smile, Вы писали:


CS>>http://www.rsdn.ru/article/files/Classes/tparser.xml
Автор(ы): Александр Шаргин
Дата: 9.04.2001

WH>Он очень медленный.

Что конкретно там медленно: compilation или evaluation?

Насколько я могу судить визально evaluation там сделана классически. Быстрее можно но не намного.
Re[2]: Частые вычисления по неопределенной формуле!!!
От: c-smile Канада http://terrainformatica.com
Дата: 23.04.04 21:45
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>А как тебе такое решение


Клево.

Только твой double calculate() (байткод стековая машина) теоретически медленнее чем прямое исполнения дерева операций.
Re[3]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 24.04.04 07:21
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Только твой double calculate() (байткод стековая машина) теоретически медленнее чем прямое исполнения дерева операций.

С какой это радости оно медленней?
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 24.04.04 07:21
Оценка:
Здравствуйте, c-smile, Вы писали:

CS>Что конкретно там медленно: compilation или evaluation?

CS>Насколько я могу судить визально evaluation там сделана классически. Быстрее можно но не намного.
Я его очень давно тестил и цифры уже не помню. Но он слил моему аналогу (тогда я прикаловался с конечными автоматами) и там и там. Причем слил в разы.
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 24.04.04 16:52
Оценка:
Здравствуйте, WolfHound, Вы писали:

Я тут немного пооптимизировал
//calculator2.h
struct calculator2
{
    calculator2()
        :grammar(*this)
    {}
    double& variable(std::string const& name);
    bool parse(std::string const& str);
    double calculate()
    {
        if(tokens.empty())
            return 0;
        double* s=&stack[0]-1;
        for(size_t i=0, count=tokens.size();i<count;++i)
            switch(tokens[i].kind)
            {
            case token_kind_variable:    *++s=*tokens[i].variable;    break;
            case token_kind_const:        *++s=tokens[i].value;        break;

            case token_kind_op_add:        s[-1]=s[-1]+s[0];--s;        break;
            case token_kind_op_sub:        s[-1]=s[-1]-s[0];--s;        break;
            case token_kind_op_mul:        s[-1]=s[-1]*s[0];--s;        break;
            case token_kind_op_div:        s[-1]=s[-1]/s[0];--s;        break;

            case token_kind_op_neg:        s[0]=-s[0];                    break;

            case token_kind_fn_sin:        s[0]=sin(s[0]);                break;
            case token_kind_fn_cos:        s[0]=cos(s[0]);                break;
            }
        return s[0];
    }
private:
    enum token_kind
    {token_kind_op_add
    ,token_kind_op_sub
    ,token_kind_op_mul
    ,token_kind_op_div

    ,token_kind_op_neg

    ,token_kind_variable
    ,token_kind_const

    ,token_kind_fn_sin
    ,token_kind_fn_cos

    };
    struct token
    {
        token(token_kind _kind)
            :kind(_kind)
        {}
        token(double _value)
            :kind(token_kind_const)
            ,value(_value)
        {}
        token(double* _variable)
            :kind(token_kind_variable)
            ,variable(_variable)
        {}
        token_kind kind;
        union
        {
            double value;
            double* variable;
        };
    };
    std::vector<token> tokens;
    std::vector<double> stack;
    spirit::symbols<double*> variables_p;
    std::map<std::string, double> variables;

    size_t stack_deep;
    size_t stack_max_deep;

    void inc_stack()
    {
        if(++stack_deep>stack_max_deep)
            stack_max_deep=stack_deep;
    }
    void dec_stack()
    {
        --stack_deep;
    }
    void add_binary_op(token_kind op)
    {
        dec_stack();
        tokens.push_back(op);
    }

    void add_unary_op(token_kind op)
    {
        tokens.push_back(op);
    }

    void add_variable(double* var)
    {
        inc_stack();
        tokens.push_back(var);
    }
    void add_const(double val)
    {
        inc_stack();
        tokens.push_back(val);
    }
private:
    struct calculator_grammar
        :spirit::grammar<calculator_grammar>
    {
        typedef calculator2 self_t;
        self_t& owner;
        calculator_grammar(self_t& _owner)
            :owner(_owner)
        {}
        template <typename ScannerT>
        struct definition
        {
            definition(calculator_grammar const& self_);

            spirit::rule<ScannerT> expression, term, factor;

            spirit::rule<ScannerT> const&
            start() const { return expression; }
        };
    };
    calculator_grammar grammar;
};
//calculator2.cpp
#include "stdafx.h"
#include "calculator2.h"

double& calculator2::variable(std::string const& name)
{
    double& ref=variables[name];
    if(double** ptr=find(variables_p, name.c_str()))
        *ptr=&ref;
    else
        add(variables_p, name.c_str(), &ref);
    return ref;
}

bool calculator2::parse(std::string const& str)
{
    tokens.clear();
    stack_deep=0;
    stack_max_deep=0;
    if    (    !spirit::parse(str.c_str(), grammar, spirit::space_p).full
        ||    stack_deep!=1
        )
    {
        tokens.clear();
        return false;
    }
    stack.resize(stack_max_deep+1);
    return true;
}

template <typename ScannerT>
calculator2::calculator_grammar::definition<ScannerT>::definition(calculator_grammar const& self_)
{
    using namespace spirit;
    self_t& self=self_.owner;
    expression
        =   term
            >> *(   ('+' >> term)[lm::bind(&self_t::add_binary_op, &self, self_t::token_kind_op_add)]
                |   ('-' >> term)[lm::bind(&self_t::add_binary_op, &self, self_t::token_kind_op_sub)]
                )
        ;

    term
        =   factor
            >> *(   ('*' >> factor)[lm::bind(&self_t::add_binary_op, &self, self_t::token_kind_op_mul)]
                |   ('/' >> factor)[lm::bind(&self_t::add_binary_op, &self, self_t::token_kind_op_div)]
                )
        ;

    factor
        =   real_p[lm::bind(&self_t::add_const, &self, _1)]
        |    self.variables_p[lm::bind(&self_t::add_variable, &self, _1)]

        |   (str_p("sin") >> '(' >> expression >> ')')[lm::bind(&self_t::add_unary_op, &self, self_t::token_kind_fn_sin)]
        |   (str_p("cos") >> '(' >> expression >> ')')[lm::bind(&self_t::add_unary_op, &self, self_t::token_kind_fn_cos)]

        |   '(' >> expression >> ')'
        |   ('-' >> factor)[lm::bind(&self_t::add_unary_op, &self, self_t::token_kind_op_neg)]
        |   ('+' >> factor)
        ;
}

и прогнал тесты
#include "stdafx.h"
#include "calculator.h"
#include "calculator2.h"
enum{TEST_COUNT=20};
#include "test_engine.h"

std::string str=
    "-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234"
    "-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234"
    "-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234"
    "-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234"
    "-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234-(asd-qwe)*3*3*asd/(asd-sin(qwe)+5/asd)-123.234"
    ;
enum
{parse_count    =10000
,calculate_count=10000
};
TEST_CASE_BEGIN(calc1_parse)
    static void exec(size_t count)
    {
        calculator calc;
        double& asd=calc.variable("asd");
        double& qwe=calc.variable("qwe");
        for(size_t i=0;i<parse_count;++i)
            calc.parse(str);
    }
TEST_CASE_END()
TEST_CASE_BEGIN(calc2_parse)
    static void exec(size_t count)
    {
        calculator2 calc;
        double& asd=calc.variable("asd");
        double& qwe=calc.variable("qwe");
        for(size_t i=0;i<parse_count;++i)
            calc.parse(str);
    }
TEST_CASE_END()
TEST_CASE_BEGIN(calc1_calculate)
    static void exec(size_t count)
    {
        calculator calc;
        double& asd=calc.variable("asd");
        double& qwe=calc.variable("qwe");
        calc.parse(str);
        for(size_t i=0;i<calculate_count;++i)
            calc.calculate();
    }
TEST_CASE_END()
TEST_CASE_BEGIN(calc2_calculate)
    static void exec(size_t count)
    {
        calculator2 calc;
        double& asd=calc.variable("asd");
        double& qwe=calc.variable("qwe");
        calc.parse(str);
        for(size_t i=0;i<calculate_count;++i)
            calc.calculate();
    }
TEST_CASE_END()

int main()
{
    test<test_calc1_parse>();
    test<test_calc2_parse>();
    test<test_calc1_calculate>();
    test<test_calc2_calculate>();
    return 0;
}

calc1_parse
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 2.66607
average middle = 2.65553

calc2_parse
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 2.61811
average middle = 2.61404

calc1_calculate
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 0.323738
average middle = 0.324844

calc2_calculate
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 0.296329
average middle = 0.297043

Выжал 10% дальше только оптимизацией выражения, а это задачка для маньяков
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Частые вычисления по неопределенной формуле!!!
От: Рома Мик Россия http://romamik.com
Дата: 25.04.04 16:19
Оценка: +1
Здравствуйте, WolfHound, Вы писали:
WH>
WH>struct calculator 
WH>

Круто.

WH>А считать быстрее у тебя врятли получится.

ИМХО можно. Если вместо token.kind иметь указатель на функцию получающую в качестве аргумента ссылку на стек. Таким образом можно избавится от switch'а.
... << RSDN@Home 1.1.3 beta 2 >>
Re[3]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 25.04.04 19:31
Оценка:
Здравствуйте, Рома Мик, Вы писали:

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: Частые вычисления по неопределенной формуле!!!
От: kaa_t Россия  
Дата: 26.04.04 07:02
Оценка:
Здравствуйте, 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)


struct  oper 
{
    int    index;
    double    res;
    int    op;
};

double    calc( oper* d,int n )
{
    double res=0;
    for( int i=0;i<n;i++)
        {
      if( d[i].op == 1 ) 
      {
        d[i].res = varlist[ d[i].index ];
          }
          if( d[i].op == 2 )
          {
           d[i].res = d[i-1].res * d[i-2].res;
          }
          if( d[i].op == 3 )
          {
           d[i].res = d[i-1].res + d[i-2].res;
          }

           res = d[i].res;

        } 
       return res;
}
Re[4]: Частые вычисления по неопределенной формуле!!!
От: WolfHound  
Дата: 26.04.04 11:17
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Не думаю что будет быстрее. (автору темы важна скорость)

Как я и предсказывал
calc1_parse
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 2.3817
average middle = 2.38266

calc2_parse
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 2.39925
average middle = 2.4002

calc3_parse
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 2.32715
average middle = 2.34962

calc1_calculate
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 0.307994
average middle = 0.307279

calc2_calculate
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 0.285568
average middle = 0.285243

calc3_calculate
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
average all    = 0.2943
average middle = 0.294283

#pragma once
#define CALCULATOR3_CALL_CONVERSION __fastcall
struct calculator3
{
    calculator3()
        :grammar(*this)
    {}
    double& variable(std::string const& name);
    bool parse(std::string const& str);
    double calculate()
    {
        if(tokens.empty())
            return 0;
        double* s=&stack[0];
        for(std::vector<token>::iterator i=tokens.begin(), e=tokens.end();i!=e;++i)
            i->operation_fn(s, *i);
        return s[0];
    }
private:
    struct token;
    typedef void(CALCULATOR3_CALL_CONVERSION *operation_fn_t)(double*&, token const&);
    struct token
    {
        token(operation_fn_t _operation_fn)
            :operation_fn(_operation_fn)
        {}
        token(operation_fn_t _operation_fn, double _value)
            :operation_fn(_operation_fn)
            ,value(_value)
        {}
        token(operation_fn_t _operation_fn, double* _variable)
            :operation_fn(_operation_fn)
            ,variable(_variable)
        {}
        operation_fn_t operation_fn;
        union
        {
            double value;
            double* variable;
        };
    };
private:
    std::vector<token> tokens;
    std::vector<double> stack;
    spirit::symbols<double*> variables_p;
    std::map<std::string, double> variables;
private:
    size_t stack_deep;
    size_t stack_max_deep;

    void inc_stack()
    {
        if(++stack_deep>stack_max_deep)
            stack_max_deep=stack_deep;
    }
    void dec_stack()
    {
        --stack_deep;
    }
private:
    void add_binary_op(operation_fn_t op)
    {
        dec_stack();
        tokens.push_back(op);
    }
    void add_unary_op(operation_fn_t op)
    {
        tokens.push_back(op);
    }
    void add_variable(operation_fn_t _operation_fn, double* var)
    {
        inc_stack();
        tokens.push_back(token(_operation_fn, var));
    }
    void add_const(operation_fn_t _operation_fn, double val)
    {
        inc_stack();
        tokens.push_back(token(_operation_fn, val));
    }
private:
    static void CALCULATOR3_CALL_CONVERSION token_variable    (double*& s, token const& t){*++s=*t.variable;}
    static void CALCULATOR3_CALL_CONVERSION token_const        (double*& s, token const& t){*++s=t.value;}

    static void CALCULATOR3_CALL_CONVERSION token_op_add    (double*& s, token const& t){s[-1]=s[-1]+s[0];--s;}
    static void CALCULATOR3_CALL_CONVERSION token_op_sub    (double*& s, token const& t){s[-1]=s[-1]-s[0];--s;}
    static void CALCULATOR3_CALL_CONVERSION token_op_mul    (double*& s, token const& t){s[-1]=s[-1]*s[0];--s;}
    static void CALCULATOR3_CALL_CONVERSION token_op_div    (double*& s, token const& t){s[-1]=s[-1]/s[0];--s;}

    static void CALCULATOR3_CALL_CONVERSION token_op_neg    (double*& s, token const& t){s[0]=-s[0];}

    static void CALCULATOR3_CALL_CONVERSION token_fn_sin    (double*& s, token const& t){s[0]=sin(s[0]);}
    static void CALCULATOR3_CALL_CONVERSION token_fn_cos    (double*& s, token const& t){s[0]=cos(s[0]);}
private:
    struct calculator_grammar
        :spirit::grammar<calculator_grammar>
    {
        typedef calculator3 self_t;
        self_t& owner;
        calculator_grammar(self_t& _owner)
            :owner(_owner)
        {}
        template <typename ScannerT>
        struct definition
        {
            definition(calculator_grammar const& self_);

            spirit::rule<ScannerT> expression, term, factor;

            spirit::rule<ScannerT> const&
            start() const { return expression; }
        };
    };
    calculator_grammar grammar;
};
//cpp
#include "stdafx.h"
#include "calculator3.h"

double& calculator3::variable(std::string const& name)
{
    double& ref=variables[name];
    if(double** ptr=find(variables_p, name.c_str()))
        *ptr=&ref;
    else
        add(variables_p, name.c_str(), &ref);
    return ref;
}

bool calculator3::parse(std::string const& str)
{
    tokens.clear();
    stack_deep=0;
    stack_max_deep=0;
    if    (    !spirit::parse(str.c_str(), grammar, spirit::space_p).full
        ||    stack_deep!=1
        )
    {
        tokens.clear();
        return false;
    }
    stack.resize(stack_max_deep+2);
    return true;
}

template <typename ScannerT>
calculator3::calculator_grammar::definition<ScannerT>::definition(calculator_grammar const& self_)
{
    using namespace spirit;
    self_t& self=self_.owner;
    expression
        =   term
            >> *(   ('+' >> term)[lm::bind(&self_t::add_binary_op, &self, &self_t::token_op_add)]
                |   ('-' >> term)[lm::bind(&self_t::add_binary_op, &self, &self_t::token_op_sub)]
                )
        ;

    term
        =   factor
            >> *(   ('*' >> factor)[lm::bind(&self_t::add_binary_op, &self, &self_t::token_op_mul)]
                |   ('/' >> factor)[lm::bind(&self_t::add_binary_op, &self, &self_t::token_op_div)]
                )
        ;

    factor
        =   real_p[lm::bind(&self_t::add_const, &self, &self_t::token_const, _1)]
        |    self.variables_p[lm::bind(&self_t::add_variable, &self, &self_t::token_variable, _1)]

        |   (str_p("sin") >> '(' >> expression >> ')')[lm::bind(&self_t::add_unary_op, &self, &self_t::token_fn_sin)]
        |   (str_p("cos") >> '(' >> expression >> ')')[lm::bind(&self_t::add_unary_op, &self, &self_t::token_fn_cos)]

        |   '(' >> expression >> ')'
        |   ('-' >> factor)[lm::bind(&self_t::add_unary_op, &self, &self_t::token_op_neg)]
        |   ('+' >> factor)
        ;
}
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: Частые вычисления по неопределенной формуле!!!
От: c-smile Канада http://terrainformatica.com
Дата: 27.04.04 04:10
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, c-smile, Вы писали:


CS>>Только твой double calculate() (байткод стековая машина) теоретически медленнее чем прямое исполнения дерева операций.

WH>С какой это радости оно медленней?

Медленнее но "тильке трошки-трошки".
На самом деле ты прав наверное. Надо еще раз проверять.
С учетом function callв моем случае может и медленнее мой вариант.

И чтоб два раза не всавать — я был проверял executable goto в GCC, ну дык он мне дал 7% увеличение быстродействия в среднем при исполненни байткода по сравнению со switch.
Re[5]: Частые вычисления по неопределенной формуле!!!
От: sergey_shandar США http://getboost.codeplex.com/
Дата: 27.04.04 06:07
Оценка:
Здравствуйте, 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; }
};


PS. Не компилировал, просто высказал идею.
getboost.codeplex.com
citylizard.codeplex.com
Re[6]: Частые вычисления по неопределенной формуле!!!
От: Рома Мик Россия http://romamik.com
Дата: 27.04.04 09:44
Оценка:
Здравствуйте, sergey_shandar, Вы писали:

_>Может здесь передавать указатель на какую то структуру состояния, вместо двух параметров? Интересно, замедлит это или наоборот ускорит? Но, по моему, это более симпатичнее.

ИМХО симпатичнее всего ( но не быстрее, видимо ) иметь
struct token
{
    virtual void Do( stack &stk ) = 0;
};
... << RSDN@Home 1.1.3 beta 2 >>
Re[7]: Частые вычисления по неопределенной формуле!!!
От: sergey_shandar США http://getboost.codeplex.com/
Дата: 27.04.04 10:46
Оценка:
Здравствуйте, Рома Мик, Вы писали:

РМ>Здравствуйте, sergey_shandar, Вы писали:


_>>Может здесь передавать указатель на какую то структуру состояния, вместо двух параметров? Интересно, замедлит это или наоборот ускорит? Но, по моему, это более симпатичнее.

РМ>ИМХО симпатичнее всего ( но не быстрее, видимо ) иметь
РМ>
struct token
РМ>{
РМ>    virtual void Do( stack &stk ) = 0;
РМ>};


Я предлагаю больше информации передавать команде, т.е. полное состояние, ссылку на процесс, а не только на стек. Так что так будет более функционально:
struct token
{
    virtual void Do( process &prc ) = 0;
};


А замена виртуальной функции на указатель на функцию это всего лишь оптимизация, которая мало затрагивает возможности реализации. Но это уже больше к философии и к субъективности восприятия индивидуумами, а не к алгоритмам
getboost.codeplex.com
citylizard.codeplex.com
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.