Funktionsinterpreter
Interpreter Nr. 2
Für unseren zweiten Funktionsinterpreter machen wir uns zunutze, dass wir das Berechnen von ein- und derselben Funktionsvorschrift beschleunigen können, indem wir auf die Stringvergleiche verzichten. Wir werden dafür sorgen, dass wir die relativ langsamen Stringvergleiche nur noch einmal durchführen und diese ab da durch Konstanten ersetzen. Wir führen dazu einen (privaten) Aufzählunstypen ein, der lediglich in der Klasse des Funktionsinterpreters genutzt werden kann.
... TPartTerm = (ptX, ptNumber, ptAdd, ptSub, ptMul, ptDivide, ptSqrt); ...
Die ersten beiden Konstanten des Aufzählungstyps dienen nur zur Unterscheidung, ob es sich um die Variablen X oder um eine Zahl handelt. Danach kommen die binären Operatoren und erst zuletzt die unären Operatoren. Dabei ist wichtig, dass sich die beiden Operatortypen in zwei voneinander getrennt liegenden Blöcken befinden, da wir ansonsten später bei der Unterscheidung zwischen den beiden Typen Probleme bekommen werden.
Unsere Teilterme (bestehend aus der Variablen X, Zahlen und Operatoren) landet in einem dafür vorgesehenen Array. Damit wir später einfacher an unsere eventuelle Zahl herankommen, handelt es sich um ein Array von Records:
...
private
type
TTerm =
record
id: TPartTerm;
value: Extended;
end;
var
terms: Array of TTerm;
...
Die ID identifiziert damit unseren Teilterm und sagt aus, ob es sich um Variable, um eine Zahl oder um einen Operator handelt. Wenn letzteres der Fall ist, sagt die ID natürlich auch aus, um welchen der Operatoren es sich handelt. Value gibt uns die Möglichkeit die Zahl auszulesen, sofern es sich um eine handelt. Die Klasse für den Funktionsinterpreter bekommt nun insgesamt folgenden Aufbau:
TFunctioninterpreter = class(TObject)
private
type
TPartTerm = (ptX, ptNumber, ptAdd, ptSub, ptMul, ptDivide, ptSqrt);
TTerm =
record
id: TPartTerm;
value: Extended;
end;
var
terms: Array of TTerm;
public
constructor Create(const str: String);
function interpret(xVal: Extended): Extended;
end;
Die Funktion SplitString(…) kennen wir bereits aus dem vorherigen Abschnitt. Auch den Destruktor werden wir hier nicht weiter betrachten, auch wenn in diesem natürlich bestimmte Resourcen wieder freigegeben werden müssten, die wir während unserer Arbeit reservieren.
Der Konstruktor unseres Funktionsinterpreters bekommt nun die anfängliche Funktionsvorschrift mit und füllt damit unser Array mit den IDs.
constructor TFunctioninterpreter.Create(const str: String);
var
splittedFunction: TStringList;
len, i: Integer;
isNumber: Boolean;
val: Extended;
begin
// Hol die einzelnen Teilstrings heraus
splittedFunction := TStringList.Create();
SplitString(splittedFunction, str, ‚ ‚);
// Bereite das Array für die Teilterme vor
len := splittedFunction.Count;
SetLength(terms, len);
// Zerlege die Funktion nun in die einzelnen Teilterme
for i := 0 to len – 1 do
begin
// ist es die Unbekannte?
if splittedFunction[i] = ‚x‘ then
begin
terms[i].id := ptX;
end
else
begin
// Ist es einfach nur eine Zahl?
isNumber := TryStrToFloat(splittedFunction[I], val);
if (isNumber) then
begin
terms[i].id := ptNumber;
terms[i].value := val;
end
// Es ist eine Operation. Aber welche?
else if splittedFunction[i] = ‚+‘ then
begin
terms[i].id := ptAdd;
end
else if splittedFunction[i] = ‚*‘ then
begin
terms[i].id := ptMul;
end
else if splittedFunction[i] = ’sqrt‘ then
begin
terms[i].id := ptSqrt;
end;
end;
end;
end;
Die Stringvergleiche sind ähnlich wie schon beim ersten Funktionsinterpreter. Nur dass sämtliche Stringvergleiche lediglich dieses eine Mal beim initialisieren stattfinden.
Ist das erst einmal geschehen, wird das eigentliche Interpretieren der Funktion folgendermaßen implementiert:
function TFunctioninterpreter.interpret(xVal: Extended): Extended;
var
Stack: TStack;
len, i: Integer;
a,b: TNumber;
begin
// Stack bereit machen
Stack := TStack.Create();
// Arbeite alles ab
len := Length(terms);
for i := 0 to len – 1 do
begin
// Wir haben nur drei Möglichkeiten:
// 1. Das Symbol ist ein x. Dann werfen wir x auf den Stack
// 2. Das Symbol ist eine Zahl. Dann werfen wir die entsprechende Zahl auf
// den Stack.
// 3. Es handelt sich um eine Operation. Dann führen wir selbige einfach aus
if (terms[i].id = ptX) then
begin
stack.Push(TNumber.Create(xVal));
end
else if (terms[i].id = ptNumber) then
begin
stack.Push(TNumber.Create(terms[i].value));
end
// nun kann es nur noch ein unärer oder ein binärer operator sein
else if (terms[i].id in [ptAdd..ptDivide]) then
begin
// wir brauchen zwei operanden
a := stack.Pop();
b := stack.Pop();
// berechnen. Dabei die Operanden umdrehen
case(terms[i].id) of
ptAdd: a.num := b.num + a.num;
ptSub: a.num := b.num – a.num;
ptMul: a.num := b.num * a.num;
ptDivide: a.num := b.num / a.num;
end;
// und zurück damit
b.Free();
stack.Push(a);
end
else
begin
// wir brauchen nur einen operanden
a := stack.Pop();
// berechnen…
case(terms[i].id) of
ptSqrt: a.num := System.sqrt(a.num);
end;
// und zurück damit
stack.Push(a);
end;
end;
// Was noch auf dem Stack liegt dürfte unser Ergebnis sein
a := stack.pop();
Result := a.num;
a.free();
end;
Unsere ständigen Stringvergleiche wurden nun also (intern) durch schnellere Zahlenvergleiche ersetzt. Überdies kann nun auch unser If-Block durch den Case-Block ersetzt werden, der, je nach Compiler, auch schneller abgearbeitet werden kann als ein If-Block.
Die Zeile (terms[i].id in [ptAdd..ptDivide]) macht nun auch deutlich, warum wir die binären und unären Operatoren in unserem Aufzählungstyp strikt trennen müssen.
Verwendet wird der Funktionsinterpreter dann übrigens folgendermaßen:
var
functionint: TFunctioninterpreter;
x: Integer;
begin
functionint := TFunctioninterpreter.Create('x x * 2 + sqrt');
for x := -100000 to 100000 do
begin
do_anything(functionint.interpret(x));
end;
end.
Das Ergebnis ist im Endeffekt zum Vergleich mit dem ersten Funktionsinterpreter eine etwa sechs- bis siebenmal schnellere Laufzeit. Natürlich kann der Funktionsinterpreter nun nach Belieben auch noch erweitert werden. Zum Beispiel mit weiteren Operatoren oder mit Überprüfungen, ob die Funktionsvorschrift auch wirklich richtig eingegeben worden ist. Natürlich kann statt mit Konstanten auch mit Interfaces und Klassen gearbeitet werden – je nach dem, was man bevorzugt. Dieses Tutorial sollte auch nur zeigen, wie man in Delphi einen relativ einfachen Funktionsinterpreter schreiben kann.