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

[BRE]

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

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

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

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

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

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

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

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

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

[SABROG]

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

На самом деле мне приходит на ум только одна область где может применяться технология - архивация/сжатие данных, а dll или exe - SFX распаковщик. Но это с учетом того, что архиватор генерит некую уникальную формулу на основе подсунутых файлов, которые надо сжать.

[BRE]

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

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

Т.е. на каждой итерации как-то генерируется разная формула -> собирать библиотеку на каждой итерации.

На самом деле встает вопрос, почему не вычислять формулу на этапе ее генерации?
Получили x[0,j]*x[2,j]*x[5,j]*x[10,j] - посчитали, получили x[0,j]*x[3,j]*x[4,j] - посчитали, прибавили. Конечно, здесь необходимо уточнить как, кто и какую формулу можно сгенерировать. Может формула состоит из повторяющихся выражений с разными переменными, здесь тоже можно попробовать помудрить.

Короче, тут простор для исследований, все нужно пробавать.

IMHO, путь с realtime-генерацией библиотеками, ээээ, ну не опревданный что-ли.

[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

[BRE]

main.obj : error LNK2019: ссылка на неразрешенный внешний символ "public: void __thiscall MathStack::push(double)"

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

Ты определили функции MathStack?

void MathStack::push( double )
{
    ...
}

double MathStack::pop()
{
    ...
}

или сделай пока так:

class MathStack : public QStack<double>
{
};

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

Ошибки я сам видел, набирал прямо здесь, но функция редактирования у меня была еще не активна.

Покажи, что сейчас получилось...

Сообщение отредактировал BRE - 9.3.2009, 11:00

[AntonTatu]

Покажи, что сейчас получилось...

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

Не компилируется если написано

    static MathStack m_stack;    // стек общий для всех операций

как только static убираю ошибка в этой строчке уходит,
еще ругается вот в этом месте

Operation::m_stack.pop();

.\main.cpp(123) : error C2228: выражение слева от ".pop" должно представлять класс, структуру или объединение


сейчас получилось вот что (переписывал все в однин cpp файл, как зарабортает (будет супер) разнесу в h)

код

#include <QtCore/QCoreApplication>
#include <QStack>



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

void MathStack::push (double var){
    MyStack.push(var);

}

double MathStack::pop(){
    return MyStack.pop();
}

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

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

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

    void    run();

private:
    const double    &m_var;
};

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

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

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

class MulOp : public Operation
{
public:
    void    run();
};
// Снять с арифметического стека два числа, сложить их и результат положить обратно на стек
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 );
}
// Снять с арифметического стека два числа, перемножить их и результат положить обратно на стек
void MulOp::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::addOp( Operation *op )
{
    m_ops.append( op );
}

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

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



int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    // Объявляем двухзначный вектор
    std::vector < std::vector <char> > *znach;
    // Распределяем память под вектор
    znach = new std::vector< std::vector <char> >( 2, std::vector<char>(5) );
    //заполним массив значениями
     for (int i=0; i<2; i++) 
         for (int j=0; j<5; j++) {
            (*znach)[i][j] = i+j; 
         
         }

Formula f;
f.addOp( new VarOp( (*znach)[ 0 ][ 0 ] ) );
f.addOp( new VarOp( (*znach)[ 0 ][ 1 ] ) );
f.addOp( new VarOp( (*znach)[ 1 ][ 1 ] ) );
f.addOp( new MulOp() );
f.addOp( new AddOp() );
f.addOp( new VarOp( (*znach)[ 1 ][ 2 ] ) );
f.addOp( new AddOp() );

//одна итерация
//double res = f.calc(); //не работает


    return a.exec();
}

Сообщение отредактировал Litkevich Yuriy - 9.3.2009, 14:01