Double Array Tries

Seit Jahren schaue ich mir immer wieder mal den Artikel “An Efficient Implementation of Trie Structures” von Aoe, Morimot und Sato an. Es ist eines meiner Steckenpferde, obwohl ich selber keine eigene Implementierung in Java beendet oder jemals Tries in meinen Projekten verwendet habe.

Ein Trie ist ein Suchbaum, dessen Zweige Zeichen repräsentieren und jeder Weg von der Wurzel zu einem Blatt eine im Trie gespeicherte Zeichenkette darstellt. Der Name Trie  wurde von  Edward Fredkin vorgeschlagen, verkürzt aus Information Retrieval .

Der erste hier dargestellte Trie enthält die Wörter BABY, BACHELOR, BADGE und JAR.  Es ist schon eine optimierte Version, da die eindeutigen Suffixe der Wörter (Y, HELOR, GE und AR) nicht über Zweige repräsentiert sind.

Nachteilig bei dieser Repräsentation ist es, dass an jedem Knoten, die ausgehenden Zweige einzeln auf das aktuelle Zeichen geprüft werden müssen, bevor der Algorithmus zum korrekten Folgeknoten wechseln kann.

Angenehmer wäre es hier, wenn man über eine Tabelle und dem Indexwert für den Buchstaben zum Folgeknoten springen könnte.

Der zweite Trie verwendet in jedem Knoten eine solche Tabelle, in der für jeden Buchstaben ein Verweis auf den Folgeknoten steht. Wie man schon in diesem kleinen Beispiel sieht, enthalten die Tabellen viele leere Felder.

Aber auch in diesem Beispiel ist schon eine Optimierung enthalten, die Länge der Tabellen ist auf den Index des letzten genutzten Buchstaben reduziert. Auch gestattet diese Optimierung dem Autoren einfachere Abbildungen zu zeichnen. Aber schon das Hinzufügen des Wortes BUS würde viele weitere Leerfelder produzieren.

Der dritte abgebildete Trie, verwendet eine einzige Tabelle in der die Tabellen des zweiten Trie ineinander geschoben werden. Durch das Füllen von Lücken in den Tabellen reduziert sich der Speicherbedarfs dieses Tries. Das Befüllen eines solchen Tries ist aufwendiger, da es bei neuen Einträge zu Kollisionen kommen kann, weil ein Tabellenplatz schon von einem anderen Knoten verwendet wird. Dann müssen die Einträge eines Knoten verschoben werden.

Damit in diesem Trie eindeutig ist, zu welchem Knoten der jeweilige Eintrag gehört, besteht jeder Tabellenplatz  aus zwei Werten base und check. Der base Wert gibt für den entsprechenden Knoten an, an welcher Position in der Tabelle die eigenen Einträge beginnen. Enthält ein Eintrag in base den Wert 22, dann kann man in der Tabelle ab der Position 22 die Einträge zu einem Knoten finden. Die Tabellenposition 26 kann also einen Eintrag für den Buchstaben C enthalten. Ob an dieser Position aber tatsächlich der Buchstabe C codiert ist, kann erst über den Wert in check verifiziert werden. Steht hier die Tabellenposition 20 des base Wertes 22, dann gehört die Tabellenposition 26 zum Knoten und der Buchstabe C ist darin enthalten. Steht dort ein anderer Wert, dann gehört diese Tabellenposition zu einem anderen, bzw. zu keinem Knoten.

Der Name Double-Array Trie ergibt sich also aus der Erfordernis für jeden Tabelleneintrag zwei Werte zu speichern.  Wie man Werte in einen Double-Array Trie einfügt und wie man sie wieder herausbekommen kann, wird in einem weiteren Beitrag beschrieben.

 

Refactoring mit Guard Clauses

Immer wieder finden sich Codefragmente, die sich in einer unnötig komplizierten Logik verlieren. Wie schon in Zauberei mit Wahrheiten angesprochen, sind es meist unterlassene Umstellungen im Code durch boolsche Umformungen.

Parameter prüfen

Eine häufige Ursache für die komplizierte Logik, ist die Prüfung der Eingangsparameter. Nicht alle Werte, die ein Parameter enthalten kann, machen Sinn für die Verarbeitung in der Methode. Daher werden sie abgefangen oder umgeformt. Die Bearbeitung von neu hinzugefügten Parameter wird in die bestehende Logik eingeflechtet, anstatt die Logik gänzlich zu überarbeiten.

private String method(String name, int age) {
  String state = null;
  if (name!= null && !name.isEmpty()) {
    if (age > 42) {
      state = normalMethod(name);
    } else {
      state = youngMethod(name);
    }
  } else {
    state = unknownMethod("anonymous");
  }
  return state;
}

Erst 13 Zeilen lang, aber schon recht kompliziert anzuschauen. Viel übersichtlicher lässt sich die Methode schreiben, wenn man alle Sonderfälle am Anfang der Methode behandelt. Das sind die Guard Clauses, die den eigentlichen Methodenaufruf bewachen.

private String method(String name, int age) {
  if (name == null || name.isEmpty() {
    return unknownMethod("anonymous");
  }
  if (age < 43) {
    return youngMethod(name);
  }
  return normalMethod(name);
}

Durch den Einsatz der Guard Clauses, ist die Methode nun besser zu verstehen und weitere Einschränkungen oder Erweiterungen können mit ihrer Hilfe einfacher ergänzt werden.

Derselbe Ansatz könnte auch bei der Überprüfung des Zustandes eines Objektes verwendet werden, doch sollte man dort besser auf State und Strategy Design Patterns zurückgreifen.

Exceptions als Überraschung

Ein sehr ähnlicher Anwendungsfall für Guard Clauses ist der Wurf einer Ausnahme aus dem Dickicht der Methodenlogik.  Auch hier leidet das Verstehen der Methode, wenn die Ausnahmebehandlung nicht an exklusiver Stelle, also vorne, beschrieben ist.

String value = null;
if (name != null && !name.isEmpty()) {
  value = complexLogic(name);
} else {
  throw new IllegalArgumentException("missing name");
}

Auch schon in diesem kurzen Beispiel ist die umgeformte Version mit der Guard Clause übersichtlicher.

if (name == null || name.isEmpty()) {
 throw new IllegalArgumentException("missing name");
}
String value = complexLogic(name);

Die Guard Clause ist ein ein gutes Mittel, um komplizierte Programmlogik zu entflechten und den Code lesbarer zu schreiben.

 

Von Beinahe-Zusammenstößen auf Fußwegen

Wenn sie diesen Beitrag gelesen haben, dann werden sie wissen, dass ich ein Linkshänder bin, bzw. ein Linksabdreher. Aber sie werden dann auch verstehen, warum wir Menschen manche Dinge völlig unterschiedlich wahrnehmen und einfache Mathematik dies erklärt.

Zu Kollisionen kommt es immer dann auf einem Fußweg, wenn die Entgegeneilenden  in unterschiedliche Richtungen ausweichen und deshalb weiter aufeinander zu steuern.

So etwas passiert hin und wieder oder aber ziemlich oft. Das liegt aber nicht an unserer Wahrnehmung oder schlechten Karma, sondern an der Verteilung  von Links- und Rechtsabdrehern in der Bevölkerung.

Vieles in diesem Beitrag ist noch Spekulation und muss in Feldversuchen überprüft werden, aber so viel wissen wir bereits. Die Verteìlung von Links- zu Rechtshändern in Deutschland liegt irgendwo zwischen 10% und 20% und die Ausweichpräferenz scheint direkt mit der Händigkeit gekoppelt zu sein.

Begegnen sich nun Passanten in einer Pareto-Verteilung (Dies ist ja immer noch ein Software Entwicklungs Blog), dann ergibt sich folgendes Bild. 64% der Begegnungen verlaufen unkritisch, weil nur Rechtsabdreher beteiligt sind, 4% weil nur Linksabdreher beteiligt sind, aber 32% der Begegnungen verlaufen kritisch, weil beide Gruppen beteiligt sind.

Dass ein Linkshänder sich über Leute ärgert, die ihm dauernd vor die Füße laufen, ein Rechtshänder aber das Problem nicht wirklich bedenkenswert hält, liegt an den Begegnungen, an denen sie beteiligt sind.

Bei einem Rechtshänder kommen 32 kritische auf 64 unkritische, also nur jede dritte Begegnung ist kritisch. Der von der Verteilung bestrafte Linkshänder kommt aber nur auf 4 unkritische von insgesamt 36 Begegnungen. Für ihn sind über 80% der Begegnungen kritisch, das ganze Leben ein einziger Spießrutenlauf.

Wenn ihnen das nächste Mal ein Passant entgegenkommt, dann weichen sie doch einfach mal zur anderen Seite aus. Der Linkshänder wird es ihnen danken.

 

Die Zunft der Programmierer

Um die Tätigkeiten von Software Entwicklern rankt sich eine Hecke von Unkenntnis und Ignoranz. Fast allen Führungskräften, Kollegen und vielen Akteuren ist nicht klar, was sie da eigentlich tun. Vermutlich hat es etwas mit dem Arbeitsplatz zu tun, der so vielen anderen Arbeitsplätzen ähnelt. Ein Schreibtisch mit einem Computerterminal. Während sich aber beim Chef nur Terminpläne, Kostenrechnungen und Email-Korrespondenz finden, entdeckt man


beim Softwareentwickler eine ganze Werkstatt voller Werkzeuge. Der Programmierer ist ein Handwerker und wenn man ganz genau hinschaut, ein Kunsthandwerker.

Die Software Craftmanship Bewegung artikuliert dieses Verständnis von einer Handwerkskunst schon seit einigen Jahren. Programmieren ist eine Tätigkeit, die Kreativität voraussetzt, die geübt werden will, die sich durch stetiges Lernen über die Jahre verbessert. Wie Kunstschmiede, Steinmetze und Tischler müssen die Programmierer mit den vorhandenen Materialien neues schaffen und dabei sorgfältig die Eigenschaften ihrer Kreation herausarbeiten.

Was hilft dieser nostalgische Blick auf die Arbeitswelt des Programmierers?

Wer etwas mehr Verständnis darüber erlangt, was seine Mitarbeiter eigentlich tun und realisiert, dass er einer Manufaktur und keiner Produktionsstraße vorsteht, kann bessere und kostengünstigere Software erstellen. Ein paar einfache Regeln lassen sich aus dem Selbstverständnis der Programmierer als Kunsthandwerker ableiten.

  1. Die Arbeit ist ein kreativer Akt. Wenn Sie einen Schmied an der Esse bei der Arbeit unterbrechen, erhalten sie keine feinen Messer aus Damaszenerstahl sondern Schrott. Wie andere Kreative kommt der Programmierer bei der Arbeit in den Flow und sollte dann nicht gestört werden.
  2. Programmieren ist ein Prozess und kostet Zeit. Lassen sie den Tischler die Möbel verfrüht liefern, dann fehlt vermutlich der Lack und sie werden keine große Freude an seiner Arbeit haben. Geben sie auch ihrem Programmier die nötige Zeit.
  3. Der Programmierer ist eine kostbare Ressource, er sollte seiner eigentlichen Profession nachgehen. Wenn sie ihre besten Glasbläser die Scherben auffegen lassen, vergeuden sie Talent. Für Routineaufgaben im Büro und die Präsentationserstellung gibt es preiswertere Büroangestellte und Führungskräfte.
  4. Ein Entwickler sollte sich immer nur um ein Projekt kümmern. Kein Steinmetz wird schneller, wenn er sich um ein Dutzend Grabmale gleichzeitig kümmern soll.
  5. Handwerker sind in früheren Zeiten auf die Walz gegangen um bei anderen Meistern zu lernen und bei manchen Handwerkern ist dies noch immer Tradition. Man kann seine Entwickler zwar nicht auf Wanderschaft schicken, aber ohne neuen Anregungen stagnieren die Fertigkeiten der Programmierer. Schicken Sie ihre Mitarbeiter auf Konferenzen, damit Sie weiterhin ihre Techniken verbessern können.
  6. Junge Software Entwickler können noch nicht gut programmieren und so wie ein ein Meister seinen Lehrling schult, sollten erfahrenen Programmierer den Neulingen ihre Erfahrungen vermitteln.
  7. In der Abteilung sitzen unterschiedliche Talente, die nicht einfach austauschbar sind. Sie können aus dem Schuster nicht einfach einen Schneider machen oder aus einem App Entwickler über Nacht einen Backend Spezialisten.

Wer das Programmieren als Handwerkskunst begreift, kommt zu einem sehr viel besseren Verständnis der Arbeit eines Software Entwicklers und kann so seine Arbeit auch wirklich würdigen.

 

Das Gift der Legacy Software

Jeder kennt Software die unter dem Euphemismus Legacy Software in vielen Firmen ihr Unwesen treibt. Obwohl in einer Hochsprache geschrieben, spürt man ihre Verwandtschaft mit Assembler Routinen und Shell Skripten. Generationen von missgelaunten Programmierern, Aushilfen und Praktikanten haben einen, vor Jahren noch recht ansehnlichen Entwurf, in etwas abgrundtief hässliches verwandelt.

Das Problem mit dieser Software ist, dass sie irgendwie funktioniert, aber niemand weiß wieso. Auch sind Informationen über den Sinn und Zweck weiter Teile der Software schlicht verloren gegangen. Fehler werden nur widerwillig behoben, Systeme selten migriert und veraltete Bibliotheken so gut wie nie ersetzt, automatisierte Tests unauffindbar und die Dokumentation hoffnungslos veraltet. Vielen Entwicklern und Verantwortlichen ist die Gefahr zu groß, durch Veränderungen an der Software, etwas kaputt zu machen.

 

Das Agile Manifest

 

Noch mehr Besucher

Im vorherigen Beitrag wurde das Visitor Pattern auf ein Enum angewendet, um das Enum nicht mit vielen Methoden zu überfrachten. Wie andere Klassen sollte ein Enum nicht gegen die Prinzipien des objektorientierten Designs verstoßen.

Die vorgestellte Lösung funktioniert zwar sehr gut, aber was soll der Entwickler machen, wenn neue Klassen die Bühne betreten? Nachdem er also ein Enum AccessLevel mit einer Menge interessanter Visitor Klassen verknüpft hat, kommt der Kunde mit neuen SecurityLevel und AnalyseLevel Anforderungen. Wie schön wäre es doch, wenn die bisherigen Visitor Klassen weiterverwendet werden könnten.

Etwas Generisches muss also her. Zuerst ein Visitor der verschiedene Enums besuchen kann.

public interface Visitor<E extends Enum<E>> {
  void visitEins(E e);
  void visitZwei(E e);
  void visitDrei(E e);
 }

Das Konstrukt sieht etwas seltsam aus, spiegelt aber die Natur der Enum Klassen wieder. Sie sind abgeleitet von der Klasse Enum und werden dieser als generischer Typ übergeben.

Das Enum, das vom Visitor besucht wird, muss sich der neuen Lage anpassen und bekommt eine etwas andere Methodensignatur.

public enum AccessLevel {
  ONE {
    public void accept(Visitor<AccessLevel> visitor) {
      visitOne(this);
    }
  },
  TWO {
    public void accept(Visitor<AccessLevel> visitor) {
      visitTwo(this);
    },
  THREE {
    public void accept(Visitor<AccessLevel> visitor) {
      visitThree(this);
    }
}

Das Enum bekommt einen Visitor, der genau auf seine Bedürfnisse zugeschnitten ist. Die Parameter der Methoden sind vom Type AccessLevel. Dazu noch ein generischer PrintVisitor, der auf beliebige Enums arbeitet.

public class PrintVisitor<E extends Enum<E> extends Visitor<E> {
  private String print;
  public void visitOne(E level) {
    print = "LEVEL-" + this;
  }
  public void visitTwo(E level) {
    print = "LEVEL-" + this;
  }
  public void visitThree(E level) {
    print = "LEVEL-" + this;
  }
  public String printLevel(E level) {
    level.accept(this);
    return print;
  }
}

Dieser PrintVisitor kann nun auf beliebige Enums angewendet werden, die einen solchen generischen Visitor akzeptieren.

PrintVisitor<AccessLevel>().printLevel(AccessLevel.ONE);
PrintVisitor<SecurityLevel>().printLevel(SecurityLevel.A);
 

Zu Besuch bei den Enums

Die Enums in Java sind eine typsichere Alternative zu den früher verwendeten Konstanten.

public class Test {
  private static final String LEVEL_ONE = "one";
  private static final String LEVEL_TWO = "two";
  ...
}

Mit solchen Konstanten hat man die üblichen Probleme, dass man sie überall fehlerhafter Weise einsetzen oder anstelle der Konstanten andere Werte des Typs verwenden kann. Besser also der Einsatz von Enums, die als echter Typ nur die definierten Konstanten zulassen.

public class Test {
  private enum Level { ONE, TWO }
  ...
}

Enums erlauben aber mehr als nur die Definition von Konstanten, sie können auch zusätzliche Methoden enthalten, die entweder für alle Elemente gelten oder aber für einzelne Elemente überschrieben werden können.

public enum Level {
  ONE {
    public String print() {
    return "LEVEL-A";
    }
  },
  TWO,
  THREE;

  public String print() {
    return "LEVEL-" + this;
  }
}

Selbstverständlich kann man auch mit diesen Sprachmittel seinen Schindluder treiben. Kein Sprachkonstrukt ist so sicher, dass nicht ein unfähiger Entwickler eine Zeitbombe daraus bauen kann. Beliebt sind bei den Enums insbesondere Membervariablen zur Speicherung von Zwischenergebnissen oder Zuständen. Dabei wird dann leicht vergessen, dass andere Software Entwickler von Enums eine gewisse Konstants erwarten.

Erkennt ein Novize die Möglichkeiten der Enums, dann ist Vorsicht geboten, denn sehr schnell expandiert das obige Beispiel und erhält zusätzliche Methoden die XML, HTML und JSON Darstellungen zurückliefern. Außerdem werden neue Konstanten FOUR und FIVE hinzugefügt und die Utility-Methoden next() und previous() ergänzt, um von einer Enum Konstante zur anderen zu wandern.

Ein schönes Pattern, um der wachsenden Zahl von Methoden entgegenzuwirken, ist das Visitor Pattern. Die spezielle Logik ist in Klassen ausgegliedert, die für unterschiedliche Besucher eigene Methoden bereitstellen. Eine Visitor-Variante für das obige Beispiel:

public enum Level {
  ONE {
    public void accept(Visitor visitor) {
      visitOne(this);
    }
  },
  TWO {
    public void accept(Visitor visitor) {
      visitTwo(this);
    },
  THREE {
    public void accept(Visitor visitor) {
      visitThree(this);
    }
  };

  public abstract void accept(Visitor visitor);
}

Der Visitor ist ein Interface, das für die Konstanten Methoden bereitstellt, die diese aufrufen können. Dabei geben sie sich selber als Parameter der Methode an. Im Falle einfacher Enums kann man dies natürlich auch vernachlässigen, da die Konstante der Methode keine zusätzliche Information liefert.

public interface Visitor {
  void visitOne(Level level);
  void visitTwo(Level level);
  void visitThree(Level level);
}

Um eine unser Beispiel zu vervollständigen fehlt nur noch die Implementierung eines Visitors.

public class PrintVisitor extends Visitor {
  private String print;
  public void visitOne(Level level) {
    print = "LEVEL-A";
  }
  public void visitTwo(Level level) {
    print = "LEVEL-" + this;
  }
  public void visitThree(Level level) {
    print = "LEVEL-THREE";
  }
  public String printLevel(Level level) {
    level.accept(this);
    return print;
  }
}

Für dieses Beispiel eine Menge Code, aber schon die Erweiterung für XML, HTML und JSON bedeutet keine Veränderung mehr am Enum, da ja die neue Funktionalität in den Visitor Implementierungen XmlVisitor, HtmlVisitor und JsonVisitor gebündelt wird.

 

Conway’s law

Any piece of software reflects the organizational structure that produced it.

 

Zauberei mit Wahrheiten

Haben Sie manchmal auch das Gefühl, dass ihre Kollegen Angst vor boolschen Ausdrücken haben? So mancher scheint die De Morganschen Gesetze wie die dunklen Zauberkünste einer Morgan le Fay zu fürchten.

So bleiben dann auch Ausdrücke, wie der folgende, für Ewigkeiten im Programmcode.

!(color != BLACK && color != WHITE) || color == WHITE

Häufige verweisen die Entwicklern auf den Optimierungen des Compilers, wenn sie ihre boolschen Ausdrücke nicht vereinfachen. Warum etwas händisch versuchen, was der Compiler sehr viel besser kann?

In erster Linie geht es natürlich um die Wartbarbeit und Erweiterbarkeit des Sourcecodes, denn nicht jeder Entwickler mag logische Labyrinthe in Form von verschachtelten If Anweisungen und großer Ausdrücke in den Bedingungen. Und vielen Entwicklern fehlt auch einfach diese autistische Freude eines Sodoku Spielers beim Ausfüllen von Wahrheitstafeln um herauszufinden, was der Autor einer Methode eigentlich bewirken wollte.

Findet ein Entwickler nicht schnell heraus, was ein Konstrukt bewirkt, schaltet er sofort auf Plan B um und installiert seinen Code neben den ursprünglichen, hängt weitere If-Else-Kaskaden an die schon existierenden und etabliert damit das Lavafluß Anti-Platten in der Software.  Der Sourcecode bläht sich auf und niemand weiß mehr, was eigentlich alles dort drinnen passiert.

Regeln

Knapp formuliert lauten die De Morganschen Gesetze, eine negierte Und-Verknüpfung entspricht der Oder-Verknüpfung der negierten Werte und umgekehrt. Man kann boolsche Ausdrücke mit diesen Gesetzen mechanisch umformen und mit Hilfe weiterer boolscher Rechenregeln vereinfachen.

Die Wahrheit in der boolschen Algebra ist, wie der boolsche Ausdruck oben.

color == BLACK || color == WHITE