Chyba jednak to w większości jest alokacja - zmieniłem kod tak żeby używał domyślnych klas C++ (std::queue i std::stack) i czas wykonania spadł do 1.06. Na razie :P
Jakby nie patrzeć to używanie standardowych klas jest bardziej naturalne niż wymyślanie koła od nowa więc myślę że moje rozwiązanie jest bliższe naturalnemu w C++.
Swoją drogą fajne zagadnienie :]
Wrzucam zmieniony kod, mam nadzieję że się nie obrazisz:
Kopiuj
#include "../include/RPN.h"
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
RPN::RPN()
: stack(), queue(), val(0)
{
}
RPN::~RPN()
{
}
void RPN::InToPost(const char* expr)
{
while(*expr)
{
Item it = Item();
if(*expr >= '0' && *expr <= '9')
{
it.ItemType = itArg;
const char* ex = expr;
while((*expr >= '0' && *expr <= '9') || (*expr == '.'))
++expr;
memcpy(it.Arg, ex, expr - ex);
queue.push(it);
}
else
{
it.ItemType = itOp;
it.Op = *expr;
it.priority = Prior(*expr);
while(!stack.empty() && it.priority <= stack.top().priority)
{ queue.push(stack.top()); stack.pop(); }
stack.push(it);
++expr;
}
}
while(!stack.empty())
{ queue.push(stack.top()); stack.pop(); }
}
void RPN::Calc()
{
while(!queue.empty())
{
if(queue.front().ItemType == itVal || queue.front().ItemType == itArg)
{ stack.push(queue.front()); queue.pop(); }
else
{
double op2, op1;
if(stack.top().ItemType == itVal)
op2 = stack.top().Val;
else
op2 = atof(stack.top().Arg);
stack.pop();
if(stack.top().ItemType == itVal)
op1 = stack.top().Val;
else
op1 = atof(stack.top().Arg);
stack.top().ItemType = itVal;
switch(queue.front().Op)
{
case '+':
{
stack.top().Val = op1 + op2;
break;
}
case '-':
{
stack.top().Val = op1 - op2;
break;
}
case '*':
{
stack.top().Val = op1 * op2;
break;
}
case '/':
{
stack.top().Val = op1 / op2;
break;
}
case '^':
{
stack.top().Val = std::pow(op1, op2);
break;
}
}
queue.pop();
}
}
val = stack.top().Val;
}
void RPN::Clear()
{
val = 0;
while(!stack.empty()) stack.pop();
while(!queue.empty()) queue.pop();
}
char RPN::Prior(const char op) const
{
if(op == '+' || op == '-')
return 1;
else if (op == '*' || op == '/')
return 2;
else
return 3;
}
U mnie czas C++ wynosi 1.06123 s. a Delphi 0.98503 s. więc różnica niebezpiecznie dla Ciebie spada :P
luźna uwaga 1: implementacja stosu i kolejki w C++ to WTF -> pop() zwraca void przez co trzeba kombinować ze stack.top(); stack.pop(). Nie ma też czegoś takiego jak clear przez co trzeba kombinować z while(!s.empty())s.pop();
luźna uwaga 2: @Cplus -> jest znacznie większa różnica - w C++
Kopiuj
if(*expr >= '0' && *expr <= '9')
w Delphi
Kopiuj
TArgSet = ['0'..'9', '.']; if Expr[I] in TArgSet then
luźna uwaga 3: Kod Delphi był przyjemniejszy do statycznej analizy pod disassemblerem (załadowałem na krótko obydwa żeby sprawdzić wyliczaną wartość), ale może wynikało to z tego że była to wersja debug.
luźna uwaga 4: zauważ że jeszcze nic nie optymalizowałem tylko zmieniłem implementację na bardziej prawdopodobną w normalnym życiu.
