Dictionary Implementation

darktrym

darktrym

Fahnenträger
Ich weiß ja, dass hier noch andere anwesend sind mit Uni/FH Hintergrund bzw. Informatik, deshalb dieses Thema.
Beruflich musste ich ein Dictionary implementieren mit festen und bekannten Schlüsseln für eine Prä 2000 Programmiersprache(:huth:). Ich wollte Kollisionen und Sondierungen vermeiden.
Die Programmiersprache hat zwar ein Dictionary ählichen ADT aber mit Suchzeit O(log n), binäre Suche.
Es müssen derzeit 163 Schlüssel aka Spaltenbezeichner über eine Hashfunktion in einem Index für ein Array gewandelt werden.
Das funktioniert zwar jetzt, aber ich habe fast einen Tag gebraucht um die Hashfunktion zu designen. Sollte nun weitere Schlüssel hinzukommen, möchte ich vermeiden nochmal so viel Zeit da reinzustecken zu müssen. Gib's Ideen bzw. Dokumente wie man das optimieren kann?

Mein Ansatz derzeit:
Eine Hashfunktion(CRC32), wo nach der letzten Runde die Länge noch verrechnet wird.
Die Spaltenbezeichner können aus a..ZA..Z0..9 bestehen.
Ich nehme nur die 6 markantesten Stellen des Schlüssels, fülle auf wenn nötig.
Ergebnis ist dann ein 32Bit Wert, der dann mit AND auf die Größe des Arrays zurechtgestutzt wird.
Unbenutzte Positionen im Array werden markiert, hilft auch um Kollisionen früh zu erkennen.

Derzeit ist mein Array 8KB groß, kollionsfrei, 75x schneller als TStringlist.IndexOf.
 
Das Stichwort hier ist "Perfect Hashing". Bei bekannter Eingabemenge ist es recht problemlos möglich algorithmisch und damit automatisiert eine garantiert kollissionsfreie Hashfunktion zu konstruieren. Schaue für den Anfang mal hier: https://en.wikipedia.org/wiki/Perfect_hash_function Am Ende des Artikel sind sogar eine Generatoren verlinkt. Ist nur die Frage ob sie für deine Sprache (die mit wahlweise P oder D am Anfang?) geeignet sind.
 
Mal eine Frage, was ist denn an einer log (n) Suche verkehrt? Mit Hash hast Du zwar O(1) aber nur wenn du kollisionsfrei bist.

Das liest sich wie ein typischer Fall von premature optimization. Grade bei einer so kleinen Anzahl Schlüssel. Bei n = 4000000000 ist log(n) = 32.
 
Dir ist schon klar, dass Kollisionfreiheit bewusst gefordert wurde?
Ich weiß nicht wie du programmierst aber für mich sind Stringvergleiche O(n) und die Anzahl log n. In sehr wenigen Fällen ist das effizient.

Aber gperf sieht recht gut aus, der erstellt mir die perfekte Hashfunktion.
 
darktrym schrieb:
Dir ist schon klar, dass Kollisionfreiheit bewusst gefordert wurde?
Ich weiß nicht wie du programmierst aber für mich sind Stringvergleiche O(n) und die Anzahl log n. In sehr wenigen Fällen ist das effizient.
Zum Vergrößern anklicken....
Erst mal ist das Stringvergleich n ein Anderes als das btree n. Nämlich einmal länge des kürzeren strings und einmal Anzahl der Keys.

Zweitens ist ein Stringvergleich zwar O(n) aber ein durchschnittlicher (statt worst Case) Stringvergleich wird wohl nur in sehr komischen Datensätzen mehr als 5 Zeichen vergleichen.

Das heißt dann Du kannst bei einem Datensatz mit 4 Mrd. Keys pro Lookup mit einem Aufwand von 160 Zeichen Rechnen. Und das ist hoch geschätzt. Hashtables haben einen ganzen batzen Nachteile und ich glaube wenn Du das Benchmarkst wirst Du feststellen, dass Deine Hashtable nicht messbar schneller ist als die eingebaute b-tree Lösung.
 
Da das 163 Spaltenbezeichnungen sind ist der Anteil mit gemeinsamen Präfixen recht hoch. Zudem muss ich jeden Schlüssel finden somit ist deine Annahme schon nicht richtig und O(n) ist es immer noch. Zweitens hatte ich bereits geschrieben das meine nicht optimierte Variante 75x schneller(mit den Werten von gperf wirds nochmal schneller) ist und drittens wie kommst du darauf das Stringvergleiche in irgendeiner Form günstiger sind als gar keine. Denn das genau ist der Sinn hier eine Hashfunktion zu verwenden.
 
Garantiert (zumk jetztigem Zeitpunkt) sind eben Hashfunktionen wie SHA256/512 oder SHA3. Für Hashfunktionen für selbst genutzte Keys bei verschiedenen Algorithmen habe ich auch öfters schon FNV [1] verwendet. Hier solltest du aber auf mögliche Kollisionen prüfen und evtl. Buckets an die Slots anhängen.

[1]https://de.wikipedia.org/wiki/FNV_(Informatik)
 
Ich spiele noch mit gperf herum und frage mich kann er eine Hashfunktion finden ohne die Schlüssel zu erweitern? Es hat Null Sinn für jeden Schlüssel anders zu erweitern, weil dann lagere ich die Vergleiche einfach aus. Und warum gebe ich jeden Schlüssel einen Value wenn er am Ende nur den Index bestimmt und nicht auch noch den eigentlichen Wert liefert?
Nebenbei gibt's eigentlich eine Möglichkeit Fallthrough in Python adäquat nachzubilden?
Zmd. vom Ansatz ist gperf vielversprechend, keine längeren Rechnungen mehr nur Lookups.
 
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben