Am schnellsten Travesieren1? vector, list , etc.
-
ok gut, aber was unterscheiden eigentlich ne list vom vector? haben doch beide die gleiceh funktion oder net?
Noch was: Ist es egal wie groß die Objekte sind welceh travesiert werden?
sgen wir mal ein Objetk bestehst nur aus einem integert, oder ein Objetk bestehst aus mehren anderen Objekten?
-
die objektgröße spielt nur dann eine rolle, wenn sie kopiert werden müssen. rein lesender zugriff interessiert sich nicht für die objektgröße.
wie die stl container intern arbeiten kommt auf die implementierung an. und die ergibt sich aus der spezifikation. vector soll schnellen random access garantieren, d.h. möglichst konstanter zugriff auf beliebige elemente. daher wird vector intern wahrscheinlich als array realisiert sein. list soll schnellen sequentiellen zugriff erlauben, d.h. über alle elemente traversieren. das wird intern wahrscheinlich als verkettete liste realisiert sein. muss aber nicht
die stl container sollen für ihre hauptaufgabe die schnellstmögliche realisierung wählen. und da list genau für die von dir gewünschte aufgabe spezifiziert ist, wäre es meine erste wahl.aber erst testen wird zutage fördern, obs auch wirklich die beste ist.
und wichtig: verwende bei stl containern die iteratoren fürs traversieren. denn die sorgen für den schnellen zugriff. wenn du was eigenes strickst, unterwanderst du die ganzen tollen optimierungen.
-
thordk schrieb:
von den stl containern dürfte sich fürs vollständige traversieren ne list am besten eignen.
Hm, weil das weiterlaufen nen Speicherzugriff macht statt +1 zu rechnen? Oder weil erwartet bei jedem Zugriff ein Cache-Miss passiert, weil die Nodes wild im Speicher liegen?
Nur zum Traversieren ist ein array bzw. vector immer noch das beste. Die Liste bringt Overhead mit. Den bezahlt man nur, wenn man die anderen Features der Liste braucht: splice und insert/delete an beliebiger Stelle.
-
wenn list eine verkettete datenstruktur ist, und vector ein array, dann dürfte insert bei list wesentlich effektiver sein..
Zudem hab ich mal getestet, was schneller ist , ob ich objekte driekt in liste ablege und travestiere, oder nur die referenzen... im letzteren ist das travestieren ca. 12% langsamer.. gemessen bei 500000 objekten.
-
BorisDieKlinge schrieb:
wenn list eine verkettete datenstruktur ist, und vector ein array, dann dürfte insert bei list wesentlich effektiver sein..
Gut erkannt - jede Containerklasse hat ihre eigenen Vor- und Nachteile, darum hast du ja auch die Wahl, welche du nehmen kannst. list<> (idR als verkettete Liste realisiert) ermöglicht es dir, recht schnell irgendwo Elemente dazwischenzuschieben, dafür gibt es keinen Direktzugriff per Index (um das n-te Element zu finden, mußt du von l.begin() aus n Schritte vorwärts gehen), vector<> (idR dynamisch wachsendes Array) bietet dir die Möglichkeit, jedes Element direkt anzusprechen, aber dafür können sich Einfügevorgänge in die Länge ziehen (wenn du einen Wert irgendwo einfügen willst, mußt du erst Platz schaffen, indem alle Nachfolger umkopiert werden).
=> jetzt kommt es auf die Anforderungen deiner Anwendung an, was du verwenden willst.
PS: Es gibt übrigens noch einen dritten Kandidaten namens deque<>, den du auch in den Vergleich einbeziehen solltest
PPS: Der Unterschied zwischen Wert-Container und Zeiger-Container dürfte hauptsächlich a der zusätzlich benötigten Dereferenzierung liegen - und wenn keine ernsthaften Gründe dagegensprechen, solltest du Wert-Container verwenden.
-
hmm ok danke..
Aber mal abgesehen von der Performanceunterscheid zwischen Werte und Zeiger list was sind noch die nachteile?
und zu deque<>, wie das aufgebaut? wie ein array oder verkette datenstruktur?
-
BorisDieKlinge schrieb:
Aber mal abgesehen von der Performanceunterscheid zwischen Werte und Zeiger list was sind noch die nachteile?
Der Haupt-Nachteil (oder Vorteil, je nachdem wie du es siehst) ist wohl, daß du als Anwender die Verantwortung für die Container-Elemente übernehmen mußt (insbesondere Speicherverwaltung und Gültigkeit der Objekte).
und zu deque<>, wie das aufgebaut? wie ein array oder verkette datenstruktur?
Der Aufbau ist recht komplex, um schnelles Einfügen/Löschen am Sequenzanfang zu ermöglichen - eine häufig benutzte Variante dürfte ein zweischichtiges Array sein.
-
CStoll schrieb:
und zu deque<>, wie das aufgebaut? wie ein array oder verkette datenstruktur?
Der Aufbau ist recht komplex, um schnelles Einfügen/Löschen am Sequenzanfang zu ermöglichen - eine häufig benutzte Variante dürfte ein zweischichtiges Array sein.
Mir ist leider immernoch nicht klar, welchen Vorteil diese Implementierung vor der als Ringpuffer hat, denn einen Ringpuffer zu implementieren ist sehr einfach (und recht effizient).
thordk schrieb:
gleich danach nen array aufm heap (int *array = new int[50]). von den stl containern dürfte sich fürs vollständige traversieren ne list am besten eignen. aber wie gesagt, testen.
Hm. Wie kommst Du darauf, dass ein Heap-Array schneller traversiert werden sollte als ein STL-Vektor? Ein guter Compiler sollte da so ziemlich dasselbe draus machen.
-
Konrad Rudolph schrieb:
Wie kommst Du darauf, dass ein Heap-Array schneller traversiert werden sollte als ein STL-Vektor? Ein guter Compiler sollte da so ziemlich dasselbe draus machen.
weil der overhead so ziemlich gen null tendiert. wahrscheinlich wird der unterschied zum stl vector nicht groß oder sogar gar nicht vorhanden sein, aber es könnte. wenn man das wort "sollte" verwenden muss, kann man sich nicht sicher sein
-
Konrad Rudolph schrieb:
Mir ist leider immernoch nicht klar, welchen Vorteil diese Implementierung vor der als Ringpuffer hat, denn einen Ringpuffer zu implementieren ist sehr einfach (und recht effizient).
Der geringere Aufwand beim wachsen?