?
SeppJ schrieb:
Erfahrung. Du glaubst nicht, wie oft hier Leute mit solchen Behauptungen vorbei kommen
Doch, ich les hier schon auch mit.
fsdfdsf schrieb:
Kannst du vielleicht noch sagen, wie das Verhältnis ist: wie oft wird eingefügt (und damit umsortiert) ggü. wie oft wird abgefragt?
Wie komplex ist dein Item Datentyp? Also bezogen auf Speichergröße sowie Laufzeitverhalten beim Erstellen, Kopieren und Zerstören.
Genaugenommen kann ich das nicht unbedingt beantworten. Es sind verschiedene Anwendungsszenarien denkbar, deswegen versuche ich möglichst "alles" zu optimieren.
Kann sein, dass das Objekt einfach nur aufgebaut und nie benutzt wird. Kann aber sein, dass es einmal aufgebaut wird (paar hundert mal einfügen) und dann mehrere zehntausend mal dadrin gesucht wird. Oder wenn das längerfristig im Cache verbleibt auch deutlich länger.
D.h., langfristig ist die Suche auf jeden Fall wichtiger, deswegen vor allem daraufhin optimiert. Aber der Aufbau des Objektes sollte auch nicht unbedingt Zeit verschwenden, deswegen such ich nach schnellen/eleganten Möglichkeiten, so ein Handle System aufzubauen. Vor allem elegant, weil mich das Thema grad wie gesagt interessiert.
Die internen Objekte sind klein und billig, im Endeffekt paar ints. Und ein Item, das man hinzufügt, ist nicht das, was intern verwaltet wird. Über das Handle kann man dann gewisse Informationen bekommen, aber nicht direkt die interne Darstellung.
hustbaer schrieb:
Eine Möglichkeit ist z.B. als Handle den Index eines Lookup-Vektors zu verweden. Und im Lookup-Vektor steht der Index in den Vektor mit den eigentlichen Objekten. Dadurch kannst du den Vektor mit den eigentlichen Objekten kompaktieren. Den Handle-Vektor kannst du natürlich nicht kompaktieren. Du kannst aber freigewordene Indexe in einem 3. Vektor mitführen und wiederverwenden.
Versteh ich noch nicht... Wenn ich einen vector mit Indizes mitführe und meinen eigentlichen vector umsortiere, muss ich die Indizes in dem Handle vector doch trotzdem anpassen? Gelöscht wird nie was, oder was meinst du mit kompaktieren?
Wegen Allokatoren und vectoren... Das ist alles noch etwas komplexer, und ich will gar nicht so ins Detail gehen... Das ist jetzt kein std::vector, sondern ein QVector. Und wir verwenden sogar einen eigenen Speicherallokator, der tatsächlich ziemlich gut ist. Aber immer noch um einiges langsamer als einen vector für paar hundert Objekte vorreservieren und da diese PODs verschieben. Außerdem ist die Wahrscheinlichkeit, das neu eingefügte Objekte am Ende und nicht in der Mitte eingefügt werden, tatsächlich größer, aber das ist auch so ein Detail...
Mir ist schon klar, dass man nur genau Antworten geben kann, wenn möglichst viele Details bekannt sind. Aber ich wollte eigentlich paar allgemeine Ideen haben und habe den konkreten Use Case hauptsächlich beschrieben, um einen Eindruck zu vermitteln worum es geht. Wirklich ins Detail will ich da nicht gehen, dafür nehme ich auch gern in Kauf, dass ich nicht "die" optimale Antwort bekomme.