“Make it work, make it right, make it fast”
Kent Beck
Im dritten Beitrag über Double Array Tries wird der Code aus Teil 2 weiter bearbeitet und einige Ergänzungen und Verbesserungen vorgestellt. Um uns am obigen Zitat von Kent Beck zu orientieren, sind nun “make it right” und “make it fast” an der Reihe.
Häufig stoppt die Software-Entwicklung irgendwo im “make it work” und der Code ist schlecht strukturiert, schlecht zu pflegen und im unangenehmsten Fall sogar fehlerhaft. Auf diese Basis werden dann Erweiterungen und Performance-Optimierungen vorgenommen, die grundsätzliche Probleme in den Algorithmen weiter verschärfen. Verschleppte Bugs und aufgeschobene Refactorings rächen sich früher oder später in jedem Software Projekt.
Der Double Array Trie Code beweist in vielen automatisierten Tests seine Korrektheit. Das heißt leider noch nicht, dass die Implementierung absolut zuverlässig ist, aber die Tests geben Sicherheit für Erweiterungen und Verbesserungen.
Um den Ziel “make it right” näher zu kommen werden Interfaces hinzugefügt, die das Arbeiten mit dem Double Array Trie vereinfachen. Da der Trie eine Datenstruktur ist, mit der eine Menge von ein eindeutigen String Instanzen gespeichert werden, lassen wir ihn das Interface Set<String> implementieren.
Das das Löschen von Einträgen nicht implementiert wurde, werfen die Methoden remove, removeAll, und retainAll eine UnsupportedOperationException. Auch die toArray Methoden werfen eine UnsupportedOperationException , da sie bei großen Tries viel Speicherplatz verbrauchen.
Die Methoden addAll und containsAll werden mit Hilfe der Stream API auf den Methoden add und contains implementiert.
@Override
public boolean addAll(Collection<? extends String> c) {
return c.stream().map(this::add).reduce(Boolean::logicalAnd).orElse(false);
}
@Override
public boolean containsAll(Collection<?> c) {
return c.stream().allMatch(this::contains);
}
Für die Methode iterator wird eine Hilfsklasse benötigt, die ausgehend vom ersten Knoten den Trie durchläuft. Damit die Implementierung einfach bleibt, wird der aktuelle Status für jeden Knoten auf einen Stack gespeichert. Wird ein neuer Knoten betreten, dann wird sein Status auf den Stack abgelegt und während der Bearbeitung ständig aktualisiert. Wird die Bearbeitung des aktuellsten Knoten beendet, dann wird seine Status vom Stack gelöscht und mit dessen Vorgänger weitergearbeitet. Diese Depth-First Methode die Einträge aus dem Trie auszulesen hat den eleganten Seiteneffekt, die Einträge alphabetisch aufsteigend auszugeben. Wobei der Begriff alphabetisch ein wenig irreführend ist. Tatsächlich wird nach der dem Buchstaben-Kode im Trie aufsteigend ausgegeben. Üblicherweise werden die Buchstaben aber auch ihrer Stellung im Alphabet nach kodiert.
Der Iterator für den Trie liefert eine ganze Reihe weiterer Möglichkeiten für die Implementierung. Durch das Überschreiben der spliterator Methode im Trie Interface kann der Trie auch mit der Stream API verwendet werden.
Trie trie = new DoubleArrayTrie();
trie.addAll(Arrays.asList("bachelor", "jar", "badge", "baby");
trie.stream().map(String::toUpperCase).forEach(System.out::println);
Im obigen Beispiel wird der Trie mit fünf Wörtern gefüllt und danach alle enthaltenen Wörter mit der Stream API in Großbuchstaben umgewandelt und über die Standard Ausgabe gedruckt.
Nach dem Ziel “make it right” kann über das “make it fast” nachgedacht werden. Im letzten Beitrag wurde schon das Suchen einer neuen Position für einen Knoten als Performance-Problem angesprochen. Der triviale Suchalgorithmus der ersten Version durchsuchte die Doppelliste ab der Position 1 bis zum Ende. Selbst bei einem Trie mit einer Million Einträgen und 2,8 Millionen Elementen in der Doppelliste. Häufig sind aber nur sehr wenig Lücken im Trie, so dass dieser Ansatz fast immer belegte Elemente vorfindet.
Da leere Einträge sehr selten sind, werden ihre Positionen in einer zusätzlichen Liste gespeichert und nur dort nach möglichen Positionen gesucht. Mit dieser Optimierungen verbessert sich das Einfügen von neuen Wörtern signifikant.
int max = 1000000;
Alphabet alphabet = new Alphabet(
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZäöüßÄÖÜéáóèÅëçîåíûñúâàôêÉæøã");
DoubleArrayTrie dat = new DoubleArrayTrie(alphabet);
try (BufferedReader reader = new BufferedReader(new InputStreamReader(getClass().getResourceAsStream("/german.txt"), UTF_8))) {
long start = System.currentTimeMillis();
reader.lines().limit(max).forEach(word -> dat.add(word));
System.out.println(System.currentTimeMillis() - start);
}
try (BufferedReader reader = new BufferedReader(new InputStreamReader(getClass().getResourceAsStream("/german.txt"), UTF_8))) {
long start = System.currentTimeMillis();
reader.lines().limit(max).forEach(word -> assertTrue(dat.contains(word), word));
System.out.println(System.currentTimeMillis() - start);
}
Das obige Test benötigt zum Einlesen von einer Million Einträgen aus einer alphabetisch sortierten Liste deutscher Wörter auf einem betagten Notebook unter 10 Sekunden und zum Prüfen aller Werte etwa 4 Sekunden. Interessant mag vielleicht auch die Anzahl von Lücken in diesem Trie sein. Er enthält genau 19 leere Elemente.
Den Code zum Beitrag ist wieder auf Gitlab im Projekt Double Array Trie zu finden. Viel Spaß beim Studieren und Ausprobieren.