-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
17. Mär 2010
Hast schon Recht: Das von mir erstellte Testszenario vergleicht wirklich Äpfel mit Birnen. Allerdings habe ich native Delphi-Strukturen mit aufgenommen, um zu zeigen, wer wann wo wie schnell bzw. lahm ist.
Tunen kann ja, wer will. Nur die eh schon schnelle Dictionary wurde durch diese blöden AnsiUppercases (die mir irgendwann reingerutscht sind), unnötig ausgebremst.
Ich poste hier mal eine...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
16. Mär 2010
Bevor man vergleicht, muss man dafür sorgen, das man Apfelsorten untereinander vergleicht, und nicht Äpfel mit Birnen.
Alle Testszenarien stellen sicher, das ein Schlüssel nur 1x eingefügt wird, der Schlüssel also eindeutig ist. Daher muss vor dem Einfügen eine Suche durchgeführt werden.
Berücksichtigt man das, wundert nicht, das RB-Tree und AVL-Tree in etwa identisch hinsichtlich ihres...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
9. Nov 2009
Eine Hashmap ist unsortiert. Die Schlüssel werden anhand eines Hash-Wertes gefunden (zumindest fast).
Eine Skiplist ist eine etwas komplexere mehrfach verkettete Liste, bei der die Schlüssel sortiert vorliegen.
Ich glaube, ich habe bei beiden einen Enumerator implementiert, also sowas wie: Gehe zum 1.Element, Hole das nächste Element bis keine mehr da sind...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
14. Aug 2009
Danke für das Kompliment. :stupid:
Natürlich gibt es immer Möglichkeiten, die Datenstrukturen für eigene Bedürfnisse zu optimieren. Allgemeingültig sind sie damit jedoch nicht mehr.
Ein schönes Beispiel hierfür sind Listen, die zuerst befüllt und dann einmalig sortiert werden, um die anschließende Binärsuche zu ermöglichen.
Ich kann mir vorstellen, das alle Strukturen von der Vorgabe...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
17. Jan 2009
Im Code der Testsuite hatte sich eine kleine Nachlässigkeit eingeschlichen, die mquadrat entdeckt hat. Eine überarbeitete Version ist im 1.Post zu finden.
Puh, für ein Tutorial über die Datenstrukturen fehlt mir im Augenblick die Zeit, da die Thematik, richtig aufbereitet, doch etwas umfangreich wird. Insbesondere eine Erklärung der Skiplists ist nicht einfach. Sie muss ja verständlich sein....
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
16. Jan 2009
Das ist interessant! Hast Du deine Optimierung mal in die Teststruktur eingepflegt, sodaß man unmittelbar einen Vergleich mit den anderen Datenstrukturen ziehen kann?
Immer wieder wichtig ist zu wissen, ob und wie eine Datenstruktur skalierbar ist, ob sie also auch bei exorbitanten Datenmengen noch performant ist. Wenn man es braucht.
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
11. Dez 2007
Yo, gute Idee.
Vermutlich wird die Hashmap ggü. der Skiplist besser abschneiden, da bei der Hashmap (=Dictionary) der String per Hash-Funktion in einen Integer umgewandelt wird. Anschließend finden (fast) nur noch Integer-Vergleiche statt.
In allen anderen Strukturen wird dagegen der zu suchende Text stehts mit einem Schlüssel verglichen.
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
10. Dez 2007
Ich schrieb doch bereits, das das der Bayer-Baum nicht hier herein passt, da es sich nicht um eine generische Struktur bzw. Algorithmus zum schnellen Speichern von Assoziationen in-Memory handelt. Der Bayer-Baum wurde doch vor allen Dingen für Page-I/O entwickelt, daher die Seiten konstanter Größe.
Im Übrigen benötigt man doch kein Video, um einen Algorithmus zu verstehen. Ein gutes Buch...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
10. Dez 2007
Der B-Baum ist eine Mischung aus T-ärem Baum und Binary Search, wird also in der Performance irgendwo dazwischen sein.
Desweiteren ist der BB für Daten gedacht, die sich auf einem externen Datenträger befinden, und passt deshalb vom Konzept her hier nicht rein.
Ich vermute auch, das der Overhead etwas zu hoch ist, um mit reinen in-Memory-Lösungen mithalten zu können.
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
22. Okt 2005
Hi,
Danke für den Tip. Ich hab sie mal eingebaut Im 1.Posting kann man die neue Version laden. Sie misst nun auch nur das Suchen.
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
21. Okt 2005
Stringlist= Delphi TStringlist mit Sorted := True und Duplicates := dupIgnore, Suchen per binary search
AVL - Tree: AVL-Baum (Binärer ausgeglichener Baum)
Skiplisten: Verkettete Listen mit zusätzlichen Pointern auf weiter entfernte Elemente (Skip list)
Directories : Hash tabellen (Nein. Nicht zum Rauchen)
Wenn Hashtabellen voll sind, werden sie erweitert. Due Größe der vergrößerten...
-
Forum: Object-Pascal / Delphi-Language
Delphi
by alzaimar,
21. Okt 2005
In Anbetracht der häufig gestellten Fragen nach 'Suchen in einer Liste' und Ähnlichem hab ich mal vier Verfahren verglichen:
- Stringlist
- AVL-Baum
- Skiplist
- Hashlist
Das Testprogramm fügt zunächst Werte in die jeweilige Datenstruktur ein und sucht sie anschließend wieder. Beim Einfügen wird sichergestellt, das der Eintrag nicht schon in der Liste ist.
Ich würde mich freuen, wenn...
