Реализация анализатора (парсера) формул времени выполнения Опции

[AntonTatu]

Всем привет !

Вопрос в следующем, имеется прога которая генерирует некоторую формулу (формула меняет количество своих параметров в зависимости от исходных значений в программе ), в этой же проге есть массив который использует полученную формулу в дальнейших расчетах, хочется создать из формулы dll ку и потом ее вызывать в нужном месте программы, как это сделать? С вызовом полученной dll я вроде бы разобрался, а вот как научить прогу генерить dll ку понять не могу.

ЗЫ: Какие можно использовать компилятор/линковщик (минимум занимаемого места, требуемых для работы файлов, потдержка STL требуется)

Выручайте ! Спасибо !

[BRE]

Пример:

array2d.h

#ifndef __ARRAY2D
#define __ARRAY2D

#include <QObject>
#include <vector>

class Array2D : public QObject
{
        Q_OBJECT
public:
        Array2D( int dx, int dy );

public Q_SLOTS:
        char    at( int i, int j ) const;
        void    set( int i, int j, char val );

        inline  int             dx() const { return m_dx; }
        inline  int             dy() const { return m_dy; }

private:
        int             m_dx;
        int             m_dy;
        std::vector< std::vector<char> > *m_data;
};

#endif

array2d.cpp

#include "array2d.h"

Array2D::Array2D( int dx, int dy )
        : m_dx( dx ), m_dy( dy )
{
        m_data = new std::vector< std::vector<char> >( m_dx );
        for( int i = 0; i < m_dx; ++i )
                (*m_data)[ i ] = std::vector<char>( m_dy );
}

char Array2D::at( int i, int j ) const
{
        Q_ASSERT( i > 0 && i < m_dx );
        Q_ASSERT( j > 0 && j < m_dy );
        return (*m_data)[ i ][ j ];
}

void Array2D::set( int i, int j, char val )
{
        Q_ASSERT( i > 0 && i < m_dx );
        Q_ASSERT( j > 0 && j < m_dy );
        (*m_data)[ i ][ j ] = val;
}

main.cpp

#include <QApplication>         
#include <QScriptEngine>        
#include <QDebug>
#include "array2d.h"

const int arrDx = 5;
const int arrDy = 5;

void dump( const Array2D &arr )
{
        for( int i = 0; i < arr.dx(); ++i )
                for( int j = 0; j < arr.dy(); ++j )
                        qDebug( "item [%i, %i] = %i", i, j, arr.at( i, j ) );
}

int main( int argc, char *argv[] )
{
        QApplication app( argc, argv );

        Array2D arr( arrDx, arrDy );

        for( int i = 0; i < arr.dx(); ++i )
                for( int j = 0; j < arr.dy(); ++j )
                        arr.set( i, j, i + j );

        dump( arr );

        QScriptEngine se;
        se.globalObject().setProperty( "arr", se.newQObject( &arr ) );

        QScriptValue fun = se.evaluate( "function( i, j ) { print( i, j ); return arr.at( i, j ); }" );
        QScriptValueList args;
        args << QScriptValue( &se, 1 ) << QScriptValue( &se, 4 );
        QScriptValue y = fun.call( QScriptValue(), args );
        qDebug() << y.toNumber();

        return 0;
}

Высокой скорости вычисления от скриптов ожидать не стоит (от нативной она будет сильно отличаться).

[BRE]

Пример:

array2d.h

#ifndef __ARRAY2D
#define __ARRAY2D

#include <QObject>
#include <vector>

class Array2D : public QObject
{
        Q_OBJECT
public:
        Array2D( int dx, int dy );
                ~Array2D();

public Q_SLOTS:
        char    at( int i, int j ) const;
        void    set( int i, int j, char val );

        inline  int             dx() const { return m_dx; }
        inline  int             dy() const { return m_dy; }

private:
        int             m_dx;
        int             m_dy;
        std::vector< std::vector<char> > *m_data;
};

#endif

array2d.cpp

#include "array2d.h"

Array2D::Array2D( int dx, int dy )
        : m_dx( dx ), m_dy( dy )
{
        m_data = new std::vector< std::vector<char> >( m_dx );
        for( int i = 0; i < m_dx; ++i )
                (*m_data)[ i ] = std::vector<char>( m_dy );
}

Array2D::~Array2D()
{
                delete m_data;
}

char Array2D::at( int i, int j ) const
{
        Q_ASSERT( i > 0 && i < m_dx );
        Q_ASSERT( j > 0 && j < m_dy );
        return (*m_data)[ i ][ j ];
}

void Array2D::set( int i, int j, char val )
{
        Q_ASSERT( i > 0 && i < m_dx );
        Q_ASSERT( j > 0 && j < m_dy );
        (*m_data)[ i ][ j ] = val;
}

main.cpp

#include <QApplication>         
#include <QScriptEngine>        
#include <QDebug>
#include "array2d.h"

const int arrDx = 5;
const int arrDy = 5;

void dump( const Array2D &arr )
{
        for( int i = 0; i < arr.dx(); ++i )
                for( int j = 0; j < arr.dy(); ++j )
                        qDebug( "item [%i, %i] = %i", i, j, arr.at( i, j ) );
}

int main( int argc, char *argv[] )
{
        QApplication app( argc, argv );

        Array2D arr( arrDx, arrDy );

        for( int i = 0; i < arr.dx(); ++i )
                for( int j = 0; j < arr.dy(); ++j )
                        arr.set( i, j, i + j );

        dump( arr );

        QScriptEngine se;
        se.globalObject().setProperty( "arr", se.newQObject( &arr ) );

        QScriptValue fun = se.evaluate( "function( i, j ) { print( i, j ); return arr.at( i, j ); }" );
        QScriptValueList args;
        args << QScriptValue( &se, 1 ) << QScriptValue( &se, 4 );
        QScriptValue y = fun.call( QScriptValue(), args );
        qDebug() << y.toNumber();

        return 0;
}

Высокой скорости вычисления от скриптов ожидать не стоит (от нативной она будет сильно отличаться).

[Гость_Гость_AntonTatu_*_*]

Высокой скорости вычисления от скриптов ожидать не стоит (от нативной она будет сильно отличаться).

спасибо, так то же попробывал..., очень медленно в 1000 раз на глазок если, вобщем вопрос не снят, каким образом можно из проги получать код и компилить его "нативно"....? я уже весь инет перелазил, ну не писать же собственный компилятор.... (для меня это не реально )

[BRE]

спасибо, так то же попробывал..., очень медленно в 1000 раз на глазок если, вобщем вопрос не снят, каким образом можно из проги получать код и компилить его "нативно"....? я уже весь инет перелазил, ну не писать же собственный компилятор.... (для меня это не реально )

Уточни, из каких операций будет состоять формула (+ - * /)? Или будут еще какие-то функции?
Опиши подробней.
Ты используешь 2-мерный массив, это не изображение часом, а формула - не фильтр ли?

[AntonTatu]

спасибо, так то же попробывал..., очень медленно в 1000 раз на глазок если, вобщем вопрос не снят, каким образом можно из проги получать код и компилить его "нативно"....? я уже весь инет перелазил, ну не писать же собственный компилятор.... (для меня это не реально )

Уточни, из каких операций будет состоять формула (+ - * /)? Или будут еще какие-то функции?
Опиши подробней.
Ты используешь 2-мерный массив, это не изображение часом, а формула - не фильтр ли?

все намного про ще, генерится специальным образом массив, считается формула такого вида:
x[0,j]*x[2,j]*x[5,j]*x[10,j]+x[0,j]*x[3,j]*x[4,j]+N+.....
формула считается в цикле, с каждой итерацией формула новая, ее длинна то же может изменится..., переменные в формуле это значения разных ячеек массива, на выходе каждой итерации необходимо получить расчетное значение итой формулы, колличество прогонов (итераций) миллионы....

[BRE]

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

Исходя из этого сообщения, я не представляю реализацию с dll.
Алгоритм:

Рассчитали и заполнили массив с переменными;
for( миллион итераций )
{
Получили строку с формулой;
Сгенерировали исходный файл (не важно С/asm);

Запустили компилятор;
Дождались завершения компиляции;

Запустили линкер;
Дождались завершения линковки;

Загрузили dll;
Resolve функцию;
Выполнили функцию;

Вернули результат;
}

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

Как генерируется сама формула? Обьясни по-подробней, чувствую все можно сделать проще и не такими экзотическими способами.

[AntonTatu]

Исходя из этого сообщения, я не представляю реализацию с dll.

Я дико извиняюсь, ввел всех в заблуждение (сижу понять не могу фигню какую то написал в предыдущем своем посте), правильно так:

Алгоритм:

1. Считается формула такого вида:

x[0,j]*x[2,j]*x[5,j]*x[10,j]+x[0,j]*x[3,j]*x[4,j]+N+.....

формула может быть разной в зависимости от задачи (разной длинны, с разным количеством переменных, но структура именно такая как показано
2. Из формулы генерится dll

в цикле (100000 раз){
2. Генерится специальным образом массив, ячеек в массиве столько сколько переменных x[переменная,j] в формуле
3. формула высчитывается по массиву (подготовленной dll)
4. Записывается ответ
}

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

Теперь алгоритм верный, может у кого рнибудь есть предложения , куда "копать" ?

Сообщение отредактировал AntonTatu - 6.3.2009, 21:25

[BRE]

Алгоритм:

1. Считается формула такого вида:

x[0,j]*x[2,j]*x[5,j]*x[10,j]+x[0,j]*x[3,j]*x[4,j]+N+.....

формула может быть разной в зависимости от задачи (разной длинны, с разным количеством переменных, но структура именно такая как показано
2. Из формулы генерится dll

в цикле (100000 раз){
2. Генерится специальным образом массив, ячеек в массиве столько сколько переменных x[переменная,j] в формуле
3. формула высчитывается по массиву (подготовленной dll)
4. Записывается ответ
}

Ага.
Как вариант:

1. Считается формула
2. Распарсивается в обратную польскую, только место конкретных чисел храняться ссылки на соответствующие элементы в массиве.
в цикле (100000 раз)
{
3. Генерится специальным образом массив, ячеек в массиве столько сколько переменных x[переменная,j] в формуле
4. запускается расчет формулы (место ссылок на элементы подставляются значения из массива)
5. Записывается ответ
}

Т.е. сначала готовим формулу для быстрого вычисления.

[AntonTatu]

4. запускается расчет формулы (место ссылок на элементы подставляются значения из массива)

я вот этот пункт понять не могу, есть у меня формула (строка типа QString), преобразовал я ее в обратную польскую, (это значит распарсил ?), а что значит "в место ссылок на элементы подставляются значения из массива" ?
я просто не понимаю, если я формулу преобразовал в обратную польскую на выходе тоже ж QString ?

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


подумал еще , а может как вариант создать класс (структуру) в котором хранить переменные функции, ссылки на ячейки массива и знак (+ или *) следуемый за переменной , и запихать все это в односвязаный список, делать обход списка от начала в конец и таким образом проводить расчет функции ?

Сообщение отредактировал AntonTatu - 7.3.2009, 1:07

[BRE]

подумал еще , а может как вариант создать класс (структуру) в котором хранить переменные функции, ссылки на ячейки массива и знак (+ или *) следуемый за переменной , и запихать все это в односвязаный список, делать обход списка от начала в конец и таким образом проводить расчет функции ?

+1

Парсер переводит математическую формулу в список необходимых операций.

Делаем класс стек выполнений:

class MathStack : protected QStack<double>
{
public:
    void     push( double );
    double pop();
};

Вводим виртуальный базовый класс для всех операций:

class Operation
{
public:
    void    run() = 0;    //выполнить операцию

protected:
    static MathStack    m_stack;    // стек общий для всех операций
    friend class Formula;                // для возможности доступа к арифметическому стеку
};

class VarOp : public Operation
{
public:
    VarOp( const double &val  );

    void    run();

private:
    const double    &m_var;
};

class AddOp : public Operation
{
public:
    void    run();
};

class SubOp : public Operation
{
    ...
};

VarOp::VarOp( const double &var )
    : m_var( var )
{
}

// Поместить переменную на арифметический стек
void VarOp::run()
{
    m_stack.push( var );
}

// Снять с арифметического стека два числа, сложить их и результат положить обратно на стек
void AddOp::run()
{
    double v1 = m_stack.pop();
    double v2 = m_stack.pop();
    m_stack.push( v1 + v2 );
}

// Снять с арифметического стека два числа, вычесть их и результат положить обратно на стек
void SubOp::run()
{
    double v1 = m_stack.pop();
    double v2 = m_stack.pop();
    m_stack.push( v1 - v2 );
}

Вводим класс формулу (список операций):

class Formula
{
public:
    void     addOp( Operation *op );
    double calc() const;

private:
    typedef QList<Operation*> ListOp;
    ListOp     m_ops;
};

// Добавить операцию в список
void Formula::add( Operation *op )
{
    m_ops.append( op );
}

// Вычислить формулу
double Formula::calc()
{
    // Выполнить все операции
    for( ListOp::ConstIteration iOp = m_ops.begin(); iOp != m_ops.end(); ++i )
        (*iOp)->run();

    // После выполнения на вершине арифметического стека результат
    return Operation::m_stack.pop();
}

Теперь, формула A + B * C + D в обратной польской нотации будет: ABC*+D+

Для примера:
A - arr[ 0 ][ 4 ];
B - arr[ 3 ][ 7 ];
C - arr[ 7 ][ 1 ];
D - arr[ 4 ][ 8 ];

Array2D arr;

Formula f;
f.addOp( new VarOp( &arr[ 0 ][ 4 ] ) );
f.addOp( new VarOp( &arr[ 3 ][ 7 ] ) );
f.addOp( new VarOp( &arr[ 7 ][ 1 ] ) );
f.addOp( new MulOp() );
f.addOp( new AddOp() );
f.addOp( new VarOp( &arr[ 4 ][ 8 ] ) );
f.addOp( new AddOp() );

for( много итераций )
{
    calcArray( arr );
    double res = f.calc();
}

Как с этим закончим, можно будет попробовать оптимизировать.

[AntonTatu]

Как с этим закончим, можно будет попробовать оптимизировать.

Третий день сижу, что то не побороть никак,

------ Построение начато: проект: one, Конфигурация: Debug Win32 ------
Компиляция...
main.cpp
Компоновка...
main.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: void __thiscall MathStack::push(double)" (?push@MathStack@@QAEXN@Z) в функции "public: virtual void __thiscall VarOp::run(void)" (?run@VarOp@@UAEXXZ)
main.obj : error LNK2001: неразрешенный внешний символ ""protected: static class MathStack Operation::m_stack" (?m_stack@Operation@@1VMathStack@@A)"
C:\Documents and Settings\Anton\Мои документы\Visual Studio 2008\Projects\one\Debug\one.exe : fatal error LNK1120: 2 неразрешенных внешних элементов
Журнал построения был сохранен в "file://c:\Documents and Settings\Anton\Мои документы\Visual Studio 2008\Projects\one\one\Debug\BuildLog.htm"
one - ошибок 3, предупреждений 0
========== Построение: успешно: 0, с ошибками: 1, без изменений: 0, пропущено: 0 ==========

Переписал вот что :

class Operation
{
public:
    virtual void    run() = 0;    //выполнить операцию

и

class VarOp : public Operation
{
public:
    VarOp( const double &var  );

но это что называется в глаза бросилось... а ошибки все равно сыплет...

Сообщение отредактировал AntonTatu - 9.3.2009, 2:27