hash_set (C++) Leistungsfähigkeit
-
Hallo, Ich habe festgestellt dass hash_set ist ziemlich langsam ist mit der std::string. auf dem PC 1HGz gibt es nur 20,000 Suchen pro Secunde (100,000 Woerter im hash_set). Es ist viel zu langsam. Ich versuchte verschiedene hash-Funktionen aber dass andert nichts. Kann jemand darueber was sagan wie kann ich hash_set effektiver machen?
-
strings sind halt langsam beim hashen.
Schau mal nach ob du vielleicht die strings vorher schon hashen kannst und im Prinzip nur den gehashten Wert in die map eintraegst.
uU ist ein Baum (wie zB std::map) auch gut - hat eben keine so schlimmen worst case faelle.
Weiters koenntest du die hashmap vergroessern, so dass es zu weniger kollisionen kommt.
schwer zu sagen ohne genauere angaben
-
ooops, das scheint mein Fehler zu sein
hash_set arbeitet doch ganz gut 500, 000 suchen pro sekunde mit strings.
-
Dieser Thread wurde von Moderator/in kingruedi aus dem Forum Linux/Unix in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
uU ist ein Baum (wie zB std::map) auch gut - hat eben keine so schlimmen worst case faelle.
Ich kenne diese allgemeinen Aussagen. Warum ist das so? Ich könnte doch intern ein Feld von Feldern verwenden. In welches Feld ich speichere erhashe ich, wie gewohnt. Sollte mehr, als ein Wert das slebe Ergebnis beim hashen erzeugen wird sortiert in das (innere) Fed eingefügt. Beim Auslesen kann dann einfach eine binäre Suche verwenden und habe somit einen Worst Case von O(log n), wie beim Baum, aber einen Durchschnitt von O(1).
Warum geht das bitte nicht?
-
Helium schrieb:
Warum geht das bitte nicht?
Natürlich geht das.
Ich bin jetzt mal von normalen Implementierungen ausgegangen. Man kann ja auch bei einer linked list einen op[] recht schnell hinbekommen, aber dennoch würde ich nicht sagen, dass der Zugriff per op[] auf eine list schnell ist (auch wenn ich es schnell machen _kann_ - aber es ist eben nicht die standard implementierung).
-
Ich finde dein Be3ispiel jetzt nicht so passend.
Der zugriff auf ein belibiges Elelement einer Liste dauert O(N), egal, ob mit oder ohne implementiertem op[].
Mein Hash hat normalerweise O(1) und im schlimmsten Fall O(N log N) ein "normaler" Hash im schlimmsten O(N). Ansonsten verhalten sie sich gleich.
-
Helium schrieb:
Ich finde dein Be3ispiel jetzt nicht so passend.
Warum?
Ich kann ganz bequem O(N/beliebige größe) machen. (dann muss ich eben ein array haben, wo die indeces drinnen stehen)Aber darum geht es doch garnicht. Ich bin halt von 'normalen' (wenn du so willst: naiven) Implementierungen ausgegangen. Schliesslich kann man nicht immer von der besten Implementierung ausgehen, oder?
Schliesslich sagst du ja auch 'normaler' hash und 'dein' hash um die Unterschied aufzuzeigen. Also lass mich von einem normalen hash ausgehen - schliesslich ging es um Vorschläge zur performance Steigerung. Und warum sollte man da nicht auch probieren ob ein Baum doch besser ist? (Ich kenne den Kontext ja nicht, deshalb habe ich Vorschläge gebracht was man verbessern _könnte_.)
-
Ich kann ganz bequem O(N/beliebige größe) machen. (dann muss ich eben ein array haben, wo die indeces drinnen stehen)
Regel der O-Notation:
O(N/Konstante) => O(N)
also bleibts bei O(N).
Wogegen ich die selbe Geschwindigkeit biete, wie ein Baum und die Zeitkonstante dürfte bei halbwegs vernüprftigen Implementierungen sogar kleiner sein. Dafür verhält sich 'mein' Hash beim Einfügen im Worst Case nicht so toll, wie ein Baum, aber IMHO immernoch so gut, wie ein 'normaler' Hash, wenn ich mich gerade nicht verdenken.Aber darum geht es doch garnicht. Ich bin halt von 'normalen' (wenn du so willst: naiven) Implementierungen ausgegangen. Schliesslich kann man nicht immer von der besten Implementierung ausgehen, oder?
Möglich.
Schliesslich sagst du ja auch 'normaler' hash und 'dein' hash um die Unterschied aufzuzeigen. Also lass mich von einem normalen hash ausgehen - schliesslich ging es um Vorschläge zur performance Steigerung. Und warum sollte man da nicht auch probieren ob ein Baum doch besser ist? (Ich kenne den Kontext ja nicht, deshalb habe ich Vorschläge gebracht was man verbessern _könnte_.)
Auch wenn ich dich in meiner ersten Antwort zitiert habe, wollte ich nicht dich kritisieren. Sicherlich kann er auch mal einen Baum ausprobieren, auch wenn ich bezweifle, dass das Besserung bringt. Es ging um den durchschnittlichen Durchsatz und nicht um den Worst-Case.
Aber wie es aussieht, ist das Problem ja eh schon behoben.