Schnell(st)er Container mit N*finden und N*einfügen
-
volkard schrieb:
rapso schrieb:
weil ein hash nur sinn macht wenn man die "datenwordgroesse" reduzieren will mit der man indiziert
Ähm! Was?
eine hashtable benutzt den hash, wie ich schon sagte, um die groesse das datenwortes mit dem man indiziert zu reduzieren.
somit int -> size_t in diesem fall, was auf vector[i%vector.size()] hinauslaeuft und nicht viel sinn macht, da keine reduktion des datenwortes stattfindest.@Badestrand
die daten die du bearbeitest liegen nicht zufaellig von anfang an alle vor bzw kommen in schueben?
-
rapso schrieb:
volkard schrieb:
rapso schrieb:
weil ein hash nur sinn macht wenn man die "datenwordgroesse" reduzieren will mit der man indiziert
Ähm! Was?
eine hashtable benutzt den hash, wie ich schon sagte, um die groesse das datenwortes mit dem man indiziert zu reduzieren.
somit int -> size_t in diesem fall, was auf vector[i%vector.size()] hinauslaeuft und nicht viel sinn macht, da keine reduktion des datenwortes stattfindest.Aber eine Hashtable IST doch hier sinnvoll. Sie braucht bei N=1000 nur 5000 Bytes, während der Baum 32000 Bytes braucht und sie ist schnell. Und immer i%N statt i zu nehmen, ist schon eine Hashtable, allerdings ganz ohne Kollissionserkennung und so und daher meistens nicht gut genug. Außerdem kann unsigned hash(unsigned x){return x*2654435769u;} sehr wohl gut sein. Die Kollisionen noch zu versorgen, ist nicht schwierig.
-
volkard schrieb:
rapso schrieb:
volkard schrieb:
rapso schrieb:
weil ein hash nur sinn macht wenn man die "datenwordgroesse" reduzieren will mit der man indiziert
Ähm! Was?
eine hashtable benutzt den hash, wie ich schon sagte, um die groesse das datenwortes mit dem man indiziert zu reduzieren.
somit int -> size_t in diesem fall, was auf vector[i%vector.size()] hinauslaeuft und nicht viel sinn macht, da keine reduktion des datenwortes stattfindest.Aber eine Hashtable IST doch hier sinnvoll. Sie braucht bei N=1000 nur 5000 Bytes, während der Baum 32000 Bytes braucht und sie ist schnell. Und immer i%N statt i zu nehmen, ist schon eine Hashtable, allerdings ganz ohne Kollissionserkennung und so und daher meistens nicht gut genug.
der konstante overhead und das teure resizen seh ich als ziemlichen nachteil, was geschwindigkeit angeht. wenn es auf die groesse ankommt hast du natuerlich recht, da wuerde wohl keine bintree-implementierung auf weniger als das doppelte vom hashset kommen (jedenfalls keine fuer diesen fall ausreichende).
Außerdem kann unsigned hash(unsigned x){return x*2654435769u;} sehr wohl gut sein.
sorry, aber wenn du, wie wohl in diesem fall gesagt, komplett zufaellige eingangswerte hast, bringen multiplikationen mit irgendwelchen zahlen garnichts, eigentlich bringt jegliche transformation garnichts, wenn man die eingangswerte nicht irgendwie einschraenken kann.
(Es kostet nur Zeit).
-
rapso schrieb:
der konstante overhead und das teure resizen seh ich als ziemlichen nachteil, was geschwindigkeit angeht.
Hier gibt's kein Resizen, weil N schon vorher bekannt ist.
-
rapso schrieb:
sorry, aber wenn du, wie wohl in diesem fall gesagt, komplett zufaellige eingangswerte hast, bringen multiplikationen mit irgendwelchen zahlen garnichts,
hab nicht gesehen, daß das gesagt wurde.
-
Selbst wenn die Eingaben zufällig verteilt sind kann Hashing helfen -- wenn man es nämlich schafft die Verteilung mit der Hashfunktion in eine günstigere zu überführen... dafür reicht eine einfache Multiplikation natürlich nicht aus, aber auch Zufälligkeit muß nichts schlechtes sein. Insbesondere wenn die Daten zum Beispiel zufällig gleichverteilt sind, dann hat man nämlich erwartet eher wenig Kollisionen, wenn man einfach mit modulo auf die Hashgröße geht.
-
Ich habe den Eindruck, dass die heute "üblichen" std::unordered_map Implementierungen alle weit weg sind von dem, was Performance-mässig möglich wäre. MS hast das ja sogar ganz offiziell für ihre erste TR1 Implementierung irgendwo geschrieben (Release-Notes? Developer-Blog? Weiss nimmer...).
-
Ich denke das ist das Problem, dass Libraries eben keine Annahmen machen können. Wenn man aber immer und überall mit dem schlimmsten rechnen muss, dann kann man natürlich nicht in jeder Situation die beste Leistung bringen. Ich fürchte das Problem wird sich auch nicht so ohne weiteres einfach mit der Zeit lösen. Je komplexer und vielseitiger eine Datenstruktur ist, desto mehr Spielraum gibt es in der Anpassung an spezielle Gegebenheiten. Und wenn man die alle zur Verfügung stellt wird meistens so schwierig zu benutzen, dass es nur noch Leute schaffen, die sich wirklich auskennen.
-
Jester schrieb:
Selbst wenn die Eingaben zufällig verteilt sind kann Hashing helfen -- wenn man es nämlich schafft die Verteilung mit der Hashfunktion in eine günstigere zu überführen...
Ja, wenn die Daten zufällig aber nicht gleichverteilt sind. Wenn die Daten bereits gleichverteilt sind, kann man nixmehr machen. Es sei denn sie sind nicht wirklich zufällig
-
Ich fürchte das Problem wird sich auch nicht so ohne weiteres einfach mit der Zeit lösen.
Ich glaube einfach nur dass noch einiges an Performance drin ist. Ohne annahmen über die Daten treffen zu müssen.
Es muss ja nicht "optimal" sein. Wenn es so schnell ist, dass man selbst mit handgestricktem spezialisiertem Code bloss max. doppelt so schnell sein kann, ist das für mich schon vollkommen ausreichend.
Die derzeitigen TR1 Implementierungen wurden z.T. aus anderen Implementierungen gebastelt, die andere Schnittstellen hatten, andere Garantien geliefert haben etc. Daher sind die noch nicht wirklich "ausgereift". Stell dir vor jmd. hätte, weil er's schon rumliegen hat, die Implementierung von stable_sort, auch für sort genommen. Dann wäre sort auch langsamer als es sein müsste...
-
hustbaer schrieb:
Jester schrieb:
Selbst wenn die Eingaben zufällig verteilt sind kann Hashing helfen -- wenn man es nämlich schafft die Verteilung mit der Hashfunktion in eine günstigere zu überführen...
Ja, wenn die Daten zufällig aber nicht gleichverteilt sind. Wenn die Daten bereits gleichverteilt sind, kann man nixmehr machen. Es sei denn sie sind nicht wirklich zufällig
stimmt, aber dann ist man ja schon im günstigen Fall und die Identität ist eine prima Hashfunktion.
-
Danke für die vielen wertvollen Posts
Leider muss ich das Projekt gerade auf Eis legen, büffeln hat Priorität. Ich arbeite daran wahrscheinlich erst Ende September weiter, gebe dann nochmal Rückmeldung!
