Mathem. Parser -- bitte testen

[Kastor]

Hi,

- Delphi7 Professional (kompiliert ohne Probleme)
- Ergebnisse sind korrekt
- Amd Athlon 2800+, gibt so um die 2 Ghz Realtakt

Ergebnisse (von oben nach unten):
850,968
1478,88
3733,95
6893,12

Gruß, Kastor

[neolithos]

• Delphi 7 Prof
  Celeron 1 GHz
  1633,33
  3007,94
  6480,49
  12938,5

Kritik: Der Parser ist sehr ausprogrammiert und schlecht erweiterbar.

Schau die mal ein paar Seiten zum Thema Compilerbau, Deterministisch Endlicher Automat, Optimierung, ZwischenCode usw. an.

Denn in dem Copy&Paste-Code möchte ich nie etwas ändern.

[dizzy]

Zitat:

Zitat von neolithos

Kritik: Der Parser ist sehr ausprogrammiert und schlecht erweiterbar.

Eigentlich nicht. Zur Erweiterung genügt es zb. einen neuen Operator einzufügen, und dessen Behandlung in den großen "if..then..else"-Zweig einzusetzen. Zwar muss man etwas darauf achten, wo man diese Behandlung einfügt, aber ich hab ihn ja ständig selbst erweitert - z.B. kennt er mittlerweile Konstanten wie pi oder e.
Ihn voll "customizable" zu machen, das wollte ich nicht, da dass erheblich an der Performance gedrückt hätte, und ich wollte das Teil so schnell wie auch nur irgend möglich machen. Das war im Gegensatz zur Erweiterbarkeit oberstes Ziel, daher auch meine Testreihe hier.
Habe das Ding jetzt sogar in eine DLL verpackt, so dass das mit der Erweiterbarkeit ohnehin flach fällt, man ihn aber in beliebigen Sprachen einsetzen kann (die DLLs einbinden können...).

Ein paar kleine Finetunings sind noch nötig, und dann werd ich den nochmal komplett mit Source+DLL hier einstellen. Und es sollte garnicht nötig sein ihn zu erweitern, da ich eigentlich so ziemlich alle Grundoperationen drin hab, incl. der eigentlich nie gebrauchten trigonometrischen Funktionen für Quaternionen :roll: :)

Speed war deshalb oberstes Gebot, da ich mit dem Teil 3D-Fraktale berechne, und da kommen sehr leicht > 10.000.000 Rechendurchläufe pro Formel rum.

Wenn diverse Funktionen fehlen sollten, die ihr vermissen würdet, so bin ich offen für Vorschläge! Das Dingen sollte nachher als Monolit dastehen, d.h. fertig und rund. Zwar OpenSource, aber nicht mit der Notwendigkeit dran rumzufummeln :). Wobei das wie gesagt garnicht so unmöglich ist :cyclops:.

Danke aber für den Tipp, ich hatte diesen Aspekt noch nicht als einzelnes betrachtet.


grüzli,
dizzy

[neolithos]

Genau so könnte man aber Speed rausholen.


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

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

(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

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

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.

[ripper8472]

@neolithos:

deinen Ansatz mit den bäumen verfolge ich auch gerne, besonders in PHP. Was ich persönlich nicht verstanden habe ist dein erzeugter code mit "pushes", deren verwendung mir nicht klar ist (sieht nicht wie assembler aus).

greets ripper

(sorry für mein gelaber)

[neolithos]

Das ist auch keine Assembler sonder eine eigene Sprache.

Sie basiert auf einem Stack. -> Stackmaschine.

push 1 --> legt 1 auf den Stack
push 4 --> legt 4 auf den Stack
and --> nimmt zwei Werte vom Stack, Addiert sie und legt das Ergebnis auf den Stack.

[ripper8472]

Hi,

ich war noch etwas verwirrt, weil ich bei den Tokens keine Klammern um die 1 und das Sinus gesehen hab. So ein Stacksytem ist echt nicht schlecht!

An solche Bäume lassen sich auch symbolische Umformungen ansetzen: ein Computer Algebra System!!

- ripper

(sorry für meine verwirrten posts)

[dizzy]

Zitat:

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:

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? :gruebel:

Zitat:

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:

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:

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* :mrgreen:.

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


guts Nächtle,
dizzy

[neolithos]

Erstens:

Die Klammern hatte ich vergessen!

Zweitens:

Meinen Parser habe ich mit C# geschrieben und dort verwende ich verdammt viel in/outboxing. Dies scheint zu lasten der Performance gehen.

Drittens:

Jetzt hast du mich doch neugirig gemacht! Ich will mal wissen wie schnell in einem Win32-Programm ist. Wenn ich mal Zeit habe schreib ich das Teil um. :mrgreen:

Viertens:

Meinem Parser werde ich aber nur Integer und Double beibringen.

[dizzy]

Zitat:

Zitat von neolithos

Meinen Parser habe ich mit C# geschrieben und dort verwende ich verdammt viel in/outboxing. Dies scheint zu lasten der Performance gehen.

Okay, da resignier ich... Ich hab weder Plan von C, noch von .NET
Das entbehrt latürnich nahezu jeder Vergleichbarkeit.

Zitat:

Zitat von neolithos

Jetzt hast du mich doch neugirig gemacht! Ich will mal wissen wie schnell in einem Win32-Programm ist. Wenn ich mal Zeit habe schreib ich das Teil um. :mrgreen:

Also meiner ist bei double rund 0.5 bis 0.65 mal so schnell wie eine Formel in Delphi direkt geschrieben. Mangels Vergleichsmöglichkeiten halte ich das einfach mal für ein recht passables Ergebnis :)
Leider bleibt mir natürlich die Optimierung durch .NET verwehrt :?

Zitat:

Zitat von neolithos

Meinem Parser werde ich aber nur Integer und Double beibringen.

Feigling :mrgreen: