Stack, Queue und Map

[3_of_8]

Ich hab mir aus Spaß mal ein paar Datenstrukturen gebastelt.

Ein Stack und ein Queue, und dann (etwas komplexer) eine Map. Genauergesagt, zwei Maps.

Meine Maps speichern ein TObject mit einem String als Schlüssel. (der wird intern als MD5 Hash gespeichert, mithilfe von Assarbads MD5-Unit (abgespeckte Version))

Eine TArrayMap, die Schlüssel und Werte in sortierten Arrays speichert.

Eine TTreeMap, die Werte in einem Binärbaum speichert.

Der Baum ist noch nicht balanciert und ich konnte ihn bisher auch noch nicht auf Bugs testen (muss ich morgen mal machen), aber ich hängs trotzdem schon mal an.

Achja, ich hab übrigens in Wrappers.pas ein paar Wrapper-Klassen definiert, um auch primitive Datentypen speichern zu können. In den Maps gibt es so etwas schon vordefiniert.

EDIT: Source reformatiert.

[alzaimar]

Nein.

Erstmal ist eigentlich kein Unterschied zwischen einem Array und einer Liste. Eine Liste ist eine geordnete Menge von Elementen, ein Array eine Implementierung auf einem Rechner (Wieso gibt es denn eine TList, müsste das nicht TArray heißen?). Aber das ist Wortklauberei. Einige meinen, eine Liste ist verkettet, bei mir ist eine Liste aber mathematisch definiert. Und in der Mathematik gibt es, soweit ich das beurteilen kann, keine Arrays.

Ein sortierte Liste hat mit binary search einen Zugriffsaufwand von O(log n). Minimal und maximal gibt es da nicht. Im Mittel (darum geht's bei 'Big Oh') wird sich also die Zugriffszeit sublinear (log 2) erhöhen: Das ist schon mal nicht schlecht, aber eben miserabel im Vergleich zu einer Hash-map.

Eine Hash-Map hat einen Zugriffsaufwand von O(1), dort ist die Zugriffszeit eigentlich gar nicht von der Anzahl der Elemente abhängig! Eine Hash-Map mit 100.000.000 Elementen verhält sich performancetechnisch auch nicht anders als eine Hashmap mit 2 Elementen.

Wenn Du nur 256 Elemente in deinem Listenarray hast, ist es wurscht, wie du suchst, aber ich hatte dich so verstanden, das Du allgemeingültige Containerklassen entwickeln willst, und die müssen (oder: sollten) eben auch bei 100.000.000 Elementen schnell sein, sofern Du die Verwendung nicht explizit eingrenzt.

Beim Einfügen, Löschen und Suchen hat eine Hashmap einen Aufwand von O(1), wohingegen eine sortierte Liste mit O(n), O(n) und O(log n) dagegen hält. Was ist nun besser?

@Chewie: Die Kollisionen sind bei geeignetem Füllfaktor (bis zu 5/4) absolut zu vernachlässigen.

Zitat von himitsu:

Wobei man aber auch auf einen Schwups verschieben kann, wenn man die innere Struktur des Arrays kennt und beachtet ^^
MOVE

Autsch, es bleibt bei dem Aufwand O(n), egal welche Befehle ich verwende. Es wird zwar schneller, weil sich die Konstante (also die Zeit pro element) verringert, aber doppelt so viele Elemente zu verschieben benötigt eben auch doppelt so viel Zeit, egal, ob ich MOVE oder sonstwas nehme.

[3_of_8]

Jaja, ich glaubs dir ja...

[Chewie]

Zitat von alzaimar:

@Chewie: Die Kollisionen sind bei geeignetem Füllfaktor (bis zu 5/4) absolut zu vernachlässigen.

Das hängt aber auch von der verwendeten Hash-Funktion ab. Bei MD5 dürfte eine Kollision schon was außergewöhnliches sein, dafür dauert das Hashen halt ewig. Nehm ich was ganz einfaches und schnelles gibts wieder mehr Kollisionen. Und dann gibts ja auch wieder verschiedene Arten der Kollisionsbehandlung.

Aber das sind wohl wirklich Sachen, die man nur inSpezialsituationen auftreten, z.B. wenn die Daten so beschaffen sind, dass sie ähnliche Hashwerte ergeben. Warum dann nicht einen Funktionszeiger zur Verfügung stellen für das Hashing? So ist die Liste noch universaler verwendbar, eine eigene Hash-Implementation kann so leicht verwendet werden.

[alzaimar]

Nee, stimmt auch nicht.
Du nimmst einen Hash (egal ob MD5, CRC oder sonst was) und mappst den auf die aktuelle Hash-Tabellengröße runter.

TableIndex := Md5Hash(aString) Mod MyTableSize; Dabei kommt es zwangsläufig zu Kollisionen, da ein sehr großer Zahlenraum, auf einen wesentlich kleineren Zahlenraum abgebildet werden. Wichtig für eine Hash-Funktion ist nur, das sie die zu erwartenden Strings gleichverteilt im Zahlenraum der Hashtabelle abbildet.

Um dies zu erreichen, benötigt mal also erstens eine gute Hashfunktion, und zweitens geeignete Tabellengrößen. Hier haben sich Primzahlen als sehr gut erwiesen.