Handles aus einer sortierten Liste vergeben

Ich habe eine Klasse, die einen sortierten vector (bzw. mehrere) von structs kapselt (keine Heap Objekte). Ich muss dem Benutzer eine MÃ¶glichkeit geben, etwas hinzuzufÃ¼gen und eine ID oder ein Handle zurÃ¼ckzubekommen, irgendwie so:

int addItem(const Item& item);

Damit das funktioniert, vergebe ich im Moment IDs und halte mir intern eine map mit der vergebenen ID und der Index Position. Wenn etwas eingefÃ¼gt wird und sich die nachfolgenden Positionen verÃ¤ndern, gehe ich die Map durch und passe die Positionen an.
Und das gefÃ¤llt mir nicht. Fallen euch schlauere MÃ¶glichkeiten ein, so ein Handle System zu realisieren?

wie groß ist die Liste?
Ist eine lineare Suche (also wenn der Benutzer getItem(int id) aufruft) ein Problem für dich?

Wenn nein, würde ich das simpel halten:

struct Wrapper
{
  Item item;
  int id;
};

Dann einen passenden Funktor der anhand von item die Sortierung festlegt erstellen und schon kannst du std::sort anwenden.
Die Suche ist, wie schon gesagt, proportional zur Anzahl der Listeneinträge.

SeppJ

Sortierter Vector? Ist das Problem eventuell trivial zu lösen, indem du eine andere Datenstruktur wählst? Beispielsweise die map, die du jetzt für die Handles benutzt direkt für die Objekte selbst? Oder eventuell auch eine list oder ein set.

Sagen wir mal so, mich wÃ¼rden auch unabhÃ¤ngig von meinem konkreten Problem jetzt noch paar LÃ¶sungsansÃ¤tze interessieren.

Die "Items" reprÃ¤sentieren irgendwelche Werte bzw. Bedingungen. Die Vectoren sind danach sortiert, damit ich schnell prÃ¼fen kann, ob eine Bedingung erfÃ¼llt ist oder nicht. Das ist in dieser Datenstruktur wichtig.
Die "ID" spielt dabei erstmal keine Rolle, deswegen bringt mir die Sortierung nach der ID nichts. Das ist ein weiteres, zweitrangiges Kriterium.
Heap Objekte mÃ¶chte ich auch nicht benutzen, sonst kÃ¶nnte ich vielleicht Zeiger rausgeben. Ich mÃ¼sste aber mal profilen, ob das nicht vielleicht tatsÃ¤chlich effizienter wÃ¤re. Das ganze ist ziemlich performance kritisch.
Die map will ich Ã¼brigens auch nicht haben, ich vermute, da wÃ¤re ein sortierter Vector mit pair<int, int> ebenfalls schneller, das wollte ich eh noch umstellen.

ErfahrungsgemÃ¤ÃŸ wÃ¼rde ich sagen, das sind paar wenige bis paar wenige hundert EintrÃ¤ge. Der Vorschlag mit dem Wrapper und der linearen Suche wÃ¤re also durchaus denkbar.

Ich mÃ¶chte aber wie gesagt auch einfach mal weitere Ideen sammeln. KÃ¶nnte mir vorstellen, dass Ã¤hnliche Probleme Ã¶fter mal vorkommen, auch wenn ich selber sowas bisher nicht wirklich gebraucht habe.

SeppJ

Kannst du mal versuchen, deine Probleme mit Umlauten zu beheben? Deine Beiträge kommen kaum lesbar bei anderen Nutzern an. Wenn du es nicht lösen kannst, dann benutz eine Umschreibung mit "ae", "oe", "ue". Das wäre dann weniger störend, beim Lesen. Derzeit ist das entziffern deiner Beiträge jedenfalls sehr anstrengend.

Bezüglich Heap: Was denkst du denn, wo Elemente eines Vectors gespeichert werden?

Bezüglich Sortierung: Daher habe ich dir doch Container vorgeschlagen, die selbstsortierend sind. In der Mitte eines Vectors etwas einzufügen ist fast immer schlecht und ein Zeichen, dass der Vector eine falsche Wahl ist.

Bezüglich Geschwindigkeit: Geschwindigkeit für was? Was soll mit den Daten denn überhaupt geschehen und woher nimmst du deine Vermutungen?

Allgemein: Je genauer du dein Problem beschreibst, desto besser kann man dir helfen. Aber wie schon gesagt: Bitte lesbar! Momentan ist mir das echt zu anstrengend, den genauen Inhalt deiner Beiträge zu entziffern.

Sorry, das mit den Umlauten ist mir nicht aufgefallen. Bei mir schauen eure kaputt aus. Egal, versuch die zu umschreiben.

Meine Vermutungen basieren darauf, dass ich an dem System seit ueber fuenf Jahren arbeite und schon alles moegliche ausgetestet und geprofiled habe. Und der sortierte vector ist schneller, als die selbstsortierenden Container. Die 2-3 Blockallokationen + paar Verschiebungen im Speicher sind viel billiger als hundert mal new+delete. Warum glaubst du, ich haette sowas triviales nicht intensiv ausgetestet? Das ist aber auch gar nicht meine Frage.
Ich will das auch nicht viel genauer beschreiben. Das ist ein Teil von einem Regelsystem und man kann sich diese Komponente als eine Art Control Table vorstellen. Ich will hier nicht ueber irgendwelche allgemeinen Loesungsmoeglichkeiten diskutieren, das ganze ist sehr komplex und man kommt schnell vom hundertsten ins tausendste. Wir diskutieren in der Firma jahrelang ueber alle moeglichen Aspekte und da wird jetzt sicher nicht ploetzlich eine geniale Loesung in einem Forum auftauchen, wo keiner das Problem im Detail kennt.

Mir gehts konkret um das Thema "Handles" und ob sich hier jemand noch paar andere Loesungsansaetze vorstellen koennte. Auch mal unabhaengig von der konkreten Aufgabenstellung, ich denke, auch allgemein formuliert ist die Frage interessant genug.

SeppJ

FastID schrieb:

Warum glaubst du, ich haette sowas triviales nicht intensiv ausgetestet?

Erfahrung. Du glaubst nicht, wie oft hier Leute mit solchen Behauptungen vorbei kommen und diese nicht getestet haben. Du bist die große Ausnahme, falls du die Wahrheit sprichst.

Mir gehts konkret um das Thema "Handles" und ob sich hier jemand noch paar andere Loesungsansaetze vorstellen koennte. Auch mal unabhaengig von der konkreten Aufgabenstellung, ich denke, auch allgemein formuliert ist die Frage interessant genug.

Interessant genug ist sie allemal. Ich denke auch schon darüber nach, aber das Problem wird erschwert dadurch, wenn der vector eine feste Vorgabe ist. Der natürliche Handle im Vector ist nun einmal der Index und wenn du den regelmäßig kaputt machst...

deine Beobachtung mit vector ist durchaus richtig, vor allem wenn es sich um eher "einfache" Objekte handelt die leicht kopierbar sind: dann ist ein vector tatsächlich (fast) unschlagbar bezogen auf das Laufzeitverhalten.
Siehe z.B. hier: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

Auch kann man ein bisschen nachhelfen, wenn man im Vorhinein bereits die obere Schranke kennt: wenn du weißt, du hast ein paar Hundert Objekte zu erwarten, dann machst du eben ein vector::reserve auf 1000 und du wirst ziemlich sicher keine Reallokationen haben.

Ich fasse zusammen:
* Benutzer fügt Objekt hinzu und bekommt Handle
* Benutzer kann mit Handle Objekt wieder abfragen
* Anzahl der Einträge ist überschaubar, sprich: max. ein paar Hundert
* Reihenfolge der Liste kann sich ändern (durch Neusortierung)

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.

P.S.: Wegen Umlauten: schau mal unter Ansicht -> Textkodierung, falls du Firefox benutzt. Ähnliche Funktionen bieten aber auch die anderen Browser. Dann sollten auch die Umlaute funktionieren.

hustbaer

@FastID
Um sinnvolle Antworten zu geben müsste man zumindest wissen auf was man hinoptimieren soll.
Also ist add/remove Performance wichtiger als Lookup-Performance?
Und reicht es wenn die amortisierte Zeit kurz ist, oder muss es "echtzeitmässig" so sein dass alles immer inetwa gleich lange dauert. Oder anders gesagt: wäre es schlecht wenn alles meisten ruck-zuck geht, dafür aber z.B. jeder 1000. Aufruf 100x so lange dauert?

Weitere Fragen...

Wie viel Speicher können/dürfen wie verschwenden?

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.
Dadurch verschwendest du nur Speicher in der Grössenordnung von N Integers, wobei N der Unterschied max-min der Anzahl an gespeicherten Objekten ist. Was für viele Anwendungen OK sein wird.

Die 2-3 Blockallokationen + paar Verschiebungen im Speicher sind viel billiger als hundert mal new+delete. Warum glaubst du, ich haette sowas triviales nicht intensiv ausgetestet?

Ach, da muss ich SeppJ Recht geben.
Weil: Moderne Allokatoren sind schon relativ flott. Und es stimmt auch dass die allermeisten Leute die sich Gedanken über Performance machen und hier fragen die trivialen Lösungen vorab für schlecht/zu langsam halten und eben gerade nicht ausprobiert haben.

Und nochmal zur Sicherheit nachgefragt: Aktuell sind die eigentlichen Objekte bereits in einem std::vector? Und falls ja: habt ihr auch entsprechenden Code drinnen der diesen Vektor zwingt überschüssigen Speicher freizugeben? Per Default macht er das nämlich nicht. Also wenn man nicht mit swap , shrink_to_fit oder dergleichen draufhaut. Und wenn er es nicht macht, und euer System dadurch nicht in Speichernot gerät, dann wird das oben beschriebene System sicher auch keine Speichernot verursachen. Bzw. dann lassen sich mit vertretbarem Aufwand auch noch schnellere Systeme umsetzen.

krümelkacker

Wie oft wird etwas eingefügt bzw gelöscht?
Wie oft werden die Objekte über eine ID angesprochen?
Wie oft werden die Objekte ohne ID angesprochen, also direkt im Vektor, wobei die Sortierung dann wahrscheinlich wichtig wäre?

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.