Kategorie: Algorithmen

Aufzählungen und andere String-Konkatenationen

Immer wieder müssen Strings in Java Applikationen zusammengefügt werden. Lange vorbei sind dabei die Zeiten, in denen der Entwickler selber die String Instanzen und einen Separator in einen StringBuilder stecken musste. Mittlerweile kann der Entwickler bei der Verwendung von Streams auf die Collectors.joining Methoden oder in anderen Fällen, auf den dahinter verborgenen StringJoiner, zurückgreifen.

Weiterlesen

Sortieren auf Teufel komm raus

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.

Weiterlesen

Double Array Tries (Teil 4)

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.

Weiterlesen

Double Array Tries (Teil 3)

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.

Weiterlesen

Double Array Tries (Teil 2)

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.

Weiterlesen

Effizient würfeln

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.

Weiterlesen

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

Weiterlesen