Schnell(st)er Container mit N*finden und N*einfügen
-
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!
