set oder map?
-
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...
