set oder map?
-
RHBaum, ein Hashtable hat die Keys NICHT sortiert.
http://en.wikipedia.org/wiki/Hash_table
Grundlegendste Grundlagen der Informatik. Datenstrukturen, Alter
-
hustbaer schrieb:
RHBaum, ein Hashtable hat die Keys NICHT sortiert.
http://en.wikipedia.org/wiki/Hash_table
Grundlegendste Grundlagen der Informatik. Datenstrukturen, Alter
Hehe, das sollte einem spätestens klar werden, wenn man den Begriff unordered_map liest.
-
RHBaum, ein Hashtable hat die Keys NICHT sortiert.
aber dafuer der hash, der ja quasi die sortierung ist. Ich meint nur ohne ne sortierung geht gar nix ....
Also in der praxis hab ichs noch nie gebraucht, nen normaler baum war immer schnell genug, bei 32bit IDs.
Ob die Hashmap wirklich performanter waer haengt ja dann auch stark von der verteilung und der Menge der ID's ab ...wie gesagt in meinem Buch ueber Algos steht das Hashes sich erst bei groesseren Structuren lohnen ... bei kleineren waeren Tree's meist effizenter.
Denn das würde ja bedeuten, dass Du eine Hash-Tabelle von der Größe 32 Bit brauchst -- also mit 2^32 Feldern.
So meint ich das ned ... Ich meint er hat eh ne 32bit als ID, da sollten die lookups im Baum effizient genug sein.
Ich kenn hashes nur aus der DB Welt, und da entschiedet die art des hashes, wie das zeugs arrangiert wird. Das kann nen fest positioniertes array sein, aber auch nen Baum, der auf den hashwert matcht. Wusst ned das bei ner hashmap bei datenstrukturen immer das positionierte array gemeint ist ...Ciao ...
-
RHBaum schrieb:
RHBaum, ein Hashtable hat die Keys NICHT sortiert.
aber dafuer der hash, der ja quasi die sortierung ist. Ich meint nur ohne ne sortierung geht gar nix ....
Vielleicht solltest du dir das Kapitel Hashtabelle noch einmal genauer anschauen. :p
Das einzige was "sortiert" ist, ist der Index.
-
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...
