3. Suche alternative Vector und Double-Linked-List Implementation

Suche alternative Vector und Double-Linked-List Implementation

  • ?

    Hi, kennt jemand zufällig eine gute Vector oder Double-Linked-List Implementation? Mal von der Standard Library abgesehen. Oft gibt es ja z.B. auf den Seiten von Universitäten entsprechende Implementationen. Bei meiner Suche habe ich jedoch noch nichts zufriedenstellendes gefunden. Ideal wäre es wenn die Implememtation dann auch noch schneller als die Standard Library ist.

    Gruß

    StellerFragen

    0
  • I

    Du kannst ruhigen Gewissens davon ausgehen, dass die Standardbibliotheksimplementierungen von vector und list (und auch der anderen Container) die performantesten für deine Platform sind.

    Die Implementierungen bei Universitäten dienen meist zu Lehrzwecken und sind deswegen gerade nicht optimiert (manchmal sogar fehlerhaft - z.B. sparen sich manche Unis bei verketteten Listen das Freigeben gelöschter Knoten).

    0
  • D

    ipsec schrieb:

    Du kannst ruhigen Gewissens davon ausgehen, dass die Standardbibliotheksimplementierungen von vector und list (und auch der anderen Container) die performantesten für deine Platform sind.

    Kommt drauf an für was du die brauchst. Generell sind sie sehr gut und performant, aber wenn man gewissen Einschränkungen hat kann man bestimmt Container bauen, die das besser ausnutzen.

    0
  • A

    StellerFragen schrieb:

    Ideal wäre es wenn die Implememtation dann auch noch schneller als die Standard Library ist.

    In der Regel ist eine schlechte Performance bezogen auf die Standardbibliothek weniger Problem der Bibliothek, sondern eher wie man sie verwendet. Und ja, man kann sie falsch (im Sinne der Performance) verwenden.

    Beispielsweise: Man weiß das in einem bestimmten Vektor mindestens 1000 Elemente stecken, setzt aber nicht die Kapazität, sondern nutzt nur push_back... Und da gibt es noch viele andere Fallstricke (wie z.B. die Benutzung des falschen Containers je nach Fall).

    0
  • I

    drakon schrieb:

    ipsec schrieb:

    Du kannst ruhigen Gewissens davon ausgehen, dass die Standardbibliotheksimplementierungen von vector und list (und auch der anderen Container) die performantesten für deine Platform sind.

    Kommt drauf an für was du die brauchst. Generell sind sie sehr gut und performant, aber wenn man gewissen Einschränkungen hat kann man bestimmt Container bauen, die das besser ausnutzen.

    Naja natürlich sind vector und list nicht die Allheilcontainer für alle Fälle. Aber jezt wo du es sagst: für Arrays mit relativ kleiner maximaler Elementanzahl können Stackarrays effizienter sein als dynamische Arrays. In Boost ist außerdem die Library AutoBuffer im Review-Scheduler, welche beides vereinigt: der Container dort hat ein internes Stackarray einer bestimmten Größe, wird diese überschritten, weicht er auf ein dynamisches Array aus. In jedem Fall ist der zu erwartende Geschwindigkeitsgewinn aber wahrscheinlich nicht sehr dramatisch (wenn für das Problem Arrays am geeignetsten sind).

    Der TE erfragte aber eine bessere vector - und list -Implementierung als die der Standardbibliothek, also ging ich vom allgemeinen Fall aus. Und da gilt: man nehme an, dass es diese nicht gibt.

    0
  • ?

    StellerFragen schrieb:

    Hi, kennt jemand zufällig eine gute Vector oder Double-Linked-List Implementation? Mal von der Standard Library abgesehen. Oft gibt es ja z.B. auf den Seiten von Universitäten entsprechende Implementationen. Bei meiner Suche habe ich jedoch noch nichts zufriedenstellendes gefunden. Ideal wäre es wenn die Implememtation dann auch noch schneller als die Standard Library ist.

    Gruß

    StellerFragen

    Boost Intrusive Lists. Nutze die in meinem Projekt und die sind etwas schneller als die STL-Container, weil sie keine Kopien anlegen.
    http://www.boost.org/doc/libs/1_43_0/doc/html/intrusive/

    0
  • Mod

    Der Artikel in diesem Sprachenthread erwähnt einen InlinedVector, der wohl 1-2% bringen kann:
    http://www.c-plusplus.net/forum/288349

    Scheint aber etwas Google-internes zu sein. Womöglich einfach alle Sourcen einer normalen Vectorimplementierung nicht vorcompiliert, sondern alle Bestandteile komplett zur Compilezeit verfügbar. Und/Oder eine Optimierung für kleine Vectoren, bei denen die Datenelemente insgesamt weniger als sizeof(vector<foo>) belegen.

    0
  • V

    SeppJ schrieb:

    Der Artikel in diesem Sprachenthread erwähnt einen InlinedVector, der wohl 1-2% bringen kann:
    http://www.c-plusplus.net/forum/288349

    Scheint aber etwas Google-internes zu sein. Womöglich einfach alle Sourcen einer normalen Vectorimplementierung nicht vorcompiliert, sondern alle Bestandteile komplett zur Compilezeit verfügbar. Und/Oder eine Optimierung für kleine Vectoren, bei denen die Datenelemente insgesamt weniger als sizeof(vector<foo>) belegen.

    Denke eher, es ist im Prinzip das, wovon ipsec spricht.
    http://qpid.apache.org/apis/0.7/cpp/html/a00326_source.html
    http://qpid.apache.org/apis/0.6/cpp/html/a00084.html

    0

  • Die grösste Bremse bei den Standard-Containern ist halt, dass sie dynamisch Speicher anfordern.

    Ein Vektor der Platz für ein paar Elemente "vorreserviert" hat (im Objekt selbst), vermeidet das (natürlich nur so lange man nicht mehr Elemente reinsteckt als vorreservierter Platz da ist). Das kann wesentlich mehr als 1-2% bringen.

    Dann kann man noch die Heap-Implementierung austauschen, das bringt bei MSVC auch nen deutlichen Schub. Ist aber nicht ganz einfach bzw. es gibt einige Fallstricke.

    Boost.Intrusive wurde auch schon erwähnt.

    Und bei MSVC bzw. einigen anderen Implementierungen kann man noch die "checked iterators" abdrehen, das bringt nochmal ein bisschen was.

    0
Anmelden zum Antworten