Частые вычисления по неопределенной формуле!!! - Алгоритмы

Здравствуйте, 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 >>

Здравствуйте, WolfHound, Вы писали:

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

CS>>http://www.rsdn.ru/article/files/Classes/tparser.xml
WH>Он очень медленный.

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

Насколько я могу судить визально evaluation там сделана классически. Быстрее можно но не намного.

Здравствуйте, WolfHound, Вы писали:

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

Клево.

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

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

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

... << RSDN@Home 1.1.3 beta 1 >>

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

CS>Что конкретно там медленно: compilation или evaluation?
CS>Насколько я могу судить визально evaluation там сделана классически. Быстрее можно но не намного.
Я его очень давно тестил и цифры уже не помню. Но он слил моему аналогу (тогда я прикаловался с конечными автоматами) и там и там. Причем слил в разы.

... << RSDN@Home 1.1.3 beta 1 >>

Здравствуйте, 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 >>

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

WH>struct calculator 
WH>

Круто.

WH>А считать быстрее у тебя врятли получится.
ИМХО можно. Если вместо token.kind иметь указатель на функцию получающую в качестве аргумента ссылку на стек. Таким образом можно избавится от switch'а.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, Рома Мик, Вы писали:

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 >>

Здравствуйте, 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;
}

Здравствуйте, 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 >>

Здравствуйте, WolfHound, Вы писали:

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

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

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

И чтоб два раза не всавать — я был проверял executable goto в GCC, ну дык он мне дал 7% увеличение быстродействия в среднем при исполненни байткода по сравнению со switch.

Здравствуйте, 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. Не компилировал, просто высказал идею.

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

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

struct token
{
    virtual void Do( stack &stk ) = 0;
};

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, Рома Мик, Вы писали:

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

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

struct token
РМ>{
РМ>    virtual void Do( stack &stk ) = 0;
РМ>};

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

struct token
{
    virtual void Do( process &prc ) = 0;
};

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

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

; 14   :         double* s=&stack[0];
; 15   :         for(std::vector<token>::iterator i=tokens.begin(), e=tokens.end();i!=e;++i)

    cmp    esi, edi
    mov    eax, DWORD PTR [ecx+12]
    mov    DWORD PTR _s$[esp+12], eax
    je    SHORT $L113694
$L113692:

; 16   :             i->operation_fn(s, *i);

    mov    edx, esi
    lea    ecx, DWORD PTR _s$[esp+12]
    call    DWORD PTR [esi]
    add    esi, 16                    ; 00000010H
    cmp    esi, edi
    jne    SHORT $L113692
$L113694:

_>Тогда сдвиг итератора i
WH>> for(std::vector<token>::iterator i=tokens.begin(), e=tokens.end();i!=e;++i)
_>можно вынести в функции, если вынести i в процесс (это может быть полезно если в дальнейшем совершенствовать этот калькулятор, например сделать оператор if в выражениях). И условие выхода сделать в виде флага, а функция устанавливающая этот флаг пусть находиться в самом конце вектора tokens.
1)Это замедлит вычисления.
2)Этого в задаче небыло. И у меня нет жилания делать полноценный интерпритатор некоторого недо языка.

... << RSDN@Home 1.1.3 beta 1 >>

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

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

... << RSDN@Home 1.1.3 beta 1 >>

Всем огромное спасибище!!!
Теперь буду все это пережевывать

Здравствуйте, GrayWizard, Вы писали:

Два вопроса...

1. Список переменных изменяется или он фиксирован? Если изменяется то в каких пределах и как часто?

2. Какого рода система исползующая это дело? Как поставляется? На каких платформах должна работать?

... << RSDN@Home 1.1.3 beta 2 >>

можно полученную строку выполнить, запомнить указатели стека и в следующие раз считать без стека.

Здравствуйте, GrayWizard, Вы писали:

Варинт на дотнет... по просбам трудящихся

.

Сначала о результатах. Вот результаты C#-варианта:

Парсинг 10 проходов. Выполнено за 1.09794569 сек.
Подсчет 10000 проходов. Выполнено за 0.00378456 сек.
Подсчет 10000 проходов. Выполнено за 0.00379629 сек.

А вот малость переработанного варианта от WolfHound скомпилированного в анменеджед-релиз на VCX 7.1:

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.134409
average middle = 0.133799

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.0775661
average middle = 0.0772016

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.0776748
average middle = 0.0774767

Переработка заключалась в том, что я для ххх_calculate-тестов вынес парсинг за пределы измеряемой зоны. Естественно это ничего не дало, так как 10 000 итераций не идут ни в какое сравнение с одним проходом парсинга, но все же... чистота эксперемента тык-сызыть.

В приведенной выше ссылке я обещал WolfHound, что мой вариант сделает его на порядок. Примерно так и вышло. Лучшее время его варианта примерно в 20 раз меньше.

Вы спросите как удалось добиться таких показателей? Гы-гы.

Библиотеки у дотнета лучше. Ну, и как я уже говорил WolfHound выбрал принципиально далекое от оптимальности решение.

Чем не оптимальное? А... Он выбрал интерпретацию вместо компиляции. А она в худшем раскладе в разы медленнее. (Обычно на порядок.)

Суть моего решения элементарна. В программе где требуется вычислять формулы задаваемые строкой объявляется интерфейс в котором описываются сигнатуры методов. Далее они скармливаются простенькому энжину который на лету компилирует реализации и возвращает ссылку на сборку. От сборки получается ссылка на интерфейс, по которой и осуществляется вызов.

Вот так выглядит код теста:

class EntryPoint
{
    const int CalcCount  = 10000;
    const int ParseCount = 10;

    static void Main(string[] args)
    {
        //string formula = "asd + qwe";

        string formula =
            "-(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";

        PerfCounter timer = new PerfCounter();

        //////////////////////////////////////////////////////////////////////
        /// Разбор.
        ICalc1 calc1 = null;
        timer.Start();
        for (int i = 0; i < ParseCount; i++)
            calc1 = Calc1Impl.Prepare(formula);
        // Пре-компиляция
        calc1.Calc(1, 1);
        Console.WriteLine("Парсинг {1} проходов. Выполнено за {0:F8} сек.", 
            timer.Finish(), ParseCount);
        
        //////////////////////////////////////////////////////////////////////
        /// Вычисления. Первый проход.
        timer.Start();
        for (int i = 0; i < CalcCount; i++)
            calc1.Calc(i, i);
        Console.WriteLine("Подсчет {1} проходов. Выполнено за {0:F8} сек.", 
            timer.Finish(), CalcCount);

        //////////////////////////////////////////////////////////////////////
        /// Вычисления. Второй проход.
        timer.Start();
        for (int i = 0; i < CalcCount; i++)
            calc1.Calc(i, i);
        Console.WriteLine("Подсчет {1} проходов. Выполнено за {0:F8} сек.", 
            timer.Finish(), CalcCount);


        Console.WriteLine("Calc(1, 1)    = {0}", calc1.Calc(1, 1));
        Console.WriteLine("Calc(-1, 333) = {0}", calc1.Calc(-1, 333));


        Console.WriteLine("...");
        Console.ReadLine();
    }
}

А вот и реализация...
Сначала энжин компиляции:

using System;
using Microsoft.CSharp;
using System.CodeDom;
using System.CodeDom.Compiler;
using System.IO;
using System.Reflection;

namespace FuncEvalCs
{
    public class CalcEngine
    {
        public static Assembly Prepare(string code)
        {
            CompilerParameters compparams = new CompilerParameters();
            compparams.IncludeDebugInformation = false;
            compparams.CompilerOptions = @"/optimize+";
            compparams.GenerateExecutable = false;
            // В релаьной программе скомпилированные сборки можно кэшировать.
            // Для этого нужно отключить компиляцию в память и задать имя сборки
            compparams.GenerateInMemory = true;
            // compparams.OutputAssembly = @"c:\mySample.dll";
            compparams.ReferencedAssemblies.Add("System.dll");
            // Задаем ссылку на сборку производящую вызов. Это нужно для того
            // чтобы создаваемая сборка могла использовать типы из нее.
            // В частности чтобы можно было использовать интерфейсы через которые
            // будет производиться вызов.
            // В принципе если производить вызовы через рефлексию или делегаты,
            // этот момент можно избежать.
            string thisAsmPath = Environment.CurrentDirectory + @"\FuncEvalCs.exe";
            compparams.ReferencedAssemblies.Add(thisAsmPath);

            CSharpCodeProvider cscp = new CSharpCodeProvider();
            ICodeCompiler cscompiler = cscp.CreateCompiler();
            // Компилируем код из строки.
            CompilerResults compresult = 
                cscompiler.CompileAssemblyFromSource(compparams, code);
            
            // Если есть ошибки выводим сообщения о них...
            if (compresult == null || compresult.Errors.Count > 0)
            {
                for (int i = 0; i < compresult.Output.Count; i++)
                    Console.WriteLine(compresult.Output[i]);
                for (int i = 0; i < compresult.Errors.Count; i++)
                    Console.WriteLine(i + ": " + compresult.Errors[i].ToString());

                return null;
            }

            // Возвращаем скомпилированную сборку.
            return compresult.CompiledAssembly;
        }
    }
}

Интерфейс используемый для вызова формулы (их может быть любое количество и они могут содержать любое количество методов, в данном случае один — калька с теста WolfHound-а):

public interface ICalc1
{
    double Calc(double asd, double qwe);
}

А вот код необходимый для реализации интерфейса:

using System;
using System.Reflection;

namespace FuncEvalCs
{
    public class Calc1Impl
    {
        public static ICalc1 Prepare(string formulaCode)
        {
            // замена sin на Math.Sin нужна исключительно для совместимости
            // с примером WolfHound-а.
            formulaCode = formulaCode.Replace("sin", "Math.Sin");
            formulaCode = formulaCode.Replace("cos", "Math.Cos");
            Assembly asm = CalcEngine.Prepare(
                @"
using System;
using FuncEvalCs;

class EntryPoint : ICalc1
{
    public double Calc(double asd, double qwe)
    {
        return " + formulaCode + @";
    }
}
                ");
            
            return (ICalc1)asm.CreateInstance("EntryPoint");
        }
    }
}

Естественно, что текст формул можно заменять динамически... как в прочем и реализацию вообще.

ЗЫ

Итого в сухом остатке мы имеет:
1. Более чем в 20 раз высокую скорость исполнения. А если учесть, что можно использовать и более быстрые типы (например, int), то и 20 раз не предел.
2. Возможности по оптимизации вычислений. Ведь Jit-компилятор производит довольно неплохую оптимизацию.
3. Динамическое расширению библиотек и фасадного кода.
4. Возможность использовать любых функций (как из стандартной библиотеки дотнета — FCL, так и собственны).
5. Намного более мощный энжин вычислений. Синтаксис Шарпа или Васика (который тоже можно сюда подключить) куда мощнее примитивных самопальных парсеров.
6. Возможность подключения любого доступного для дотнета языка. Например, можно подключить функциональные языки вроде SML-я или Ocaml-а.
7. Типизированный парсер. Интерфейс не обязан работать с double-ами, как у WolfHound-а. Параметры могут передаваться по ссылке, быть пользовательского типа или массива.
8. Можно кэшировать результат компиляции, что значительно сократит время на повторные запуски.
9. Полноценные сообщения об ошибках.
10. Размер исполняемого файла 20 килобайт. Перекомпилированный нэйтив-мидж 16 кил. Размер генерируемой сборки 4 кил. Для сравнения размер по сравнению с 180 килобайтами у WolfHound-а (это еще в моем, упрощенном варинтае изначально он занимал 250 кил (по словам WolfHound-а)). Самым же смешным оказалось сравнение места занимаемого данными тестами после компиляции в релиз и дебаг... Проект на Шарпе занял 146 кил. А вот проект на С++ занял (ни за что не догадаетесь) 104... но мегабайта!

Все "богатство" естественно находится в каталогах Debug и Release. Первый занимает 49 мег., а второй 54. И все это "богатство", вы не поверите, с 19 кил исходников.

Если сравнивать размеры исходников, то один (самый шустрый) С++-вариант занимает 10 кил. Вариант же на Шарпе занимает 6 кил.
11. Более точные вычисления с плавающей точкой .NET использует для таких вычислений возможности текущего процессора. Например, на последних Intel-ах вычисления приводятся с точностью значительно превышающую возможности double-а. Так что если при вычислениях результаты превышают размеры double-а, точность не теряется.

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

Ну, и еще, если конечно это вообще недостаток — это дотнет.

2 WolfHound: Как я и говорил, разница в два раза между компиляторами просто фигня по сравнению с выбором оптимального решения/алгоритма/библиотеки.

Если же приспичит писать собственные парсеры, то нужно выбирать проверенные временем, дедовские способы — генераторы парсеров вроде yacc-а или Coca-и, а не заниматься извращениями на шаблонах. Тогда все не нужное в ратайме останется в компайл-тайме, а работа будет проще, качественнее и будет намного проще поддаваться расширению.

2 GrayWizard: Если тебе не приемлем .NET, то того же можно добиться и с помощью обычного компилятора C++. Правда повозиться придется несколько больше и скорость компиляции будет скорее всего ниже (особенно при массе инклюдов). Но тем не менее ты получишь значительно более шустрое и компактное решение нежели используя самопальный интерпретатор. На сегодня бесплатно доступны очень приличные компиляторы: бесплатный VC (правда похоже в нем нет многих оптимизаций как в коммерческом варианте, но все же это куда быстрее чем интерпретация), бесплатный BCC (Borland-овский компилятор добротен но не шустр), GCC (тянет за собой откровенно говоря не скромный по размерам runtime и не может поставляться совместно с коммерческим продуктом, так как GNU-ый, но зато самый быстрый из перечисленных вариантов). Ну, и если разработка внутренняя, то вообще нет проблем. Бери коммерческий VC или Intel C++. Будет и самый быстрый код.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, VladD2, Вы писали:

Да, если кому интересны исходники, то они здесь: http://www.rsdn.ru/File/73/ParserTest.zip

Там же лежат и релизные бинарники.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, VladD2, Вы писали:

[]

Супер!

Может я чего-то не понял, но ИМО говоря о плюсах использования компилятора в ран-тайме ты умолчал о минусах.

Близкий пример. Когда-то я слабал калькулятор на jscript, который использовал интерпретатор jscript для вычисления введенного мат. выражения, не производя самостоятельный разбор выражения. Так вот, если вместо "1+2" написать например "window.close()", то окно закрывалось.
Конечно приятно считать это фичей, но по существу для калькулятора это дыра.

Здравствуйте, folk, Вы писали:

F>Может я чего-то не понял, но ИМО говоря о плюсах использования компилятора в ран-тайме ты умолчал о минусах.

F>Близкий пример. Когда-то я слабал калькулятор на jscript, который использовал интерпретатор jscript для вычисления введенного мат. выражения, не производя самостоятельный разбор выражения. Так вот, если вместо "1+2" написать например "window.close()", то окно закрывалось.
F>Конечно приятно считать это фичей, но по существу для калькулятора это дыра.
Для этого есть Code Access Security. И можно коду этих выражений так яйца в тиски закрутить, что он даже взгляд кинуть куда не надо не посмеет. Это вам не С++

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, VladD2, Вы писали:

VD>В приведенной выше ссылке я обещал WolfHound, что мой вариант сделает его на порядок. Примерно так и вышло. Лучшее время его варианта примерно в 20 раз меньше.

Не так-то все однозначно. Допустим пользователю по каждой новой формуле нужно сделать не более N операций. Для каких N твоя реализация будет быстрее, чем WolfHound-а? N > 3000. Если, например, эти вычисления встроены в программу электронной таблицы, то N явно < 3000, и реализация с отдельным вызовом компилятора не годится. А если N ~ 100, то, наоборот, программа WolfHound-а становится в 20 раз быстрее твоей.

Здравствуйте, VladD2, Вы писали:

Для затравки, вот ссылочка: Компилятор в RunTime
Уверен, что любой человек, хоть раз писавший на асме хоть чуть-чуть, способен в принципе сотворить подобное.

VD>Библиотеки у дотнета лучше.
Ну, библиотеки тут не причем.

VD>10. Размер исполняемого файла 20 килобайт. Перекомпилированный нэйтив-мидж 16 кил. Размер генерируемой сборки 4 кил. Для сравнения размер по сравнению с 180 килобайтами у WolfHound-а (это еще в моем, упрощенном варинтае изначально он занимал 250 кил (по словам WolfHound-а)). Самым же смешным оказалось сравнение места занимаемого данными тестами после компиляции в релиз и дебаг... Проект на Шарпе занял 146 кил. А вот проект на С++ занял (ни за что не догадаетесь) 104... но мегабайта!

А теперь приплюсуй к размеру проекта на Шарпе размера дотнетовского рантайма.

VD>Если сравнивать размеры исходников, то один (самый шустрый) С++-вариант занимает 10 кил. Вариант же на Шарпе занимает 6 кил.
А вот вообще круто. На c++ написан какие-никакие, но парсер и интерпретатор, а на шарпе написано обращение к библиотеке содержащей эти самые парсер и интерпретатор. К слову сказать, минимальный проект, использующий, например, lua, занимает поменьше 6кб. Есть например возможность быстро и легко использовать JavaScript, правда там я размер минимального проекта не скажу, но тоже в том же порядке.

VD>2 WolfHound: Как я и говорил, разница в два раза между компиляторами просто фигня по сравнению с выбором оптимального решения/алгоритма/библиотеки.

VD>Если же приспичит писать собственные парсеры, то нужно выбирать проверенные временем, дедовские способы — генераторы парсеров вроде yacc-а или Coca-и, а не заниматься извращениями на шаблонах. Тогда все не нужное в ратайме останется в компайл-тайме, а работа будет проще, качественнее и будет намного проще поддаваться расширению.
Собственно spirit по простоте поддержки и расширения гораздо лучше старых дедовских способов вроде yacc'а. Да и сам он скоро перейдет в разряд старых, дедовских способов.

VD>2 GrayWizard: Если тебе не приемлем .NET, то того же можно добиться и с помощью обычного компилятора C++. Правда повозиться придется несколько больше и скорость компиляции будет скорее всего ниже (особенно при массе инклюдов). Но тем не менее ты получишь значительно более шустрое и компактное решение нежели используя самопальный интерпретатор. На сегодня бесплатно доступны очень приличные компиляторы: бесплатный VC (правда похоже в нем нет многих оптимизаций как в коммерческом варианте, но все же это куда быстрее чем интерпретация), бесплатный BCC (Borland-овский компилятор добротен но не шустр), GCC (тянет за собой откровенно говоря не скромный по размерам runtime и не может поставляться совместно с коммерческим продуктом, так как GNU-ый, но зато самый быстрый из перечисленных вариантов). Ну, и если разработка внутренняя, то вообще нет проблем. Бери коммерческий VC или Intel C++. Будет и самый быстрый код.
ИМХО если уж таскать за собой компилятор, то какой-нибудь маленький и простой. Есть же компиляторы с C, а не с C++ хотя бы.
Но интереснее всего, как предполагается осуществлять взаимодействие с скомпилированным результатом? Компилировать в dll и динамически ее подлинковывать?

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, folk, Вы писали:

F>Может я чего-то не понял, но ИМО говоря о плюсах использования компилятора в ран-тайме ты умолчал о минусах.

F>Близкий пример. Когда-то я слабал калькулятор на jscript, который использовал интерпретатор jscript для вычисления введенного мат. выражения, не производя самостоятельный разбор выражения. Так вот, если вместо "1+2" написать например "window.close()", то окно закрывалось.
F>Конечно приятно считать это фичей, но по существу для калькулятора это дыра.

Есля и начну говорить о минусах связаных с С++, то меня тут могут и поубивать.

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

Здравствуйте, alexkro, Вы писали:

A>Не так-то все однозначно. Допустим пользователю по каждой новой формуле нужно сделать не более N операций. Для каких N твоя реализация будет быстрее, чем WolfHound-а? N > 3000. Если, например, эти вычисления встроены в программу электронной таблицы, то N явно < 3000, и реализация с отдельным вызовом компилятора не годится. А если N ~ 100, то, наоборот, программа WolfHound-а становится в 20 раз быстрее твоей.

Я исходил из условий задачи. Да и описанная тобой ситуация встречается редко.

Здравствуйте, Рома Мик, Вы писали:

РМ>Уверен, что любой человек, хоть раз писавший на асме хоть чуть-чуть, способен в принципе сотворить подобное.

Все меньше и меньше таких людей отстается. И по-моему — это правильно.

VD>>Библиотеки у дотнета лучше.
РМ>Ну, библиотеки тут не причем.

Кому как.

РМ>А теперь приплюсуй к размеру проекта на Шарпе размера дотнетовского рантайма.

Я знал, что это кто-нить скажет. Так вот дотнет входит во второй сервиспак к ХРюше. Во все остальные ОС он встроен штатно. Ну, и даже если его и нет, то ставится он один раз.

РМ>А вот вообще круто. На c++ написан какие-никакие, но парсер и интерпретатор,

Во-во. Никакие.

РМ>а на шарпе написано обращение к библиотеке содержащей эти самые парсер и интерпретатор.

Это называется фрэймворк.

РМ>К слову сказать, минимальный проект, использующий, например, lua, занимает поменьше 6кб. Есть например возможность быстро и легко использовать JavaScript, правда там я размер минимального проекта не скажу, но тоже в том же порядке.

Ну, минимальный проект я тоже в пару сотин байт умещу, вот только зачем? Качество не заменишь краткостью.

РМ>Но интереснее всего, как предполагается осуществлять взаимодействие с скомпилированным результатом? Компилировать в dll и динамически ее подлинковывать?

Общий принцип я уже продемонстрировал. Описываешь интерфейсыю... (для С++ за основу нужно взять КОМ-интерфейсы, т.е. классы с чисто виртуальными методами и без данных) Далаешь фабрику классов (опять же на подобии КОМ-а) которая возвращает ссылку на интерфейс реализуемый классам... Получаешь указатель... Приводишь его к указателю на требуемый интерфейс и пользуешся.

Здравствуйте, VladD2, Вы писали:

А если потребуется какойнибудь синтаксис который не поддерживается CodeDom.Compiler'ом?
Допустим заказчик хочет возводить в степень так "asd^(qwe*asd)"
Я всеголишь добавлю выделеное(Это переделаный calculator3 я его еще маленько порефакторил)

...
static void CALCULATOR4_CALL_CONVERSION token_op_pow    (double*& s, token const& t){s[-1]=pow(s[-1], s[0]);--s;}
...
template <typename ScannerT>
calculator4::calculator_grammar::definition<ScannerT>::definition(calculator_grammar const& self_)
{
    using namespace spirit;
    self_t& self=self_.owner;
    priority1
        =   priority2
            >> *(   ('+' >> priority2)[lm::bind(&self_t::add_binary_op, &self, &token_op_add)]
                |   ('-' >> priority2)[lm::bind(&self_t::add_binary_op, &self, &token_op_sub)]
                )
        ;

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

    priority3
        =   factor
            >> *(   ('^' >> factor)[lm::bind(&self_t::add_binary_op, &self, &token_op_pow)]
                )
        ;

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

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

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

А ты что будешь делать?

... << RSDN@Home 1.1.3 beta 1 >>

Здравствуйте, WolfHound, Вы писали:

WH>А если потребуется какойнибудь синтаксис который не поддерживается CodeDom.Compiler'ом?

А требуется?

WH>Допустим заказчик хочет возводить в степень так "asd^(qwe*asd)"

О. Задача из серии неберучек.

Я там в коде меняю sin на Math.Sin... Подход в народе называется препроцесирование. Твой случай решается им на ура.

WH>Я всеголишь добавлю...

И получишь еще 100 кил кода.

гора кода поскипана.

WH>А ты что будешь делать?

Ну, я как бы выше скзал. А вообще это синтаксис Васика. Так что моно его подключить.

ЗЫ

Если уж писать полноценные парсеры, то делать это лучше на базе кодогенератора вроде яка или каки. Но об этоя я уже гворил.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, VladD2, Вы писали:

VD>А требуется?
Допустим

VD>О. Задача из серии неберучек.

Чего?

VD>Я там в коде меняю sin на Math.Sin... Подход в народе называется препроцесирование. Твой случай решается им на ура.
Уверен? И чтобы приоритет операций учесть... И скобочки...

VD>И получишь еще 100 кил кода.
Сколько было столько и осталось... Размер байт в байт совпадает...

VD>Ну, я как бы выше скзал. А вообще это синтаксис Васика. Так что моно его подключить.
А потом еще чего захотят... Типа плюсового a<b?a:b...

VD>Если уж писать полноценные парсеры, то делать это лучше на базе кодогенератора вроде яка или каки. Но об этоя я уже гворил.

Вот сам этим и пользуйся

... << RSDN@Home 1.1.3 beta 1 >>

Здравствуйте, VladD2, Вы писали:

VD>Если уж писать полноценные парсеры, то делать это лучше на базе кодогенератора вроде яка или каки. Но об этоя я уже гворил.

Непонятное утверждение. Чем yacc лучше spirit'а? Тем что он написан на C и генерит сишный же код, что засунуть в программу два парсера уже проблема?

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, Рома Мик, Вы писали:

РМ>Непонятное утверждение. Чем yacc лучше spirit'а?

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

РМ> Тем что он написан на C и генерит сишный же код, что засунуть в программу два парсера уже проблема?

Нет конечно. Ты просто недооцениваешь современные yacc-и и им подобные программы. Они уже давно научились генерировать код не только на С. Парсер Моно — это модификация якак (по имени jay) генерирующая ОО-код на C# (или Яве), например.

Наш R# делается с использованием CocoR. Есть еще ANTLR и много других.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, WolfHound, Вы писали:

VD>>А требуется?
WH>Допустим

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

VD>>О. Задача из серии неберучек.

WH>Чего?

В детском саду била такая прилипчивая поговорка. "Ххх небуручка, кто взял, то ванючка."

.

VD>>Я там в коде меняю sin на Math.Sin... Подход в народе называется препроцесирование. Твой случай решается им на ура.
WH>Уверен? И чтобы приоритет операций учесть... И скобочки...

Скобки сами собой учтутся. В общем, что выдумывать. Создавать свой язык из-за вычислителя формул не размумно. Проще взять готовый.

VD>>И получишь еще 100 кил кода.
WH>Сколько было столько и осталось... Размер байт в байт совпадает...

Ага. Я из твоего кода выкинул пару фигни и 40 кил как ххх сбрило.

VD>>Ну, я как бы выше скзал. А вообще это синтаксис Васика. Так что моно его подключить.
WH>А потом еще чего захотят... Типа плюсового a<b?a:b...

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

VD>>Если уж писать полноценные парсеры, то делать это лучше на базе кодогенератора вроде яка или каки. Но об этоя я уже гворил.

WH>

Вот сам этим и пользуйся

Сам и пользуюсь. А опечатки и у тебя не редкость. Хотя мои конечно круче.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, Sinclair, Вы писали:

F>>Конечно приятно считать это фичей, но по существу для калькулятора это дыра.

S>Для этого есть Code Access Security. И можно коду этих выражений так яйца в тиски закрутить, что он даже взгляд кинуть куда не надо не посмеет. Это вам не С++

Может ли это повлиять на производительность вызова?

Здравствуйте, folk, Вы писали:

F>Близкий пример. Когда-то я слабал калькулятор на jscript, который использовал интерпретатор jscript для вычисления введенного мат. выражения, не производя самостоятельный разбор выражения. Так вот, если вместо "1+2" написать например "window.close()", то окно закрывалось.
F>Конечно приятно считать это фичей, но по существу для калькулятора это дыра.

Как ты умудрился это сделать? window — это часть DOM, а не javascript как языка. Или приложение работало в браузере?

Здравствуйте, Воронков Василий, Вы писали:

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

F>>Близкий пример. Когда-то я слабал калькулятор на jscript, который использовал интерпретатор jscript для вычисления введенного мат. выражения, не производя самостоятельный разбор выражения. Так вот, если вместо "1+2" написать например "window.close()", то окно закрывалось.
F>>Конечно приятно считать это фичей, но по существу для калькулятора это дыра.

ВВ>Как ты умудрился это сделать? window — это часть DOM, а не javascript как языка. Или приложение работало в браузере?

Да, это hta, я его когда-то выкладывал в исходники.
Кстати до сих пор пользуюсь, надо сохранить текст как файл с расширением .hta и запустить. Чтобы увидет хелп надо развернуть окно.

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<META NAME="Author" CONTENT="Konstantin A. Echenko, 2002">
<HTML>
<SCRIPT>window.resizeTo(400, 150)</SCRIPT>
<HEAD>
 <TITLE>Calc PRO</TITLE>
 <HTA:APPLICATION ICON="calc.exe">
</HEAD>
<BODY BGCOLOR="buttonface" SCROLL="no">
<FORM ID="form" onsubmit="calc(); return false">
 <INPUT TYPE="text" ID="expr"   STYLE="width:100%">
 <INPUT TYPE="text" ID="result" STYLE="width:100%" READONLY="true">
 <INPUT TYPE="submit" VALUE="=" STYLE="width:100%;color:red">
</FORM>
<SCRIPT>
 form.expr.select();
 function calc()
 {
  try { with(Math) form.result.value = eval(form.expr.value); }
  catch(error) { form.result.value = error.description; }
  form.expr.select();
 }
</SCRIPT>

<TABLE BORDER="0" STYLE="width:100%;font-size:X-Small"><TBODY VALIGN="top">
 <TR>
  <TH COLSPAN="2">Функции</TH><TH COLSPAN="2">Константы</TH>
 </TR><TR>
  <TD><B>abs</B>(<I>x</I>)</TD><TD>Отбрасывает знак</TD>
  <TD><B>E</B></TD><TD>Число <I>e</I>, константа Эйлера</TD>
 </TR><TR>
  <TD><B>acos</B>(<I>x</I>)</TD><TD>Арккосинус</TD>
  <TD><B>LN2</B></TD><TD>Натуральный логарифм 2</TD>
 </TR><TR>
  <TD><B>asin</B>(<I>x</I>)</TD><TD>Арксинус</TD>
  <TD><B>LN10</B></TD><TD>Натуральный логарифм 10</TD>
 </TR><TR>
  <TD><B>atan</B>(<I>x</I>)</TD><TD>Арктангенс</TD>
  <TD><B>LOG2E</B></TD><TD>Логарифм <I>e</I> по основанию 2</TD>
 </TR><TR>
  <TD><B>ceil</B>(<I>x</I>)</TD><TD>Округление вверх</TD>
  <TD><B>LOG10E</B></TD><TD>Логарифм <I>e</I> по основанию 10</TD>
 </TR><TR>
  <TD><B>cos</B>(<I>x</I>)</TD><TD>Косинус</TD>
  <TD><B>PI</B></TD><TD>Число <I>пи</I></TD>
 </TR><TR>
  <TD><B>exp</B>(<I>x</I>)</TD><TD><I>e</I> в степени <I>x</I></TD>
  <TD><B>SQRT1_2</B></TD><TD>Квадратный корень из 0.5</TD>
 </TR><TR>
  <TD><B>floor</B>(<I>x</I>)</TD><TD>Округление вниз</TD>
  <TD><B>SQRT2</B></TD><TD>Квадратный корень из 2</TD>
 </TR><TR>
  <TD><B>log</B>(<I>x</I>)</TD><TD>Натуральный логарифм</TD>
 </TR><TR>
  <TD><B>max</B>(<I>x</I>,<I>y</I>)</TD><TD>Большее из двух чисел</TD>
 </TR><TR>
  <TD><B>min</B>(<I>x</I>,<I>y</I>)</TD><TD>Меньшее из двух чисел</TD>
 </TR><TR>
  <TD><B>pow</B>(<I>x</I>,<I>y</I>)</TD><TD><I>x</I> в степени <I>y</I></TD>
 </TR><TR>
  <TD><B>random</B>()</TD><TD>Случайное число между 0 и 1</TD>
 </TR><TR>
  <TD><B>round</B>(<I>x</I>)</TD><TD>Округление к ближайшему</TD>
 </TR><TR>
  <TD><B>sin</B>(<I>x</I>)</TD><TD>Синус</TD>
 </TR><TR>
  <TD><B>sqrt</B>(<I>x</I>)</TD><TD>Квадратный корень</TD>
 </TR><TR>
  <TD><B>tan</B>(<I>x</I>)</TD><TD>Тангенс</TD>
 </TR>
</TBODY></TABLE>
</BODY>
</HTML>

	От:	GrayWizard
	Дата:	22.04.04 05:58
	Оценка:

	От:	_temp_
	Дата:	22.04.04 06:55
	Оценка:

	От:	ch00k
	Дата:	22.04.04 07:54
	Оценка:

От:	c-smile	http://terrainformatica.com
Дата:	22.04.04 15:56
Оценка:

	От:	WolfHound
	Дата:	23.04.04 21:10
	Оценка:

От:	Рома Мик	http://romamik.com
Дата:	25.04.04 16:19
Оценка:	+1

От:	sergey_shandar	http://getboost.codeplex.com/
Дата:	27.04.04 06:07
Оценка:

От:	VladD2	www.nemerle.org
Дата:	06.05.04 00:32
Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	07.05.04 06:32
Оценка:	3 (1)

	От:	Воронков Василий
	Дата:	09.05.04 10:51
	Оценка:

	От:	kaa_t
	Дата:	26.04.04 07:02
	Оценка: