Optymalizacja kodu - liczenie wyrażeń ONP

Witam,
mam problem z optymalizacją kodu. Mam funkcje, która przelicza wyrazenie na wejsciu np. w postaci ( ( ( ( ( 2 * 3 ) + 2 * 8 ) / 2 ) + 1 * ( 2 + 3 ) ) + 8 * 4 ). I problem w tym że takich danych wejsciowych jest np ich kilka tysiecy, przez co ta funkcja długo pracuje. Ma ktos pomysł jak zoptymalizować podany przeze mnie kod ? Oto kod tej funkcji:

void przeliczNaONP(const char* wejscie, char* wyjscie)
{
	// W tej funkcji bufor bedzie nam sluzyl glownie do zamiany zmiennej typu char na jednoelementowy
	// lancuch znakow (deklarujemy dwuelementowa tablice, poniewaz musi zostac miejsce na znak konca
	// lancucha, '\0').
	char bufor[2] = {'\0'};
	int i = 0;
	Stos s;
	wyjscie[0] = '\0';

	
	while (wejscie[i] != '\0') // (Warunek konca).
	{
		if (jestOperatorem(wejscie[i]))
		{
			// Jesli jest to operator unarny, oznaczymy go jako '#'.
			if (wejscie[i] == '-')
			{
				if (wejscie[i+1] >= '0' && wejscie[i+1] <= '9')
				{
					// Traktujemy go jako liczbe.
					i++;
					char bufor[SMALL_BUFFER];
					int j = 0;

					while ((wejscie[i] >= '0' && wejscie[i] <= '9') || wejscie[i] == '.')
					{
						bufor[j] = wejscie[i];
						j++;
						i++;
					}

					bufor[j] = '#';
					bufor[j+1] = ' ';
					bufor[j+2] = '\0';
					strcat(wyjscie, bufor);
					continue;
				}
			}

			if (!s.jestPusty())
			{
				while (jestOperatorem(s.szczyt->wartosc[0]))
				{
					char x = wejscie[i];
					char y = s.szczyt->wartosc[0];

					// Porownujemy oba operatory.
					if (x == '+' || x == '-')
					{
						strcat(wyjscie, s.pobierz().wartosc);
						strcat(wyjscie, " ");
					}
					else // x == '*' albo x == '/'
					{
						if (y != '+' && y != '-')
						{
							strcat(wyjscie, s.pobierz().wartosc);
							strcat(wyjscie, " ");
						}
						else
						{
							break;
						}
					}
				}
			}

			bufor[0] = wejscie[i];
			Element* e = new Element(bufor, OPERATOR);
			s.dodaj(e);
		}
		else if (wejscie[i] == '(')
		{
			Element* e = new Element("(", NAWIAS);
			s.dodaj(e);
		}
		else if (wejscie[i] == ')')
		{
			while (strcmp(s.szczyt->wartosc, "(") != 0)
			{
				strcat(wyjscie, s.pobierz().wartosc);
				strcat(wyjscie, " ");
			}

			// Zdejmujemy '(' ze stosu.
			s.pobierz();
		}
		else if ((wejscie[i] >= '0' && wejscie[i] <= '9') || wejscie[i] == '.')
		{
			bufor[0] = wejscie[i];
			strcat(wyjscie, bufor);
			if (wejscie[i+1] == ' ')
			{
				strcat(wyjscie, " ");
			}
		}
		else if (wejscie[i] != ' ')
		{
			// Zmienna. Wyszukujemy jej pelna nazwe i znajdujemy wartosc.
			char bufor2[SMALL_BUFFER];
			int b2i = 0;

			while (wejscie[i] != ' ')
			{
				bufor2[b2i] = wejscie[i];
				i++;
				b2i++;
			}

			bufor2[b2i] = '\0';

			for (int j = 0; j < tablicaZmiennych.ilosc; j++)
			{
				if (strcmp(bufor2, tablicaZmiennych.tablica[j].nazwa) == 0)
				{
					if (tablicaZmiennych.tablica[j].wartosc < 0.0)
					{
						sprintf(bufor2, ILOSC_MIEJSC_MINUS, -tablicaZmiennych.tablica[j].wartosc);
					}
					else
					{
						sprintf(bufor2, ILOSC_MIEJSC, tablicaZmiennych.tablica[j].wartosc);
					}

					strcat(wyjscie, bufor2);
					strcat(wyjscie, " ");

					break;
				}
			}
		}

		i++;
	}
} 

Struktura Stosu:

struct Stos
{
	Element* szczyt;

	Stos()
	{
		szczyt = NULL;
	}

	~Stos()
	{
		while (szczyt != NULL)
		{
			delete [] szczyt->wartosc;
			szczyt = szczyt->next;
		}
	}

	void dodaj(Element* e)
	{
		e->next = szczyt;
		szczyt = e;
	}

	Element pobierz()
	{
		if (szczyt == NULL)
		{
			//cerr << "[!] Stos pusty.\n";
			return Element();
		}

		Element e(szczyt->wartosc, szczyt->typ);
		Element* adres = szczyt;

		szczyt = szczyt->next;
		delete [] adres->wartosc;
		delete adres;
		return e;
	}

	void czysc()
	{
		if (szczyt == NULL)
		{
			return;
		}

		do
		{
			Element* tmp = szczyt->next;
			delete [] szczyt->wartosc;
			delete szczyt;
			szczyt = tmp;
		} while (szczyt != NULL);
	}

	void wypisz()
	{
		if (szczyt == NULL)
		{
			//cerr << "[!] Stos pusty.\n";
			return;
		}

		Element* tmp = szczyt;

		do
		{
			tmp = tmp->next;
		} while (tmp != NULL);
	}

	bool jestPusty()
	{
		if (szczyt == NULL)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}; 

Struktura Element

struct Element
{
	char* wartosc;
	Typ typ;
	Element* next; // Element znajdujacy sie tuz pod obecnym (moze byc to NULL, jesli obecny
	// element jest pierwszym na stosie).

	Element()
	{
		wartosc = new char[strlen("???") + 1];
		strcpy(wartosc, "???");
		typ = BRAK;
		next = NULL;
	}

	Element(const char* w, Typ t)
	{
		wartosc = new char[strlen(w) + 1];
		strcpy(wartosc, w);
		typ = t;
		next = NULL;
	}
}; 

Przetłumacz wejściowe wyrażenie do ONP a potem policz.

Tak, to funkcja robi. Chodzi o optymalizacja kodu przeliczania na ONP.

A z jakiego algorytmu korzystasz? http://pl.wikipedia.org/wiki/Odwrotna_notacja_polska#Algorytm_konwersji_z_notacji_infiksowej_do_ONP ?

// Algorytm napisany przy pomocy stron:
http://edu.i-lo.tarnow.pl/inf/utils/010_2010/0410.php
http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/
http://stackoverflow.com/questions/17254080/infix-to-postfix-algorithm-that-takes-care-of-unary-operators

• zastosowałem minus unarny (czyli stojący przed liczbą, a nie oznaczający działania odejmowania) jest oznaczany jako #.

Musisz korzystać z odwrotnej notacji polskiej?

Tzn. muszę zamieniać wejściowe wyrażenia, tak jak to robie. A jest jakiś inny sposób?

Musisz policzyć to wyrażenie (jego wartość), tak?

Tak, dokładnie

Więc po co bawić się z ONP, skoro znacznie szybsze będzie napisanie prostego parsera.

W moim kompilatorze wygląda to tak: https://github.com/Piterolex/SScript-Compiler/blob/master/expression/expressionparser.pas#L348

Ale domyślam się, że analizowanie czegoś takiego z Twojego punktu widzenia będzie porażką i minie się z celem, dlatego tutaj masz wersję uproszczoną:
http://pastebin.com/WaCnFVu2 (kiedyś pisałem program do rozwiązywania równań i właśnie wtedy to spłodziłem)

Jest to parser o prostej zasadzie działania (chociaż trzeba mieć trochę wyobraźni, aby tę zasadę zrozumieć) - napisany na podstawie jakiegoś angielskiego artykułu, do którego już zgubiłem link (właśnie przeczesuję historię i parę innych stron, ale nie mogę odnaleźć tego bloga ;/).
Przyśpieszył mój kompilator kilkadziesiąt do kilkuset razy (chociaż nie sprawdzałem, jak działa w naprawdę sporych wyrażeniach), więc może się sprawdzi też i u Ciebie.

W razie czego pytaj :P

Edit: oczywiście w wyniku otrzymujesz drzewko wyrażenia, które potem musisz już po prostu policzyć.

Dzieki za odpowiedz Patryk.Mam te IDE delphi jednak niewiem jak to uruchomic, potrzebne sa jakies dodatkowe biblioteki? Nie ma Pan pewnie tego kodu w C++? Bardzo by sie przydal, nigdy nie mialem stycznosci z tym jezykiem.

To jest tylko fragment kodu - cały ten "rozwiązywacz równań" ma 42.5 KB (i nie jest dokończony ;p).
Miał on Ci tylko pokazać ogólną ideę/zasadę działania takiego parsera.
W pseudo-C++ to będzie coś w stylu:

class Parser
{
private:
 Scanner scanner; // skaner tokenów

 /* ... */

 Expression* parse_order_2() // operatory '+' i '-'
 {
  Expression* result = parse_order_3();
  Token next;

  While ((next = scanner.next_token()) == tkPlus) || (next == tkMinus))
  {
   if (next == tkPlus)
    result = new Expression(ekAdd, result, parse_order_3()); else
    result = new Expression(ekSub, result, parse_order_3());
  }

  return result;
 }

 Expression* parse_order_1() // operator '='
 {
  Expression* result = parse_order_2();

  While (scanner.next_token() == tkEqual)
  {
   result = new Expression(ekAssign, result, parse_order_2());
  }

  return result;
 }

public:
 Expression* parse()
 {
  return parse_order_1();
 }
}

Ten kod zakłada, że wejście jest już przeparsowane (scanner).

Ok, dzięki Patryk za pomoc.

Pisanie parsera samodzielnie jest jakąś opcją, ale prostsze (i wydajniejsze, za to dające mniej możliwosci) jest jednak napisanie poprawnego shunting-yarda (czy innej konwersji na ONP).

Jako że dawno go nie implementowałem, napisałem (i przetestowałem) teraz swoją implementację w nadziei że się przyda.

Kod korzysta z: szablonów, wskaźników na funkcje, biblioteki standardowej C, biblioteki standardowej C++. Jeśli któreś z nich nie podoba Ci się (w szczególności możesz nie lubić szablonów jeśli wolisz prosty kod na razie), można się ich zawsze pozbyć lekko zmieniająć kod.

template <typename Rpn>
void stack_execute(Rpn &rpn, precedence_fx prec, stack<char> &stack, char op) {
    while (op && !stack.empty() && prec(stack.top()) >= prec(op)) {
        switch (stack.top()) {
            case '+': rpn.add(); break;
            case '-': rpn.sub(); break;
            case '*': rpn.mul(); break;
            case '/': rpn.div(); break;
            case '(': op = 0; break;
        } stack.pop();
    }
    if (op) { stack.push(op); }
}

template <typename Rpn>
void shunting_yard(const char *expr, Rpn &rpn, precedence_fx prec) {
    stack<char> stack;
    while (*expr) {
        if (isdigit(*expr)) {
            int num = strtol((char*)expr, (char**)&expr, 10);
            rpn.val(num);
        } else if (strchr("+-*/()", *expr)) {
            stack_execute(rpn, prec, stack, *expr);
            expr++;
        } else { expr++; }
    } stack_execute(rpn, prec, stack, ')');
}

D (doszedłem do wniosku że to co robimy z danymi w ONP powinno być elastyczne a nie ustalone na sztywno - o tym zaraz). Byłby ładniejszy, ale konieczność czyszczenia stosu RPN (RPN == skrót angielski od odwróconej notacji polskiej) wymusiła stworzenie funkcji pomocniczej albo brzydkie hacki (wybrałem to pierwsze).

No więc idzie to tak:

- tak długo jak nie doszliśmy do końca wyrażenia (while (*expr))
   - jeśli następny token to liczba, wrzuć go do kolejki wyjściowej RPN
   - jeśli następny token to liczba, przetwórz go za pomocą stack_execute

stack_execute zdejmuje operatory ze stosu operatorów tak długo jak ten na szczycie ma większy priorytet niż obecny (+ specjalny warunek na nawiasy).
A po informacje dlaczego, wynika z tego jak działa sam algorytm (http://en.wikipedia.org/wiki/Shunting-yard_algorithm). Na wiki jest rozważane trochę więcej przypadków, tak naprawdę wszystko podpada (za wyjątkiem ')' wymagającego drobnego specjalnego traktowania, ale to tyle) albo pod 'liczbę' albo pod 'operator' jak u mnie.

Dalej, konieczna jest funkcja przypisujaca każdemu operatorowi odpowiedni priorytet:

typedef int (*precedence_fx)(char op);

int default_precedence(char op) {
    const char *prec[] = { ")", "(", "+-", "*/" };
    for (int i = 0; i < sizeof(prec) / sizeof(*prec); i++) {
        if (strchr(prec[i], op)) { return i; }
    }
    puts("unknown operator :("); return INT_MAX;
}

(można by to oczywiście hardcodować, ale byłoby to trudniejsze w modyfikacji i łamało zasadę separation of concerns. Tym niemniej jeśli nie lubisz wskaźników na funkcję, możesz je łatwo usunąć).

I to w sumie prawie tyle, jak pisałem wcześniej poza implementacją samego RPN.

Na klasie Rpn wywoływane są operacje mul(), div(), add(), sub() i val() (pierwsze cztery, rozkazy wykonania operacji, ostatnie, wrzucenie liczby na stos). Co ta klasa z nimi zrobi, zależy wyłącznie od niej.

Przykładowa, najprostsza implementacja (wykorzystana przy debugowaniu):

class rpn_debug {
    public:
    void mul() { puts("mul"); }
    void div() { puts("div"); }
    void add() { puts("add"); }
    void sub() { puts("sub"); }
    void val(int num) { printf("val %d\n", num); }
};

I użycie:

int main() {
    rpn_debug rpn;
    shunting_yard("2 + 2 * 2", rpn, default_precedence);
}

$ ./a.exe
val 2
val 2
val 2
mul
add

int main() {
    rpn_debug rpn;
    shunting_yard("(2 + 2) * 2", rpn, default_precedence);
}

$ ./a.exe
val 2
val 2
add
val 2
mul

Czyli wygląda na to że wszystko OK.

Łatwo w razie potrzeby np. zmodyfikować rpn_debug żeby zamiast wypisywać informacje do debugowania na konsolę, tworzyła w pamięci string z wyrażeniem w RPN.

Ale oczywiście najbardziej interesujące jest obliczanie wartości wyrażenia. Do tego potrzebujemy takiej implementacji RPN:

class rpn_evaluator {
    stack<int> state;
    template <typename Functor>
    void exec(Functor op) {
        int x = state.top(); state.pop();
        int y = state.top(); state.pop();
        state.push(op(y, x));
    }

    public:
    void mul() { exec(multiplies<int>()); }
    void div() { exec(divides<int>()); }
    void add() { exec(plus<int>()); }
    void sub() { exec(minus<int>()); }
    void val(int num) { state.push(num); }
    int result() { return state.top(); }
};

Być może trochę przesadziłem z szablonami jak na kod który miał być prosty/wydajny...
Zamysł jest bardzo prosty - val() wrzuca argument na stos, a każda z mul, div, add, sub pobiera dwie liczby ze stosu, wykonuje swoją operacje i wrzuca wynik na stos z powrotem.

Zobaczmy czy działa:

int main() {
    rpn_evaluator rpn;
    shunting_yard("2 + 2 * 2", rpn, default_precedence);
    printf("%d\n", rpn.result());
}

$ ./a.exe
6

Działa.

To teraz wydajność. Dla testów wygenerowałem 3.8MB plik z wyrażeniem matematycznym, zawierający 1000001 liczb połączonych 1000000 operacjami mnożenia, dzielenia, dodawania i odejmowania.

import random

result = 'const char *out ="'
for i in range(1000000):
    result += str(random.randint(1, 1000))
    result += random.choice("+-*/")
result += str(random.randint(1, 1000)) + '";'

open('out.txt', 'w').write(result)

(OT: tak, to kiepski sposób generowania długich napisów w pythonie. Ale działał i szybko się pisze)

Przetestowałem następnie za pomocą:

#include "out.txt"

int main() {
    rpn_evaluator rpn;
    shunting_yard(out, rpn, default_precedence);
    printf("%d\n", rpn.result());
}

Wynik:

$ time ./a.exe
774727084

real    0m0.220s
user    0m0.187s
sys     0m0.031s

Skoro 1000000 operacji wykonało się w 0.187 sekundy, to "kilka tysiecy" wykona się prawdopodobnie w mniej niż 0.001 sekundy (same obliczenia, rozruchu programu nie liczę).

Minusa unarnego nie zaimplementowałem, ale nie powinien być problemem.

To chyba tyle, jeśli zdecydujesz się jednak na użycie RPN to może Ci się przyda (http://4programmers.net/Pastebin/3091 - cały kod).