Gedanken zur agilen Softwareentwicklung
Kaum ein Bereich in der Software Entwicklung gebiert so furchtbare Töchter wie die Sortierung. Obwohl die Java Standard Bibliothek viele wunderbare Klassen bereitstellt, finden sich immer wieder Programmierer, die ihre eigenen Holzwege schaffen.
In den ersten drei Beiträgen dieser Reihe wurde das Thema Löschen aus einem Double Array Trie immer wieder umgangen. Eine kleine Sünde, die in diesem Beitrag nun endlich ihr Ende findet. Außerdem wird die Einsatzmöglichkeit des Trie erweitert, in dem eine Map Implementierung basierend auf dem Double Array Trie Algorithmus vorgestellt wird.
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.
In einem früheren Beitrag wurde die Datenstruktur Double Array Trie (DAT) vorgestellt. Zur schnellen Suche von Wörtern werden diese in einer linearisierten Baumstruktur gespeichert. Die einzelnen Knoten des Baumes werden dabei überlappend in die Liste eingefügt. Enthält ein Knoten Lücken, dann können diese durch Werte anderer Knoten aufgefüllt werden. In diesem Beitrag werden Einfügen und Auslesen der DAT Struktur erläutert.
Hin und wieder stolpert der Entwickler bei seiner Suche nach guten Lösungen über interessante Algorithmen, die er eigentlich gerade nicht braucht. In diesem Fall handelt es sich um Voses Algorithmus zum generieren von Zufallswerten anhand einer vorgegebenen Verteilung.
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 … Weiterlesen