Dieses Kapitel ist als die Fortsetzung vierer anderer Kapitel
zu sehen - hier laufen viele Fäden zusammen. Vordergründig handelt
es sich zunächst einmal um die Fortsetzung des Abschnitts über
die Funktionen zu Datum und Zeit, es soll hier die Funktion
(elapsed ...) vorgestellt werden, mit der man das
Laufzeitverhalten anderer Funktionen abschätzen kann - eine
Stoppuhr für Funktionen sozusagen.
Da diese Funktion aber, um deren Verhalten zu messen, irgendwelche
anderen Funktionen oder beliebige Ausdrücke evaluieren soll,
muss gewährleistet sein, dass sie dies auch kann, ohne dass es
zu irgendwelchen Kollisionen kommt. Solche Kollisionen können
dadurch entstehen, dass es in Lisp keine wirklich lokalen
Variablen gibt, und dass globale Variablen nicht explizit als
solche deklariert werden müssen. Daher geht es hier auch um die
Fortsetzung des Kapitels über
Namensräume.
Die innerhalb von
(elapsed ...) ausgeführten Ausdrücke
können ganze Programme sein, es können Funktionen sein, aber auch
lambda-expressions oder sogar 'unverpackte' Ausdrücke wie
(setq t1 nil) oder schlicht
1. Hier entsteht aber
ein Risiko, auf das wir gleich eingehen werden, und das wiederum
nur mit Hilfe einer
lambda-expression umgangen werden kann.
Daher ist dieses Kapitel auch die Fortsetzung des Themas
lambda-expressions.
Die Funktion
(elapsed ...) benötigt Argumente und lokale
Variablen, wie immer sie auch implementiert wird. Zum einen
muss sie den Ausdruck abspeichern, den sie testen soll, die
Anzahl der Test-Durchläufe (diese kann bei kurzen Ausdrücken
auch eine Million betragen, damit Zeiten vergleichbar werden)
muss bekannt sein, und die Startzeit muss sie speichern, um sie
später mit der Endzeit zu vergleichen. Nehmen wir einmal an, der
Anfang der Funktion sähe so aus:
(defun elapsed(test-expr n-times / t1)...
Ein Benutzer ruft die Funktion auf und verwendet dabei folgenden
lambda-Ausdruck (der Benutzer möchte gerne wissen, ob drei
einzelne Aufrufe von
setq wirklich so viel langsamer sind
als die folgende Variante mit einem Dreifach-
setq:
(elapsed
'(lambda( / x y z)(setq x 10 y 11 z 12))
1000
)
Die Funktion wird ihm also die gemessene Zeit ausgeben. Was aber
passiert, wenn er als Variablennamen das hier verwendet?
(elapsed
'(lambda( / t1 t2 t3)(setq t1 10 t2 11 t3 12))
1000
)
Natürlich, es passiert nichts - die Variablen sind ja sauber
als lokal zum
lambda deklariert! Sichtbar sind sie also nur
innerhalb der
lambda-expression, und die Variable
t1
verdeckt die gleichnamige Variable der Funktion
elapsed.
Was aber wird passieren, wenn Schlamperei ins Spiel kommt? Die
übergebene
lambda-expression wurde unsauber programmiert, die
Variable
t1 wurde nicht als lokale Variable in die
Argumentenliste eingetragen! Die Variable
t1 der
elapsed-Funktion wird überschrieben, und wenn im Anschluss
an die Test-Durchläufe die Zeitdifferenz berechnet werden soll,
kommt nur noch Müll dabei heraus.
Es muss aber nicht unbedingt Schlamperei im Spiel sein - schliesslich
könnte ja eine Funktion getestet werden, die bewusst eine globale
Variable namens
t1 erzeugt. Es können ja an
elapsed
auch beliebige Ausdrücke ohne
lambda übergeben werden.
Prinzipiell trägt jede von uns geschriebene Funktion, die einen
von Aussen kommenden Ausdruck evaluiert, dieses Risiko. Die Funktion
(elapsed ...) steht hier allerdings an exponierter Stelle,
sie ist ja ausschliesslich dazu da, irgendwelche Ausdrücke zu
evaluieren, wobei nicht einmal ein
lambda-Ausdruck gefordert wird.
Was also kann man tun, um solche Pannen zu verhindern?
Die Lösung heisst - wie sollte es anders sein -
(lambda ...)!
Wir verpacken die zu evaluierenden Ausdrücke einfach noch einmal in
eine
lambda-expression, und natürlich können wir - wie immer -
solche Ausdrücke beliebig tief verschachteln! Der Trick dabei ist
aber, dass wir dieser 'Ummantelung' ein paar lokale Argumente
mitgeben: Nämlich die unserer
elapsed-Funktion. Dadurch
erreichen wir, dass in diesem Mantel-
lambda namensgleiche
Variablen erzeugt werden, die evtl. auftretende 'Querschläger'
auffangen.
Dieses Einwickeln eines Ausdrucks in ein
lambda kennen wir
bereits von
(let ...), und nun sollte klar werden, warum dies
hier auch eine Fortsetzung des
let-Kapitels ist. Wir werden
allerdings nicht
let selbst verwenden, da es bei
let
vor allem darum geht, den lokalen Variablen Werte zuzuweisen. Das
ist hier natürlich nicht nötig - die Existenz der Variablen allein
reicht für unsere Zwecke.
Zum 'Einwickeln' eines Ausdrucks ohne Argumente in ein lambda
würde das hier schon genügen:
; macht aus einem beliebigen Ausdruck eine
; argumentlose lambda-expression
(defun envelope(expr / )
(eval
(append
(list'lambda nil)
(list expr)
)
)
)
Um die Namen der zu schützenden Variablen mitzugeben, müssen wir
die Funktion ein bisschen 'umstricken':
(defun safe-envelope(expr fences / )
(eval
(append
(list'lambda(cons '/ fences))
(list expr)
)
)
)
Wir führen einen kleinen Test durch, um die Sache zu verifizieren:
((safe-envelope '(setq a 13) '(a))) => 13
!a => nil
Das war's, was wir wollten: Obwohl a nirgendwo als lokale
Variable deklariert wurde, ist trotzdem keine globale Variable
daraus entstanden! Und nun können wir mit Hilfe von
(safe-envelope ...) unsere Funktion (elapsed ...)
implementieren, und zwar ohne die Gefahr, von Aussen 'abgeschossen'
zu werden:
(defun elapsed(test-expr n-times / t1)
(setq t1(time-list))
(setq test-expr
(safe-envelope test-expr
'(test-expr n-times t1)
)
)
(repeat n-times
((eval test-expr))
)
(time-diff t1(time-list))
)
Und nun können wir herausfinden, was schneller ist. Damit
sich das Beispiel nachvollziehen lässt, müssen natürlich auch
die Funktionen (time-list ...) und (time-diff ...)
geladen sein! Auf jeden Fall können die zu evaluierenden Tests
unbedenklich das Symbol t1 ohne lokale Deklaration
enthalten - aber natürlich auch test-expr oder n-times.
(setq test-expr
'(progn
(setq t1 10)
(setq t2 11)
(setq t3 12)
)
)
; oder
(setq test-expr2
'(progn(setq t1 10 t2 11 t3 12))
)
(elapsed test-expr 1000000) => (0 0 11)
(elapsed test-expr2 1000000) => (0 0 11)
Es erweist sich, dass kein relevanter Zeitunterschied festzustellen
ist. Machen wir doch noch ein kleines Experiment: Wir vergleichen
das Zeitverhalten von cons und append, wie es im Kapitel
über Listen-Strukturen besprochen wurde. Da append jedesmal
die gesamte Liste durchlaufen muss, wird es mit zunehmender Länge
der Liste immer langsamer.
(defun cons-test( / n ls)
(setq n 1)
(repeat 1000000 ;!!!
(setq ls
(cons n ls)
)
(setq n(1+ n))
)
(reverse ls)
)
(elapsed '(test1) 1) => (0 0 7)
(defun test( / n)
(setq n 1 ls nil)
(repeat 10000 ;!!!
(setq ls
(append ls(list n))
)
(setq n(1+ n))
)
ls
)
(elapsed '(test2) 1) => (0 1 10)
Das Ergebnis ist mehr als deutlich: Eine Million Elemente bei
der cons-Variante sind in 7 Sekunden erledigt - aber
10000 Elemente mit append aneinander zu hängen, dauert
bereits eine Minute und 10 Sekunden. Einen Versuch mit 50.000
Elementen habe ich nach etwa 10 Minuten ergebnislos abgebrochen.
Eine Million würde da wohl kein Rechner überleben, die Rechenzeiten
steigen ja nicht etwa linear an ...