webentwicklung-frage-antwort-db.com.de

Effiziente verknüpfte Liste in C ++?

Dies Dokument sagt std::list ist ineffizient:

std :: list ist eine extrem ineffiziente Klasse, die selten nützlich ist. Es führt für jedes eingefügte Element eine Heap-Zuordnung durch und hat damit einen extrem hohen konstanten Faktor, insbesondere für kleine Datentypen.

Kommentar: Das ist zu meiner Überraschung. std::list ist eine doppelt verknüpfte Liste, daher unterstützt sie trotz ihrer Ineffizienz bei der Elementkonstruktion das Einfügen/Löschen in O(1) Zeitkomplexität, aber diese Funktion wird in diesem zitierten Absatz vollständig ignoriert.

Meine Frage: Sagen wir, ich brauche einen sequentiellen Container für kleine homogene Elemente, und dieser Container sollte Element einfügen/löschen in O (1) Komplexität und tut nicht benötigen Direktzugriff (obwohl die Unterstützung von Direktzugriff Nizza ist, ist dies hier kein Muss). Ich möchte auch nicht, dass der hohe konstante Faktor durch die Heap-Zuweisung für die Konstruktion jedes Elements eingeführt wird, zumindest wenn die Anzahl der Elemente klein ist. Schließlich sollten Iteratoren nur ungültig gemacht werden, wenn das entsprechende Element gelöscht wird. Anscheinend brauche ich eine benutzerdefinierte Containerklasse, die eine Variante einer doppelt verknüpften Liste sein kann (oder auch nicht). Wie soll ich diesen Container gestalten?

Wenn die oben genannte Spezifikation nicht erreicht werden kann, sollte ich möglicherweise einen benutzerdefinierten Speicherzuordner haben, z. B. einen Stoßzeigerzuordner? Ich kenne std::list verwendet einen Allokator als zweites Vorlagenargument.

Bearbeiten: Ich weiß, ich sollte mich nicht zu sehr mit diesem Thema befassen, aus technischer Sicht - schnell genug ist gut genug. Es ist nur eine hypothetische Frage , daher habe ich keinen detaillierteren Anwendungsfall. Fühlen Sie sich frei, um einige der Anforderungen zu entspannen!

Edit2: Ich verstehe zwei Algorithmen von [~ # ~] o [~ # ~] (1) Komplexität kann aufgrund der Unterschiede in ihren konstanten Faktoren eine völlig unterschiedliche Leistung haben.

42
Leedehai

Am einfachsten sehe ich alle Ihre Anforderungen zu erfüllen:

  1. Einfügen/Entfernen mit konstanter Zeit (hoffentlich amortisierte konstante Zeit ist für das Einfügen in Ordnung).
  2. Keine Heapzuweisung/Freigabe pro Element.
  3. Keine Iterator-Invalidierung beim Entfernen.

... wäre so etwas, wenn Sie nur std::vector verwenden würden:

template <class T>
struct Node
{
    // Stores the memory for an instance of 'T'.
    // Use placement new to construct the object and
    // manually invoke its dtor as necessary.
    typename std::aligned_storage<sizeof(T), alignof(T)>::type element;

    // Points to the next element or the next free
    // element if this node has been removed.
    int next;

    // Points to the previous element.
    int prev;
};

template <class T>
class NodeIterator
{
public:
    ...
private:
    std::vector<Node<T>>* nodes;
    int index;
};

template <class T>
class Nodes
{
public:
    ...
private:
    // Stores all the nodes.
    std::vector<Node> nodes;

    // Points to the first free node or -1 if the free list
    // is empty. Initially this starts out as -1.
    int free_head;
};

... und hoffentlich mit einem besseren Namen als Nodes (Ich bin ein bisschen beschwipst und nicht so gut darin, mir gerade Namen auszudenken). Ich überlasse die Implementierung Ihnen, aber das ist die allgemeine Idee. Wenn Sie ein Element entfernen, entfernen Sie einfach eine doppelt verknüpfte Liste mithilfe der Indizes und schieben Sie sie an den freien Kopf. Der Iterator macht nicht ungültig, da er einen Index zu einem Vektor speichert. Prüfen Sie beim Einsetzen, ob der freie Kopf -1 beträgt. Wenn nicht, überschreiben Sie den Knoten an dieser Position und platzieren Sie ihn. Ansonsten Push_back Zum Vektor.

Illustration

Diagramm (Knoten werden zusammenhängend in std::vector Gespeichert. Wir verwenden einfach Indexverknüpfungen, um das verzweigungslose Überspringen von Elementen sowie zeitlich konstante Entfernungen und Einfügungen an beliebiger Stelle zu ermöglichen.):

enter image description here

Angenommen, wir möchten einen Knoten entfernen. Dies ist Ihre standardmäßige Entfernung von doppelt verknüpften Listen, außer dass wir Indizes anstelle von Zeigern verwenden und Sie den Knoten auch auf die freie Liste verschieben (was nur das Manipulieren von ganzen Zahlen beinhaltet):

Entfernungsanpassung von Links:

enter image description here

Entfernten Knoten in freie Liste verschieben:

enter image description here

Nehmen wir nun an, Sie fügen in diese Liste ein. In diesem Fall entfernen Sie den freien Kopf und überschreiben den Knoten an dieser Position.

Nach dem Einfügen:

enter image description here

Das zeitlich konstante Einfügen in die Mitte sollte ebenfalls leicht zu verstehen sein. Grundsätzlich fügen Sie einfach den freien Kopf oder Push_back In den Vektor ein, wenn der freie Stapel leer ist. Anschließend führen Sie die Standardeinfügung für doppelt verknüpfte Listen aus. Logik für die kostenlose Liste (obwohl ich dieses Diagramm für eine andere Person erstellt habe und es sich um eine SLL handelt, aber Sie sollten die Idee haben):

enter image description here

Stellen Sie sicher, dass Sie die Elemente ordnungsgemäß konstruieren und zerstören, indem Sie beim Einfügen/Entfernen neue und manuelle Aufrufe an das dtor senden. Wenn Sie es wirklich verallgemeinern möchten, müssen Sie auch über die Ausnahmesicherheit nachdenken, und wir benötigen auch einen schreibgeschützten Constituerator.

Vor- und Nachteile

Der Vorteil einer solchen Struktur besteht darin, dass sie sehr schnelle Einfügungen/Entfernungen von einer beliebigen Stelle in der Liste ermöglicht (selbst bei einer riesigen Liste), die Einfügungsreihenfolge beim Durchlaufen beibehalten und die Iteratoren für Elemente, die nicht direkt entfernt werden, niemals ungültig macht (obwohl es Zeiger auf sie ungültig macht; verwenden Sie deque, wenn Sie nicht möchten, dass Zeiger ungültig werden). Persönlich würde ich mehr Verwendung dafür finden als std::list (Was ich praktisch nie benutze).

Bei ausreichend großen Listen (z. B. größer als Ihr gesamter L3-Cache, wenn Sie auf jeden Fall mit einem riesigen Rand rechnen sollten) sollte dieser Wert beim Entfernen und Einfügen von/von der Mitte und von vorne deutlich über std::vector Liegen. Das Entfernen von Elementen aus einem Vektor kann für kleine sehr schnell gehen. Versuchen Sie jedoch, eine Million Elemente aus einem Vektor zu entfernen, indem Sie von vorne nach hinten arbeiten. Dort kriechen die Dinge, während dieser im Handumdrehen zu Ende geht. std::vector Ist IMO immer ein wenig überzeichnet, wenn Leute damit beginnen, mit der Methode erase Elemente aus der Mitte eines Vektors zu entfernen, der 10k oder mehr Elemente umfasst Auf eine Weise, bei der jeder Knoten einzeln einem Allokator für allgemeine Zwecke zugewiesen wird, während Cache-Fehler in Hülle und Fülle verursacht werden.

Der Nachteil ist, dass nur der sequenzielle Zugriff unterstützt wird und der Overhead von zwei Ganzzahlen pro Element erforderlich ist. Wie Sie im obigen Diagramm sehen können, verschlechtert sich die räumliche Lokalität, wenn Sie ständig sporadisch Objekte entfernen.

Verschlechterung der räumlichen Lokalität

Der Verlust der räumlichen Lokalität, wenn Sie anfangen, viel von der Mitte zu entfernen und in die Mitte einzufügen, führt zu zickzackförmigen Speicherzugriffsmustern, die möglicherweise Daten aus einer Cache-Zeile entfernen, um sie während einer einzelnen sequenziellen Schleife zurückzuspeichern und neu zu laden. Dies ist im Allgemeinen bei jeder Datenstruktur unvermeidlich, die das Entfernen von Daten aus der Mitte in konstanter Zeit ermöglicht und gleichzeitig die Rückgewinnung dieses Speicherplatzes unter Beibehaltung der Reihenfolge des Einfügens ermöglicht. Sie können jedoch die räumliche Lokalität wiederherstellen, indem Sie eine Methode anbieten, oder Sie können die Liste kopieren/austauschen. Der Kopierkonstruktor kann die Liste so kopieren, dass sie die Quellliste durchläuft und alle Elemente einfügt, wodurch Sie einen perfekt zusammenhängenden, cachefreundlichen Vektor ohne Lücken erhalten (dies macht jedoch Iteratoren ungültig).

Alternative: Freie Listenzuordnung

Eine Alternative, die Ihren Anforderungen entspricht, ist die Implementierung einer kostenlosen Liste gemäß std::allocator Und deren Verwendung mit std::list. Ich mochte es jedoch nie, in Datenstrukturen herumzugreifen und mit benutzerdefinierten Zuweisern herumzuspielen, und dass man die Speicherbelegung der Links auf 64-Bit durch die Verwendung von Zeigern anstelle von 32-Bit-Indizes verdoppeln würde, daher würde ich die obige Lösung persönlich vorziehen, indem ich std::vector Ist im Grunde Ihr analoger Speicherzuweiser und Index anstelle von Zeigern (die sowohl die Größe reduzieren als auch eine Anforderung werden, wenn wir std::vector Verwenden, da Zeiger ungültig werden, wenn der Vektor eine neue Kapazität reserviert).

Indizierte verknüpfte Listen

Ich nenne diese Art von Dingen eine "indizierte verknüpfte Liste", da die verknüpfte Liste nicht wirklich ein Container ist, sondern vielmehr eine Möglichkeit zum Verknüpfen von Dingen, die bereits in einem Array gespeichert sind. Und ich finde diese indizierten verknüpften Listen exponentiell nützlicher, da Sie nicht knietief in den Speicherpools arbeiten müssen, um Heap-Zuweisungen/Freigabezuweisungen pro Knoten zu vermeiden. Dinge hier und da verarbeiten, um die räumliche Lokalität wiederherzustellen).

Sie können dies auch einfach verknüpfen, indem Sie dem Knoten-Iterator eine weitere Ganzzahl hinzufügen, um den vorherigen Knotenindex zu speichern. (Bei 64-Bit-Versionen wird keine Speichergebühr erhoben, vorausgesetzt, 32-Bit-Ausrichtungsanforderungen für int und 64-Bit-Versionen für Zeiger.) Sie verlieren jedoch die Möglichkeit, einen umgekehrten Iterator hinzuzufügen und alle Iteratoren bidirektional zu machen.

Benchmark

Ich habe eine schnelle Version des oben Genannten erstellt, da Sie an 'em: release build, MSVC 2012, keinen überprüften Iteratoren oder Ähnlichem interessiert zu sein scheinen:

--------------------------------------------
- test_vector_linked
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000015 secs}

Erasing half the list...
time passed for 'erasing': {0.000021 secs}
time passed for 'iterating': {0.000002 secs}
time passed for 'copying': {0.000003 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector_linked: {0.062000 secs}
--------------------------------------------
- test_vector
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000012 secs}

Erasing half the vector...
time passed for 'erasing': {5.320000 secs}
time passed for 'iterating': {0.000000 secs}   
time passed for 'copying': {0.000000 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector: {5.320000 secs}

War zu faul, um einen hochpräzisen Timer zu verwenden, aber hoffentlich gibt dies eine Vorstellung davon, warum man die Methode vector's Linearer Zeit erase in kritischen Pfaden für nicht triviale Eingabegrößen nicht verwenden sollte, wobei vector über ~ 86 liegt mal länger (und exponentiell schlimmer, je größer die Eingabegröße - ich habe es ursprünglich mit 2 Millionen Elementen versucht, aber nach fast 10 Minuten Wartezeit aufgegeben) und warum vector meiner Meinung nach für diese Art der Verwendung etwas überzeichnet ist. Das heißt, wir können das Entfernen aus der Mitte in eine sehr schnelle Operation mit konstanter Zeit umwandeln, ohne die Reihenfolge der Elemente zu ändern, ohne die Indizes und Iteratoren zu ungültig zu machen, die sie speichern, und während wir weiterhin vector verwenden ... Alles, was wir tun müssen, ist einfach make Es speichert einen verknüpften Knoten mit prev/next - Indizes, um das Überspringen entfernter Elemente zu ermöglichen.

Zum Entfernen habe ich einen zufällig gemischten Quellvektor mit geraden Indizes verwendet, um zu bestimmen, welche Elemente in welcher Reihenfolge entfernt werden müssen. Das ahmt einen realen Anwendungsfall nach, in dem Sie aus der Mitte dieser Container mithilfe von zuvor erhaltenen Indizes/Iteratoren entfernen, beispielsweise die Elemente, die der Benutzer zuvor mit einem Auswahlrechteck ausgewählt hat, nachdem er die Schaltfläche Löschen (und erneut Sie) gedrückt hat Sollte für diese nicht-triviale Größe wirklich kein Skalar vector::erase verwenden, es wäre sogar besser, eine Reihe von Indizes zu erstellen, um remove_if zu entfernen und zu verwenden - immer noch besser als vector::erase Hat jeweils einen Iterator aufgerufen).

Beachten Sie, dass die Iteration bei den verknüpften Knoten etwas langsamer wird und dass dies weniger mit der Iterationslogik zu tun hat als mit der Tatsache, dass jeder Eintrag im Vektor mit den hinzugefügten Links größer ist (mehr Speicher für die sequenzielle Verarbeitung entspricht mehr Cache) Fehlschläge und Seitenfehler). Wenn Sie jedoch beispielsweise Elemente aus sehr großen Eingaben entfernen, ist die Leistungsverschiebung für große Container zwischen linearer und zeitlich konstanter Entfernung so episch, dass dies in der Regel ein lohnender Austausch ist.

1
Dragon Energy

Ihre Anforderungen sind gena die von std::list, außer dass Sie entschieden haben, dass Sie den Overhead der knotenbasierten Zuweisung nicht mögen.

Der vernünftige Ansatz ist, oben anzufangen und nur so viel zu tun, wie Sie wirklich brauchen:

  1. Benutz einfach std::list.

    Benchmark it: Ist der Standard-Allokator für Ihre Zwecke wirklich zu langsam?

    • Nein, du bist fertig.

    • Ja, gehe zu 2

  2. Verwenden std::list mit einem vorhandenen benutzerdefinierten Allokator, z. B. dem Boost-Pool-Allokator

    Benchmark: Ist der Boost-Pool-Allokator für Ihre Zwecke wirklich zu langsam?

    • Nein, du bist fertig.

    • Ja, gehe zu 3

  3. Verwenden std::list mit einem von Hand gerollten benutzerdefinierten Allokator, der genau auf Ihre individuellen Anforderungen abgestimmt ist und auf allen Profilen basiert, die Sie in den Schritten 1 und 2 erstellt haben

    Benchmark wie bisher etc. etc.

  4. Betrachten Sie als letzten Ausweg etwas Exotischeres.

    Wenn Sie zu diesem Zeitpunkt gelangen, sollten Sie eine wirklich genau spezifizierte SO) - Frage haben, mit vielen Details darüber, was Sie genau benötigen (z. B. "Ich muss") quetschen Sie n Knoten in eine Cacheline "anstatt" dieses Dokument sagte, das Ding ist langsam und das klingt schlecht ").


PS. Das Obige macht zwei Annahmen, aber beide sind eine Untersuchung wert:

  1. wie Baum mit Augen betont, ist es nicht ausreichend, ein einfaches Ende-zu-Ende-Timing durchzuführen, da Sie sicher sein müssen, wohin Ihre Zeit geht. Es kann sich um den Allokator selbst oder um Cache-Ausfälle aufgrund des Speicherlayouts handeln. Wenn etwas langsam ist, müssen Sie immer noch sicher sein warum, bevor Sie wissen, was sich ändern sollte.
  2. ihre Anforderungen werden als gegeben vorausgesetzt, aber Wege zu finden, um Anforderungen zu schwächen, ist oft der einfachste Weg, etwas schneller zu machen.

    • müssen Sie wirklich überall oder nur vorne oder hinten oder beides, aber nicht in der Mitte, in konstanter Zeit einfügen und löschen?
    • benötigen Sie diese Einschränkungen für die Iterator-Invalidierung wirklich oder können sie gelockert werden?
    • gibt es Zugriffsmuster, die Sie ausnutzen können? Wenn Sie häufig ein Element von der Vorderseite entfernen und es dann durch ein neues ersetzen, können Sie es dann einfach direkt aktualisieren?
87
Useless

Alternativ können Sie ein erweiterbares Array verwenden und die Links explizit als Indizes im Array behandeln.

Nicht verwendete Array-Elemente werden über einen der Links in eine verknüpfte Liste eingefügt. Wenn ein Element gelöscht wird, wird es in die freie Liste zurückgeführt. Wenn die freie Liste erschöpft ist, vergrößern Sie das Array und verwenden Sie das nächste Element.

Für die neuen freien Elemente haben Sie zwei Möglichkeiten:

  • füge sie sofort der freien Liste hinzu,
  • fügen Sie sie bei Bedarf hinzu, basierend auf der Anzahl der Elemente in der freien Liste im Vergleich zur Array-Größe.
18
Yves Daoust

Das Erfordernis, Iteratoren mit Ausnahme der auf einem zu löschenden Knoten nicht ungültig zu machen, verbietet es jedem Container, der keine einzelnen Knoten zuweist und sich stark von z. list oder map.
Ich habe jedoch festgestellt, dass dies in fast allen Fällen, in denen ich dachte notwendig war, mit ein wenig Disziplin gelangte, auf die ich genauso gut verzichten konnte. Vielleicht möchten Sie überprüfen, ob Sie können, Sie würden stark profitieren.

Während std::list In der Tat das "richtige" ist, wenn Sie so etwas wie eine Liste benötigen (meistens für CS-Klassen), ist die Aussage, dass es fast immer die falsche Wahl ist, leider genau richtig. Die Behauptung O(1) ist zwar völlig wahr, aber in Bezug auf die tatsächliche Funktionsweise der Computerhardware ist sie dennoch miserabel, was einen riesigen konstanten Faktor darstellt. Beachten Sie, dass Sie nicht nur die Objekte iterieren zufällig platziert, aber die Knoten, die Sie pflegen, sind es auch (ja, Sie können das irgendwie mit einem Allokator umgehen, aber das ist nicht der Punkt.) Im Durchschnitt haben Sie zwei ein garantierter Cache-Miss für alles, was Sie tun, plus bis zu zwei eine dynamische Zuordnung für mutierende Operationen (eine für das Objekt und eine andere für den Knoten).

Edit: Wie von @ratchetfreak unten hervorgehoben, reduzieren Implementierungen von std::list Üblicherweise die Objekt- und Knotenzuordnung in einem Speicherblock als Optimierung (ähnlich wie z. B. make_shared does), was den Durchschnittsfall etwas weniger katastrophal macht ( eine Zuordnung pro Mutation und einen garantierten Cache-Miss anstelle von zwei).
Eine neue, andere Überlegung in diesem Fall könnte sein, dass dies möglicherweise auch nicht völlig problemlos ist. Das Nachfixieren des Objekts mit zwei Zeigern bedeutet das Umkehren der Richtung während der Dereferenzierung, was den automatischen Prefetch beeinträchtigen kann.
Das Präfixieren des Objekts mit den Zeigern bedeutet andererseits, dass Sie das Objekt um zwei Zeiger zurückschieben, was bis zu 16 Byte auf einem 64-Bit-System bedeutet (das eine Mitte aufteilen könnte). Objektgröße jedes Mal über Cache-Zeilengrenzen Es ist auch zu berücksichtigen, dass std::list Es sich nicht leisten kann, z.B. SSE Code nur, weil er einen geheimen Versatz als besondere Überraschung hinzufügt (so wäre zum Beispiel der xor-Trick wahrscheinlich nicht anwendbar, um den Fußabdruck mit zwei Zeigern zu verringern.) Es müsste wahrscheinlich einige geben Umfang des "sicheren" Auffüllens, um sicherzustellen, dass Objekte, die zu einer Liste hinzugefügt wurden, weiterhin so funktionieren, wie sie sollten.
Ich kann nicht sagen, ob es sich um tatsächliche Leistungsprobleme oder nur um Misstrauen und Angst von meiner Seite handelt, aber ich glaube, es ist fair zu sagen, dass sich möglicherweise mehr Schlangen im Gras verstecken, als man erwartet.

Nicht umsonst empfehlen namhafte C++ - Experten (insbesondere Stroustrup) die Verwendung von std::vector, Es sei denn, Sie haben einen guten Grund, dies nicht zu tun.

Wie viele Leute zuvor habe ich versucht, etwas Besseres als std::vector Für das eine oder andere spezielle Problem zu verwenden (oder zu erfinden), bei dem es den Anschein hat, dass Sie es besser können, aber es stellt sich einfach heraus Die Verwendung von std::vector ist nach wie vor fast immer die beste oder zweitbeste Option (wenn std::vector zufällig nicht die beste Option ist, ist std::deque in der Regel die richtige Option).
Sie haben viel weniger Zuweisungen als bei jedem anderen Ansatz, viel weniger Speicherfragmentierung, viel weniger Indirektionen und ein viel günstigeres Speicherzugriffsmuster. Und raten Sie mal, es ist leicht verfügbar und funktioniert einfach.
Die Tatsache, dass hin und wieder Beilagen eine Kopie aller Elemente erfordern, ist (in der Regel) kein Problem. Sie denken es ist, aber es ist nicht. Es kommt selten vor und ist eine Kopie eines linearen Speicherblocks, in dem Prozessoren genau gut sind (im Gegensatz zu vielen doppelten Indirektionen und zufälligen Sprüngen über den Speicher).

Wenn die Anforderung, Iteratoren nicht ungültig zu machen, wirklich ein absolutes Muss ist, können Sie beispielsweise ein std::vector - Objekt mit einem dynamischen Bitset oder mangels besserer Eigenschaften ein std::vector<bool> - Objekt koppeln. Verwenden Sie dann reserve() entsprechend, damit keine Neuzuordnungen erfolgen. Wenn Sie ein Element löschen, entfernen Sie es nicht, sondern markieren Sie es nur als gelöscht in der Bitmap (rufen Sie den Destruktor manuell auf). Rufen Sie zu geeigneten Zeitpunkten, zu denen Sie wissen, dass das Ungültigmachen von Iteratoren in Ordnung ist, eine "Staubsauger" -Funktion auf, die sowohl den Bitvektor als auch den Objektvektor komprimiert. Dort sind alle unvorhersehbaren Iterator-Invalidierungen verschwunden.

Ja, das erfordert die Beibehaltung eines zusätzlichen "Element wurde gelöscht" -Bits, was ärgerlich ist. Aber ein std::list Muss zusätzlich zum eigentlichen Objekt auch zwei Zeiger pflegen und Zuordnungen vornehmen. Mit dem Vektor (oder zwei Vektoren) ist der Zugriff immer noch sehr effizient, da er cachefreundlich abläuft. Selbst wenn Sie nach gelöschten Knoten suchen, bedeutet dies, dass Sie sich linear oder nahezu linear über den Speicher bewegen.

18
Damon

std::list ist eine doppelt verknüpfte Liste, daher unterstützt sie trotz ihrer Ineffizienz bei der Elementkonstruktion Einfügen/Löschen in O(1) Zeitkomplexität, aber diese Funktion ist vollständig in diesem zitierten Absatz ignoriert.

Es wird ignoriert weil es eine Lüge ist.

Das Problem der algorithmischen Komplexität besteht darin, dass sie im Allgemeinen eine Sache misst . Wenn wir zum Beispiel sagen, dass das Einfügen in ein std::map ist O (log N), wir meinen, dass es O (log N) Vergleiche durchführt. Die Kosten für das Iterieren , Abrufen von Cache-Zeilen aus dem Speicher usw. werden nicht berücksichtigt.

Dies vereinfacht natürlich die Analyse erheblich, lässt sich aber leider nicht unbedingt sauber auf die Komplexität der Implementierung in der Praxis abbilden. Insbesondere ist eine ungeheure Annahme , dass die Speicherzuweisung zeitlich konstant ist . Und das ist eine kühne Lüge.

Allzweck-Speicherzuordnungen (malloc und co) können keine Garantie für die Komplexität der Speicherzuordnungen im ungünstigsten Fall übernehmen. Der schlimmste Fall ist in der Regel vom Betriebssystem abhängig, und im Falle von Linux kann es sich um den OOM-Killer handeln.

Speicherzuordnungen für spezielle Zwecke könnten möglicherweise eine konstante Zeit haben ... innerhalb eines bestimmten Bereichs der Anzahl von Zuordnungen (oder der maximalen Zuordnungsgröße). Da es sich bei der Big-O-Notation um die Grenze im Unendlichen handelt, kann sie nicht als O (1) bezeichnet werden.

Und so, wo der Gummi auf die Straße trifft , die Umsetzung von std::list bietet im Allgemeinen NICHT O(1) Einfügen/Löschen, da die Implementierung auf einem realen Speicherzuweiser beruht, nicht auf einem idealen.


Das ist ziemlich deprimierend, aber Sie müssen nicht alle Hoffnungen verlieren.

Vor allem, wenn Sie eine Obergrenze für die Anzahl der Elemente herausfinden und so viel Speicherplatz im Voraus zuweisen können, können Sie a erstellen Speicherzuordnung, die eine zeitlich konstante Speicherzuordnung durchführt und Ihnen die Illusion von O (1) gibt.

16
Matthieu M.

Verwenden Sie zwei std::lists: Eine "freie Liste", die beim Start mit einem großen Vorrat an Knoten vorbelegt ist, und die andere "aktive" Liste, in die Sie splice Knoten aus der freien Liste einfügen. Dies ist eine konstante Zeit und erfordert keine Zuweisung eines Knotens.

7
Mark B

Der neue slot_map Antragsanspruch O(1) zum Einfügen und Löschen.

Es gibt auch einen Link zu einem Video mit einer vorgeschlagenen Implementierung und einigen früheren Arbeiten.

Wenn wir mehr über die tatsächliche Struktur der Elemente wüssten, könnte es einige spezielle assoziative Container geben, die viel besser sind.

5
Surt

Ich würde vorschlagen, genau das zu tun, was @ Yves Daoust sagt. Verwenden Sie jedoch einen Vektor, anstatt eine verknüpfte Liste für die kostenlose Liste zu verwenden. Schieben und platzieren Sie die freien Indizes auf der Rückseite des Vektors. Dies wird amortisiert O(1) Einfügen, Nachschlagen und Löschen, erfordert keine Zeigerjagd und erfordert auch kein nerviges Allokatorgeschäft.

4
Dan

Ich wollte nur einen kleinen Kommentar zu Ihrer Wahl abgeben. Ich bin ein großer Fan von Vektoren, weil sie eine hohe Lesegeschwindigkeit haben. Sie können auf jedes Element direkt zugreifen und bei Bedarf sortieren. (Vektor der Klasse/Struktur zum Beispiel).

Aber wie auch immer, ich schweife ab, es gibt zwei raffinierte Tipps, die ich offenlegen wollte. Bei Vektoren können Einfügungen teuer sein, also ein ordentlicher Trick. Fügen Sie keine ein, wenn Sie damit durchkommen können. Führe einen normalen Push_back durch (am Ende setzen) und tausche dann das Element mit dem gewünschten aus.

Dasselbe gilt für Löschvorgänge. Die sind teuer. Also tausche es mit dem letzten Element aus, lösche es.

2
ViperG

Ich antworte @Useless, insbesondere PS Punkt 2 über die Überarbeitung der Anforderungen. Wenn Sie die Einschränkung der Iterator-Invalidierung aufheben, verwenden Sie std::vector<> ist Standardvorschlag von Stroustrup für einen Container mit geringer Stückzahl (aus Gründen, die bereits in den Kommentaren erwähnt wurden). VerwandteFragen zu SO.

Ab C++ 11 gibt es auch std::forward_list.

Auch wenn die Standard-Heap-Zuordnung für dem Container hinzugefügte Elemente nicht ausreicht, sollten Sie sehr sorgfältig Ihre genauen Anforderungen und Feineinstellung für sie.

2
Pablo H

Danke für alle Antworten. Dies ist ein einfacher - wenn auch nicht strenger - Maßstab.

// list.cc
#include <list>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        list<size_t> ln;
        for (size_t i = 0; i < 200; i++) {
            ln.insert(ln.begin(), i);
            if (i != 0 && i % 20 == 0) {
                ln.erase(++++++++++ln.begin());
            }
        }
    }
}

und

// vector.cc
#include <vector>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        vector<size_t> vn;
        for (size_t i = 0; i < 200; i++) {
            vn.insert(vn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                vn.erase(++++++++++vn.begin());
            }
        }
    }
}

Dieser Test zielt darauf ab zu testen, was std::list Gegenüber Excel behauptet: - [~ # ~] o [~ # ~] (1) Einfügen und Löschen. Und wegen der Positionen, die ich einfügen/löschen möchte, ist dieses Rennen stark gegen std::vector Verzerrt, weil es alle folgenden Elemente verschieben muss (daher [~ # ~] o [~ # ~] (n)), während std::list das nicht tun muss.

Jetzt kompiliere ich sie.

clang++ list.cc -o list
clang++ vector.cc -o vector

Und testen Sie die Laufzeit. Das Ergebnis ist:

  time ./list
  ./list  4.01s user 0.05s system 91% cpu 4.455 total
  time ./vector
  ./vector  1.93s user 0.04s system 78% cpu 2.506 total

std::vector Hat gewonnen.

Mit der Optimierung O3 Kompiliert, gewinnt std::vector Immer noch.

  time ./list
  ./list  2.36s user 0.01s system 91% cpu 2.598 total
  time ./vector
  ./vector  0.58s user 0.00s system 50% cpu 1.168 total

std::list Muss die Heap-Zuordnung für jedes Elements aufrufen, während std::vector Den Heap-Speicher im Batch zuordnen kann (obwohl dies möglich ist) Implementierungsabhängig sein), daher hat das Einfügen/Löschen von std::list einen höheren konstanten Faktor, obwohl es [~ # ~] o [~ # ~] (1) .

Kein Wunder, dass dieses Dokument sagt

std::vector Wird sehr geliebt und respektiert.

[~ # ~] edit [~ # ~]: std::deque funktioniert in einigen Fällen sogar noch besser , zumindest für diese Aufgabe .

// deque.cc
#include <deque>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        deque<size_t> dn;
        for (size_t i = 0; i < 200; i++) {
            dn.insert(dn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                dn.erase(++++++++++dn.begin());
            }
        }
    }
}

Ohne Optimierung:

./deque  2.13s user 0.01s system 86% cpu 2.470 total

Optimiert mit O3:

./deque  0.27s user 0.00s system 50% cpu 0.551 total
1
Leedehai