set oder map?
-
also was ich wann verwende ist halt sache,
map, etc die man in O(log n) durchsucht wenn es mehr darauf ankommt elemente geordnet zu halten, und es viele elemente werden könnten hash map wenn ich wirklich sehr schnellen zugriff brauche aber die anzahl moderat genug das sich der mehraufwand an speicher auch lohnt den man verbraucht.
-
RHBaum, der Hash ist nicht sortiert, der "ist" einfach. Weiters wird er (meist per Modulodivision) auf [0-N) runtergebrochen (wobei N die Grösse des Tables ist), wodurch die Ordnung des Hash (die ja schonmal nix mit der Ordnung der Keys zu tun hat) erst zerstört wird. Allgemein kann man sagen dass die Einträge (bzw. Zeiger auf die Einträge) in keiner verwendbaren Ordnung im Hashtable liegen -- nur die Position eines einzelnen Eintrages eignet sich zum schnellen Auffinden.
Weiters muss im Idealfall (und auch im Normalfall, wenn man es richtig implementiert) nicht ein Baum mit 3, 4, 5... Ebenen durchwandert werden, sondern der erste bzw. spätestens zweite Table-Lookup ist meist ein Treffer.
Ob bzw. um wieviel ein Hashtable schneller ist als z.B. ein RB-Tree hängt dann auch noch stark davon ab wie teuer der Vergleich 2er Keys ist. Hat man z.B. Strings als Keys (wo vielleicht vorne noch ein Namespace-Teil dranhängt, so dass viele Strings sich erst weit hinten unterscheiden) dann ist ein Hashtable auch bei ganz wenigen Elementen schon oft deutlich schneller.
-
hustbaer schrieb:
Ob bzw. um wieviel ein Hashtable schneller ist als z.B. ein RB-Tree hängt dann auch noch stark davon ab wie teuer der Vergleich 2er Keys ist. Hat man z.B. Strings als Keys (wo vielleicht vorne noch ein Namespace-Teil dranhängt, so dass viele Strings sich erst weit hinten unterscheiden) dann ist ein Hashtable auch bei ganz wenigen Elementen schon oft deutlich schneller.
Das versteh ich nicht, in beiden fällen muss ich vergleichen. Und auch das gleiche. Wo soll man nun bei den vergleichen unterschiede machen? Solange ich schlüssel nicht nur aufgrund ihrer Struktur vergleiche dauert es gleich lang.
Es bleibt halt nur noch das problem, wende ich divide and conquer an, so das ein O(log n) zugriff habe. Oder halt so ein zugriffsverfahren wie bei der hashmap wo ich im grunde direkt in eine zelle greife in der ich vermute das dort das element steht. Aber ich muss im endeffekt immer die beiden schlussel vergleichen.
Aber nochmal zum eigentlichen problem zurück. Bei der sturktur die gespeichert werden soll eignet sich auch ein trie hervorragend. http://en.wikipedia.org/wiki/Trie
-
Also erstmal vielen Dank für die interessante Diskussion, die Kompetenz dieses Forums überrascht mich positiv.
Hab nun ein unordered_set und eine Hashfunktion, die einfach die ID zurückgibt, und das klappt gut.
Hab aber noch eine Frage, wird bei einer Hashmap (unordered_map) der Key gehasht oder die Values? Und wenn ja, wie könnte eine gute Hashfunktion für strings aussehen?Fedaykin schrieb:
Aber nochmal zum eigentlichen problem zurück. Bei der sturktur die gespeichert werden soll eignet sich auch ein trie hervorragend. http://en.wikipedia.org/wiki/Trie
Gibt es für diese Datenstruktur gute Implementationen die man verwenden könnte?
Gruss
-
Eldoran schrieb:
Hab aber noch eine Frage, wird bei einer Hashmap (unordered_map) der Key gehasht oder die Values?
Der Schlüssel.
Und wenn ja, wie könnte eine gute Hashfunktion für strings aussehen?
Oha. Das ist eine Wissenschaft für sich, siehe http://en.wikipedia.org/wiki/Hash_table. Dort ist auch eine recht gute Funktion genannt.
-
Hm, das trau ich mir jetzt nicht zu, ne eigene Wissenschaft zu betreten.
Kennt jemand die hash<> struct ausm tr1? --> http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/structstd_1_1tr1_1_1hash_3_01__Tp_01_5_01_4.html
Ist die ordentlich implementiert für std::strings?
-
Eldoran schrieb:
Kennt jemand die hash<> struct ausm tr1?
Ist die ordentlich implementiert für std::strings?Ich gehe davon aus (auch wenn ich die Implementierung nicht kenne).
-
Fedaykin schrieb:
Das versteh ich nicht, in beiden fällen muss ich vergleichen. Und auch das gleiche. Wo soll man nun bei den vergleichen unterschiede machen?
Was ist daran nicht zu verstehen? Bei der Hashmap musst du erwartungsgemäß nur einmal, zweimal vergleichen, beim Baum hast du einen Vergleich pro Knoten im Pfad.
Je nachdem wie teuer Schlüsselvergleich und Hashfunktion sind, lohnt sich eine Hashmap dann auch schon bei kleineren Mengen.
Fedaykin schrieb:
Solange ich schlüssel nicht nur aufgrund ihrer Struktur vergleiche dauert es gleich lang.
Huh?
-
ok.... nun hab ich wohl was verwechselt ich dachte du meintest irgendwie das die vergleiche unterschiedlich aufwendig wären. Also ein vergleich in einer hashmap langsamer wäre als ein vergleich in einer map.
Zum thema strukturvergleich. Damit ist es z.B. möglich sortieralgorithmen die ein O(n) hab zu schreiben, aber das ganze ist im grunde ein fake da es ein O(n*m) ist wobei m von 0 bis x geht. Das heißt es kann sehr schnell sein als auch sehr langsam da ich halt die struktur analsiere ich vergleiche nicht zwei werte sondern z.B. bei zahlen zuerst die 0, dann die 10, dann die 100er stelle etc.
-
@Fedaykin: ich hab nur gemeint 1x "strcmp" ist schneller als 4x "strcmp" -- hat finix eh schon klargestellt
Und das mit den O(N) Sortieralgorithmen, Bucket Sort ist z.B. sowas, und ist kein Fake, sondern eine sehr gute Lösung für bestimmte Sonderfälle. Wenn ich z.B. 1000+ Elemente habe deren Sort-Key von 0-9 gehen kann, dann sortiere ich die natürlich mit Buckets (O(N)), und nicht mit nem normalen O(N log N) Sort.
Wenn der Sort-Key dagegen von 0-10000 gehen kann machen Buckets natürlich weniger Sinn...
