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?
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 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?

[3_of_8]

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 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 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.