Wenn es eine oder zwei Empfehlungen gibt, die ich einer Programmiererin oder einem Programmierer mit auf den Weg geben möchte, dann diese zwei:
- Visualize what you don’t see
- Express your understanding of your code
Beide Tipps drehen sich um ein und denselben Punkt: Stimmt das, was ich da programmiert habe, mit meinen Vorstellungen überein, was der Code wirklich tut? Habe ich ein korrektes Abbild dessen im Kopf, was sich zur Laufzeit meines Programms abspielt? Gerade in einer OO-Sprache ist die Gefahr sehr groß, dass man nicht wirklich überblickt, wie sich Objekte untereinander verknüpfen, ob die Objektstrukturen auch das abbilden, was man wollte. Man muss eine lebhafte Phantasie haben, um zu sehen, welche Auswirkungen der Programmcode in Form von Klassen und Methoden bei seiner Ausführung auf die Ebene der Objekte hat.
Beide Tipps seien an einem Beispiel erläutert.
In den letzten Tagen implementierte ich eine besondere Variante der binären Bäume: AVL-Bäume. AVL-Bäume achten beim Hinzufügen oder Entfernen von Knoten darauf, dass der Binärbaum balanciert bleibt — die englischsprachige Wikipediaseite erklärt AVL trees sehr gut. Als kleine Herausforderung kam dazu, dass der AVL-Baum als persistente Datenstruktur umgesetzt werden sollte. Man braucht persistente Datenstrukturen in der funktionalen Programmierung. Bei einer persistenten Datenstruktur werden Daten niemals verändert (Immutabilität), das Hinzufügen oder Entfernen von Daten erzeugt eine neue Datenstruktur, wobei so viele Anteile der “alten” Struktur wie möglich wiederverwendet werden.
Tipp 1: Visualize what you don’t see
Ich startete mit einer persistenten Implementierung eines Binärbaums — das ist in Python rasch geschehen. Dann folgte der Ausbau zum AVL-Baum, was ein wenig Arbeit und vor allem Verständnis erforderte. Wenn nach dem Einfügen eines Knotenelements der Baum seine Balance verliert, dann müssen Teilbäume rotiert werden, damit der Baum wieder ausgewogen ist.
Nachdem ich fertig war, stellte sich die Frage aller Fragen: Macht mein Code, was er soll? Erste Gehversuche mit dem Code an der Python-Konsole verliefen gut und ohne Probleme. Doch sind die Bäume wirklich ausbalanciert? Ich will nicht nur Sonderfälle testen, sondern auch sehen, dass die Verlinkung der Knoten stimmt. Visualisierung als vertrauensbildende Maßnahme ist nicht zu überbieten!
Zum Glück gibt es ein wunderbares Werkzeug zur Darstellung von Graphen aller Art: Graphviz. Schnell war die
__str__-Methode der Node-Klasse angepasst und ich konnte mir mit Hilfe einer Funktion gviz eine passgerechte Ausgabe für eine Graphviz-Ausgabe erzeugen. Und die brachte das Unglück an den Tag.n1 = Node(3).insert(4).insert(2)
n2 = n1.insert(1)
n3 = n2.insert(0)
print(gviz(n3))
Der sich ergebende Baum war alles andere als balanciert. Ab einem Höhenunterschied von mindestens 2 muss der Baum neu ausgerichtet werden. Blau eingefärbt ist jeweils der Verweis auf den “linken” Teilbaum eines Knotens, in Rot der “rechte” Teilbaum. Die Angabe im Knoten entspricht dem Schlüsselwert, dem
key des Knoten.
Der Fehler im Code war schnell gefunden. Die “Höhe” eines Knoten wurde falsch berechnet, ich hatte die Addition um
+ 1 am Ende von max( ... ) vergessen. So ein Fehler passiert schnell und ist leicht behoben. self.height = max(left.height if left else 0,
right.height if right else 0) + 1
Und siehe da, jetzt stimmt es!
Die Visualisierung der ansonsten verborgenen Verlinkungen von Node-Objekten hilft außerdem dabei, die schrittweise Entstehung der Baumstrukturen zu beobachten, wobei die Immutabilität gewahrt bleibt. Es werden keine Referenzen “verbogen”, sondern gegebenenfalls neue Knoten mit neuen Referenzen erzeugt. Wann immer möglich, wird auf vorhandene Teilstrukturen verwiesen. Ein
print(gviz(n1,n2,n3))
liefert mir die Darstellung von drei Bäumen mit jeweils
n1, n2 bzw. n3 als Wurzelknoten.
Links sieht man den durch
n1 aufgespannten Baum, der mit der Ergänzung um einen Schlüssel 1 einen neuen Wurzelknoten, n2 liefert, der die rechte Teilstruktur beibehält (die roten Verweise auf den Knoten mit dem Schlüsselwert 4), jedoch links einen neuen Teilbaum mit dem zusätzlichen, neuen Knoten mit dem Schlüssel 1 aufbaut. Die Ergänzung um einen Schlüssel mit dem Wert 0 liefert den Knoten n3, der nun im linken Baumteil eine Rotation durchführen muss, um den n3-Baum zu balancieren.
Ohne eine solche Visualisierung hätte ich meinem Code kaum getraut. Vor allem sind große Baustrukturen rasch auf ihre Balanciertheit hin visuell inspiziert. Visualization builds trust in code!
Tipp 2: Express your understanding of your code
Natürlich gehören zu jedem guten Stück Code ein paar Testfälle. Was ich mit diesem zweiten Tipp jedoch meine, greift noch viel unmittelbarer: Überprüfe — beispielsweise mit Unit-Tests — ob der Code auch das tut, von dem Du glaubst, dass er es tut. Im Beispiel: Hat ein instanziierter
Node tatsächlich die ihm zugewiesenen Eigenschaftswerte, insbesondere die berechneten Eigenschaftswerte. Wie ich feststellen musste, was schon die erste und einfachste meiner Annahmen nicht korrekt. Ein Knoten ohne jegliche Nachfolger sollte die Höhe 0 haben — hatte er aber nicht. def test_oneNode(self):
n = Node(3)
self.assertTrue(n.key == 3)
self.assertTrue(n.height == 0)
self.assertTrue(n.left == None)
self.assertTrue(n.right == None)
Der obige Code zur Berechnung von
self.height hatte tatsächlich noch einen Fehler! Er konnte niemals 0 werden, was von mir gar nicht beabsichtigt war. Dieser Widerspruch zwischen Annahme und tatsächlich berechneter Knotenhöhe fiel nicht weiter auf, da es für die Berechnung der Balance zwischen zwei Teilbäumen keine Rolle spielt, ob ein konstanter Wert konsistent dazugerechnet wird oder nicht. Erst die kleine Korrektur von self.height brachte die Welt wieder in Ordnung. self.height = max(left.height if left else -1,
right.height if right else -1) + 1
Zusammengefasst
Wer programmiert, baut Kunstwelten aus Objekten auf. Und dabei ist vor allem wichtig, dass die Ideen und Vorstellungen im Kopf übereinstimmen mit den erschaffenen Objektwelten. Sonst weiß man nicht wirklich, was man da programmiert hat, was da abläuft und was sich da tut.
Kopfwelt und Programmwelt müssen unbedingt in Passung gebracht werden. Und dazu gibt es zwei Techniken:
- Visualisiere die Welt Deiner Objekte, damit Du Deine Erwartungen und Vorstellungen abgleichen kannst. Graphiz ist dafür ein sehr elegantes Werkzeug.
- Formuliere Deine Vorstellungen an die Objektwelt, so dass Brüche in der Objektwelt sofort zutage treten. Assertions und TestCases sind hier ein gutes Hilfsmittel.