Mathem. Parser -- bitte testen

[dizzy]

Zitat von neolithos:

Grund: Wenn du die Formel zu einer schnell durchrechenbaren Sprache umcompilierst und opimierst, vermute ich, dass das Teil schneller wird.

Die Sprache meines Parsers heisst "Baum"

Zitat von neolithos:

Bei Meinem Formel-Parser (der langsamer ist, durch Typenkonvertierungen und OOP) gehe ich wie folgt vor.

Ist meiner nicht OOP? Und hast du dir mal die ganzen Typecasts angesehen die ich da zwischen drin sitzen hab?

Zitat von neolithos:

(1 + sin(A))^3 * (1+1)

Erster Schritt:

zerlegen in Token (Teile):

"1" "+" "sin" "(" "A" ")" "^" "3" "*" "(" "1" "+" "1" ")"
Dies erledigt eine while Schleife gekoppelt mit einer Matrix.

Baue aus den Tokens einen Parsebaum:

Dazu wird ein vor definierter Syntax-Graph durchlaufen.
-> Wieder nur eine while-Schleife

Das mache ich z.B. in nur einer Rekursion (procedure TTF(...)). Die dort enthaltene irre große "if..then..else"-Verzweigung legt in ihrer Struktur und Reihenfolge den "virtuellen" Sytaxgraphen fest, und das Ende dieser einen Rekursion die sich direkt den zu parsenden String vornimmt ist der (fast) fertige Baum.

Zitat von neolithos:

Optimiere den Code:
in dem Fall wird 1+1 zusammengefasst.

Deswegen oben das "fast" in Klammern: Das mache ich in 2 rekursiven Schritten. Erst wird von den Blättern anfangend gekennzeichnet welche Knoten überhaupt "zusammenfassungswürdig" sind, also nicht Variablen oder von solchen abhängig sind. Im 2. Durchlauf findet die eigentliche Optimierung statt, die alles was möglich ist zusammen fasst.
(Diese Funktion ist in dem hier eingestellten glaub ich noch nicht vorhanden. Bei mir aber sehr wohl )

Zitat von neolithos:

Erzeuge Code:

Code:

push 1
push a
sin
and
push 3
power
push 2
mul

Und die Ausführung dieses Code's könnte man extrem Optimieren.
Array für Stack.
Sprung-Tabelle für Proceduren.

Und genau das spare ich mir. Dafür müsste man den Baum ein mal rekursiv durchlaufen um den Stack zu bilden, und dann muss man noch mal ran und den Stack lösen. Ich löse direkt den Baum, so dass diese rekursive Funktion als Rückgabewert das fertige Ergebnis liefert.

Ich hatte mal testweise 2 verschiedene Stackprinzipe eingebaut: Ein mal mit nur einem Stack, und mal mit getrennten Operanden- Werte- und Ergebnisstack.
Beide Versuche führten zu einer erheblichen Verlangsamung. (Man muss hierbei beachten, dass die Stärke meines Parsers ist, ein und die selbe, ein einziges Mal geparste Formel, immer und immer wieder zu lösen, mit veränderten Variablen. Also zum Plotten von Funktionen gut geeignet, oder halt für Fraktalrechnungen )
Bei der Variante mit einem Stack war das Problem, dass ich für jedes Mal Lösen den gesamten Stack "echt" kopieren musste. Und das hat einfach viel zu lange gedauert.
Bei der Variante mit 3 Stacks fiel der Kopieraufwand weg, aber der Overhead durch die Stackverwaltung in Form von Unterscheidung von Unären und Binären Operatoren, und der Indexverwaltung an sich, war wohl größer als der Overhead einer Rekursion. Zumindest hatten das meine Messungen ergeben.
Von daher bin ich beim Baum geblieben.

Was auch noch mit reinspielt ist, dass ich gerne die 3 Zahlentypen strukturell möglichst gleich abhandeln wollte. Und die Rechnerei mit komplexen Zahlen/Quaternionen gestaltet sich ja noch etwas anders als mit double, da man ja nicht die normalen Operatoren verwenden kann.
Weiteres Schmankerl ist in dieser Hinsicht auch das Variablenhandling. Es gibt 8 Variablen, denen es völlig egal ist ob sie nun ein double-Wert sind, ne komplexe Zahl, oder was auch immer. Daher bleibt die "usability" für den "Endbenutzer" (also Programmierer...) gut. Um mit dem Teil etwas mit double-Werten zu rechnen reicht folgendes:

Delphi-Quellcode:

var p: TCQParser;
    ergebnis: double;
.
.
p := TCQParser.Create;
p.Parse('(1 + sin(A))^3 * (1+1)');
p.SetVariable(A, pi);
p.Solve(ergebnis);

Naja, und ich bin (noch *g*) der Meinung dass ich meine beiden obersten Ziele (Speeeed und einfache Bedienbarkeit) einigermaßen gut erreicht habe.
Wenn du es aber hinbekommen solltest das Dingen noch schneller zu machen, dann bin ich der erste dem die Kinnlade runterfällt *provozier* .

Ich werde die Tage (in 1-2 Wochen) die neue Version posten. Ich will ein Parser-Battle


guts Nächtle,
dizzy