Liste - Performance verbessern

mnimda

ich weis das es nicht sehr fair ist es kommen noch 2 funktionen zum loschen und einfügen von einträgen an bestimmten stellen dazu. ich wollte blos wissen ob man irgendwo da noch was optimieren könnte euerer meinung nach ich finde die liste gut sie ist nicht zu voll

ach ja wegen den iteratoren wenn ich genauer wüsste was das ist und wie das geht würde ichs vllt einbauen kann mir das jemand erklären

Marc-O

Hy

Und hier eine Kleine Hilfe: Klicken.

Hier ein kleiner Artikel, aber schau auf den C++ Teil.

Bzw hier im Forum ca. 10 Artikel unter deinem findest du das hier

Mfg marco

Edit: Hilfe eingebaut :), URL-Tags berichtigt (Blöde Laptoptastatur :()

mnimda schrieb:

ach ja wegen den iteratoren wenn ich genauer wüsste was das ist und wie das geht würde ichs vllt einbauen kann mir das jemand erklären

!(Wir sind alle froh, dass du nicht Google kennst);

otze

Deine Liste mact genau das, was std::list macht. Checke also nochmal, ob alle DEBUG-Flags draussen sind(#defines!) und ob der compiler maximal optimiert.

volkard

Ich würde center wegmachen. Wer einen schnellen Indexzugriff haben will, soll sich was anderes als eine verkettete Liste nehmen. center macht ja nur doppelt so schnell.

Und dann das anbieten, was die Liste sehr schnell kann.
Im Fall der doppelt verketteten Liste würde ich
- Aus der doppelt verketteten Liste mit Start und Ende einen doppelt verketteten Ring mit Anker machen.
- Den Anker ohne sinnvollen Wert immer anlegen, damit der Ring nie leer ist.
- Den Anker als Objekt und nicht nur als Zeiger in das Listenobjekt fest aufnehmen.
Viola, schon gehen vorne und hinten einfügen und löschen ohne ein einziges if.
Jetzt stört nur noch das eine zuviele Element.
- Klasse Basisknoten machen, die nur die Links hat und davon Datenknoten erben lassen, der zusätzlich Daten hat.
- Das Listenobjekt hat nur einen Basisknoten. Zum Einfügen und Löschen wird gegebenenfalls auf Datenknoten runtergecastet.
Viola, ein hübsches minimales Ding.
Von hier aus würde ich mir überlegen, was ich vielleicht dazufrickeln will und aber sobald es auf die Performance der bisherigen Funktionen schlägt, andere Listentypen forken.

Der Sinn des Center-Zeigers erschließt sich mir nicht wirklich. Wenn man random access benötigt, nimmt man üblicherweise std::vector oder std::deque (letzteres, wenn man an beiden Enden des Containers Löschen und Anfügen will oder nicht abschätzen kann, wie viele Elemente man benötigt). Beide sind in diesem Fällen wesentlich performanter als eine verkettete Liste; in der Tat ist diese std::deque hauptsächlich dann vorzuziehen, wenn Splicing benötigt wird (also das Einfügen/Löschen in der Mitte des Containers).

Ansonsten bietet es sich bei einer verketteten Liste an, Dummy-Elemente am Anfang und Ende zu benutzen; sie fügen der Liste eine Invariante zu (head und tail sind nie NULL), die Operationen an den Enden stark vereinfachen. So spart man sich einen Haufen Gebranche und hat leichter verständlichen Code. Etwa könnte push_back dann so aussehen:

void push_back(value_type const &val) {
  node_t *p = new node_t(val);

  val->prev = tail->prev;
  val->next = tail->prev->next;
  tail->prev->next = val;
  tail->prev = val;

  ++size;
}

Übrigens spart man sich damit auch die Notwendigkeit für einen Default-Konstruktor und einen Zuweisungsoperator (obwohl std::list, wenn ich das richtig im Kopf habe, an anderer Stelle Assignable verlangt).

Natürlich wäre es guter Stil, die Verkettungslogik an zentraler Stelle zu haben (etwa der insert-Funktion mit Iterator).

volkard

seldon schrieb:

Ansonsten bietet es sich bei einer verketteten Liste an, Dummy-Elemente am Anfang und Ende zu benutzen; sie fügen der Liste eine Invariante zu (head und tail sind nie NULL), die Operationen an den Enden stark vereinfachen. So spart man sich einen Haufen Gebranche und hat leichter verständlichen Code.

Ja. Und weil ich bemerkt habe, daß der Nachfolgerzeiger des Endeknotens und der Vorgängerzeigers des Anfangsknotens unbenutzt sind, schlage ich sogar vor, deinen Plan ein winziges Bißchen zu ändern und nur einen einzigen Grenzknoten zu nehmen, daß also der selbe Grenzknoten die Liste auf beiden Seiten begrenzt.

Das ergibt auf den ersten Blick eine Menge Sinn, gerade bei kurzen Listen - und wenn ich mich nicht verkucke, ist das in der Anwendung identisch, sofern der Anker bei einer leeren Liste mit prev und next sich selbst referenziert.

Guter Plan! Den muss ich mir merken.

hustbaer

@mnimda:
Ich bin mir auch nicht sicher, ob für dich eine Liste die beste Datenstruktur ist.
Wird wirklich so häufig mitten drin gelöscht/eingefügt?

Superlexx

Naja, ich will nicht nörgeln, aber eine Liste, die einen Bruchteil der Features und ein Vielfaches der Bugs einer guten std::list hat, nein, darauf hat die Welt nicht gewartet :).

Die XGenList hat keine Iteratoren ergo sehr wenige Algorithmen. Auch nicht die einfachste exception safety. Verlangt default-constructible Type. Kein custom allocator. Wenn man Iteratoren hat, dann will man auch die Laufzeitprüfungen haben wie sie die großen STLs anbieten.

Wenn man was schnelles braucht, dann dürfte die EASTL einen Blick wert sein. STLport ist auch nicht von schlechten Eltern. Dinkumware ist Hausmannskost :D. Ansonsten immer schön LTCG und PGO machen, bringt bei STL-Code locker Faktor 3 :).

hustbaer

Superlexx schrieb:

Kein custom allocator.

Will ja nicht kleinlich sein, aber das Feature (bzw. das Fehlen davon) interessiert glaube ich nicht wirklich viele Leute.

Du wärst erstaunt. Erwähn das mal jemandem gegenüber, der ein paar Dutzend Threads zu bedienen hat; der hätte ernsthafte Probleme damit, wenn die sich alle um den selben Heap prügeln müssten.

hustbaer

seldon schrieb:

Du wärst erstaunt. Erwähn das mal jemandem gegenüber, der ein paar Dutzend Threads zu bedienen hat; der hätte ernsthafte Probleme damit, wenn die sich alle um den selben Heap prügeln müssten.

In so einem Fall nimmt man einen Allocator (globales new/malloc Replacement) der damit gut umgehen kann.
Irgendwas ala tcmalloc, jemalloc etc.

Das über std::allocator zu lösen halte ich für eine relativ schlechte Idee, das schreit geradezu nach Bugs.
std::allocator wird mit Containern mitkopiert.
Stell dir mal vor was passiert wenn Worker-Thread X eine std::list mit custom Allocator kopiert um sie in eine Queue zu stopfen, wo Thread Y sie rausnimmt und munter weiterbearbeitet.
Sieht alles ganz sicher aus, da ja kopiert wurde.
Dummerweise wurde auch der Allocator mitkopiert. Der greift dann auch munter auf die Datenstrukturen zu, die eigentlich für Thread X gedacht sind, ganz ohne Locking, weil wir ja optimieren wollten. -> BUMM

Was man natürlich machen kann, ist einen Allocator zu schreiben, der einfach nur tcmalloc o.ä. kapselt. Dabei sind die Instanzen des Allocator selbst nicht Thread-affin, und können gefahrlos kopiert werden. Allerdings würde ich in dem Fall vorziehen gleich global new/malloc zu ersetzen. Ist speziell unter Windows nicht ganz trivial, aber einige fertige Allocator bringen den nötigen Code mit.

p.S.: std::list ist auch ein ganz heisses Eisen wenn's um Allocator mit State geht: nicht alle STL Implementierungen unterstützen in dem Fall splice() korrekt.

DocShoe

Superlexx schrieb:

...
Wenn man was schnelles braucht, dann dürfte die EASTL einen Blick wert.
...

Hat EA die inzwischen freigegeben? Habe nirgends was gefunden, ausser einem Whitepaper.

Christoph

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

ipsec

Christoph schrieb:

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

http://cplusplus.com/reference/stl/list/splice/ schrieb:

Complexity: Constant on all cases, except when x is a list object different than *this in the third function version, in which case it is linear in the range between first and last (iterator advance).

Mit 3. Variante ist dabei die Variante von dir gemeint. Wie du siehst, hat diese also (wahrscheinlich aus genau dem Grund mit der Länge) lineare Laufzeit.

life

Dinkumware hat jedenfalls constant time size Methode.

Christoph

ipsec schrieb:

Christoph schrieb:

otze schrieb:

Deine Liste mact genau das, was std::list macht.

Nicht ganz: Eine std::list speichert ihre Länge im allgemeinen nicht, sondern berechnet sie ad-hoc bei einem length()-Aufruf.

Der Grund ist, dass die Funktion std::list::splice(iterator p, list<T>& x, iterator f, iterator l) laut C++-Standard in Konstantzeit laufen muss. Das ist nicht zu erreichen, wenn eine std::list zu jedem Zeitpunkt ihre Länge wüsste.
Die Aufgabe der Funktion ist: Verschiebe alle Elemente im Range [f,l) aus der Liste x heraus und in die aktuelle Liste direkt vor Position p hinein. Das ist nur ein bisschen Pointer-Gebastel und ist in Konstantzeit implementierbar. Wenn aber x und *this ihre Länge speichern würden, müsste splice() zählen wie viele Elemente denn gerade verschoben wurden.

http://cplusplus.com/reference/stl/list/splice/ schrieb:

Complexity: Constant on all cases, except when x is a list object different than *this in the third function version, in which case it is linear in the range between first and last (iterator advance).

Mit 3. Variante ist dabei die Variante von dir gemeint. Wie du siehst, hat diese also (wahrscheinlich aus genau dem Grund mit der Länge) lineare Laufzeit.

Ah, stimmt, so war das. Der Standard verlangt weder, dass std::list::splice() noch dass std::list::length() in konstanter Zeit laufen, er empfiehlt wohl nur, dass std::list::length besser in konstanter Zeit laufen sollte ("should", nicht "must").
Die Implementierungen haben also die Wahl, eine dieser beiden Funktionen in Konstantzeit zu implementieren. Die andere wird zwangsläufig langsamer laufen. Manche Implementierungen lassen std::list::length in Konstantzeit laufen, andere std::list::splice.

Nexus

Möglich wäre ja auch ein Kompromiss, sodass sowohl size() als auch splice() in den meisten Fällen eine Laufzeit von O(1) haben. Nämlich, indem die gespeicherte Grösse bei splice() ungültig gemacht und bei Aufruf von size() neu berechnet wird. Aber das dafür notwendige if lohnt sich wahrscheinlich nicht.