023
20.01.2009, 10:49 Uhr
~raps
Gast
|
| Zitat von 0xdeadbeef: |
Lies dich bitte noch mal schlau über Hashtables. Was du da schreibst, ist stumpf nicht wahr.
Wenn wir von einer vernünftigen Hashtable ausgehen, d.h., einer ausreichend groß dimensionierten Hashtable (die Auslastung sollte nie über etwa 70-80% steigen) und eine vernünftige Hash-Funktion (z.B. Jenkin's one-at-a-time hash), die eine ausreichend gleichförmige und zufällige Verteilung hat, lässt sich abschätzen, dass ein Element in O(1) auslesbar ist. Die Mathematik dahinter greift auf Stochastik und Kombinatorik zurück und ist nicht ganz trivial; im Endeffekt läuft es darauf hinaus, dass ein Haufen Binomialkoeffizienten < 1 wegfallen.
|
ich sprach vom worst case, da du ja fuer die bittable auch vom worst case schriebst (mit boesen kernels die speicher auslagern, mit rumalllokieren dass es garnicht gibt etc.)
"theoretically the worst-case lookup time can be as bad as O(n)"
die bit-table ist im worst case O(1) beim zugriff.
die bit-table hat in jedem fall konstanten speicherverbrauch (im gegensatz zum nicht einschaetzbaren von deiner hashtable bzw. ueberlauf, je nach implementierung.)
die bit-table zugriffe sind schneller (ein cachemiss, besonders mit prefetching, braucht weniger als Jenkin's hash mit lauter RAW-hazards).
| Zitat: |
Dein Bit-Array dagegen verbraucht einen derart großen Haufen Speicher, dass es leicht zu Swapping führen kann und passt zweitens niemals in den CPU-Cache (Zusätzlich zu der vorher bereits bemerkten Abhängigkeit von Kernel-Details). Dass sich damit ein Laufzeitvorteil herausholen ließen, erscheint mir nach wie vor unrealistisch.
|
ja, kann schon verstehen dass du das noch nicht einschaetzen kannst, aber wenn du sowas mal selbst versuchst, wirst du auch sehen, dass diese simple methode alles andere in den schatten stellt was geschwindigkeit angeht. |
