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.

[Elvis]

Warum nimmst du eine kryptographische Funktion um deinen Hash zu generieren?
Ist der mit 128bit nicht ein /wenig/ groß und die Funktion selbst nicht ein wenig langsam? :shock:
Nichts gegen Ollies Funktion, aber IMHO wäre eine piepnormale CRC32 vollkommen ausreichend. Vor allem da eine Map keine Hashtable ist. ;)

[alzaimar]

Hier ist eine String-Hashtable mit CRC. mittlerweile verwende ich aber noch einfachere Hash-Funktionen, die im Compilerbau Verwendung finden. Die reichen auch vollkommen aus (und machen die Klasse um 50% schneller):

http://www.delphipraxis.net/internal...ght=dictionary

Anstelle einer sortierten Liste solltest Du eine Hash-Tabelle nehmen, das ist wesentlich schneller.

[Elvis]

Zitat:

Zitat von alzaimar

mittlerweile verwende ich aber noch einfachere Hash-Funktionen, die im Compilerbau Verwendung finden. Die reichen auch vollkommen aus (und machen die Klasse um 50% schneller):

Magst du die vielleicht auch mit uns teilen? :angle2:

[DP-Maintenance]

Dieses Thema wurde von "JasonDX" von "Neuen Beitrag zur Code-Library hinzufügen" nach "Open-Source" verschoben.
Passt hier besser hin, da eigentlich ganze Klassen und weniger kleine Codestuecke zur Verfuegung gestellt werden ;)

[3_of_8]

:wall:

Bitte nochmal etwas einfacher...

Wer empfiehlt mir jetzt was?

[alzaimar]

Ist doch ganz einfach:
1. MD5 ist overkill
2. sorted lists mit binary search ist langsam.

Ich empfehle

zu 1: CRC32 oder -noch besser- ELF-Hash oder PJW (googel mal)
zu 2: Hash-Maps oder Dictionaries, wie z.B. meine Unit.

[3_of_8]

Das ist keine Liste, sondern ein Array und damit eigentlich sogar mit vernünftiger Geschwindigkeit.

Bei n Elementen hat man eine minimale Suchzeit von O(1), eine maximale von O(log2(n)).

256 Elemente ^= O(8)

Ist doch eine vernünftige Zeit.

Ich gebe zu, dass man ein Problem bekommt, wenn man einfügt. Da hat man dann eine minimale Anzahl von Verschiebungen 0, aber eine maximale von n.

[himitsu]

Zitat:

Zitat von 3_of_8

Ich gebe zu, dass man ein Problem bekommt, wenn man einfügt. Da hat man dann eine minimale Anzahl von Verschiebungen 0, aber eine maximale von n.

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

MOVE

[Chewie]

Zitat:

Zitat von 3_of_8

Das ist keine Liste, sondern ein Array und damit eigentlich sogar mit vernünftiger Geschwindigkeit.

Bei n Elementen hat man eine minimale Suchzeit von O(1), eine maximale von O(log2(n)).

256 Elemente ^= O(8)

Bei einer Hash-Tabelle hättest du aber, jetzt mal von den Kollisionen abgesehen, O(1) ;)
Und Arrays sind ja auch nur spezielle Listen.

[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:

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:

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.

Delphi-Quellcode:

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.