041
22.01.2009, 12:10 Uhr
0xdeadbeef
Gott
(Operator)
|
Zunächst, was das Hashen angeht - den Jenkins-Hash habe ich, wenn du dich zurückerinnerst, im Zusammenhang mit Hashtables und ihrer Laufzeitabschätzung erwähnt. Einen sinnvollen Hash für diesen Fall kann ich ohne weitere Informationen über die erwartete Wertemenge natürlich nicht vorschlagen. Ich bezweifle zwar, dass wir entsprechende Informationen vom ursprünglichen Poster noch bekommen, aber wenn jemand einschätzen kann, dass er etwa 400000 verschiedene Werte kriegt, wird er auch eine grobe Vorstellung davon haben, welche das sein könnten - und dann ist die Identität mit großer Wahrscheinlichkeit alles andere als ein guter Hash.
Ansonsten, was die Skalierung der Hashtable in der "Vanilla-Implementierung" angeht...zwar ist mir, nachdem ich das gesehen habe, etwas klarer geworden, wie du auf die Idee kommst, dass das ganze mit einer Hashtable in O(n * log(n)) skaliere. Richtig ist es zwar auch da nicht, schon weil Zugriffe auf die Hashtable nicht mit dem gleichen n skalieren wie das Durchlaufen des Datenvektors, wenn ich das mal so salopp ausdrücken darf.
Wenn du deine Hashtable die ganze Zeit vollaufen lässt, kannst du natürlich keinen konstanten Zugriff auf die Werte erwarten, guter Hash hin oder her. Wenn zum Beispiel die Hashtable in deiner "Vanilla-Implementierung" gerade 393241 Werte beinhaltet, ist das Nachschlagen, ob ein Wert im Datenvektor schonmal gefunden wurde, plötzlich sehr teuer.
Der Punkt steht, Hashen funktioniert nicht so, dass man einfach hinschreibt "hash jetzt!" und etwas sinnvolles dabei rauskommt.
Was die Bittables angeht: Die praktischen Probleme, eben mal ein Achtel des verfügbaren Adressraums anzufordern, sind schon nicht zu unterschätzen, auch wenn sie lösbar sind. Laufzeittechnisch ist damit aber kaum etwas gewonnen, selbst wenn ausreichend Speicher vorhanden ist, dass das Betriebssystem nie auf die Idee kommt, irgendetwas auszulagern; wir skalieren auf einmal exponentiell mit der Registerbreite der Hostarchitektur. Der angeforderte Speicher nullt sich ja nicht von selbst.
Ja, wir sprechen von 100 Millionen Werten im Vektor, aber wir sprechen auf einer 32bit-Architektur schon von über 536 Millionen Byte in der Bittable. Allein der Aufwand, den du mit Paging und Initialisierung hast, geht schon weit über das hinaus, was man von einer vernünftig angewandten Hashtable zu erwarten hat. Und die 64bit-Architektur, inzwischen alles andere als ein exotisches Szenario, erwähne ich hier nur nochmal - das Problem sollte offensichtlich sein.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
Dieser Post wurde am 22.01.2009 um 12:11 Uhr von 0xdeadbeef editiert. |
