STL Container: Ab wann ist die Aussage "große Menge an Elementen" gerechtfertigt?
-
Huhu,
mich interessiert, ab wann es gerechtfertigt ist zu sage: Mein STL Container beinhaltet viele Elemente.
Ich habe mal ein Video von Bjarne Stroustrup gesehen, in dem er gesagt hat, 10000 Elemente in einemstd::vectorseien wenig.Damit hängt ja dann auch die Frage zusammen, ab wann ein Assoziative Container bemerkbar schneller ist, als der Defaultcontainer
std::vector?Danke euch
-
Das hängt würde ich sagen von der Größe ab. Wenn du nur Skalare Datentypen in deinem Container hälst, dann sind 10000 Elemente nicht viel. Wenn du dagegen andere, evt. große Klassen (mit vielen Membervariablen) darin hälst, dann ist es was anderes. Kommt immer auf die Situation an, wie effizient man gezwungen ist zu programmieren...
-
Das kommt darauf an, was man mit dem Container macht :p .
Deine Frage ist zu allgemein, daher ist so eine allgemeine Antwort wie "viele" oder "groß" das einzige, was man dir geben kann.
Du ungefähr abschätzen, wie groß die Datenmenge im Container so ist und dann vergleichen mit dem, was dein Computer sonst so macht. Hier kommen immer wieder Leute an, die 1000 Integer (also ein paar kB) für eine so große Menge halten, dass sie spezielle Algorithmen zur Verarbeitung brauchen. Dabei ist das eine Scherzmenge für einen heutigen Computer (oder jeden Computer der letzten 40 Jahre), die kleinsten Arbeitseinheiten sind normalerweise schon größer.
Du kannst auch über die Komplexität abschätzen, wie lange eine Aktion braucht. Bei vector und anderen Sequenzcontainern geht vieles mit O(N), bei assoziativen Containern oft mit O(log(N)), Details entnimmst du Referenzen. Dafür sind die Grundkonstanten bei den assoziativen Containern oftmals viel größer, so dass sie erst ab einer gewissen Füllmenge effektiver werden (Orientierunghilfe: ein paar Dutzend bis ein paar Hundert, aber wieder sehr stark abhängig davon was man überhaupt macht).
Also Erfahrungswerte:
1. An Algorithmus angepasste Container benutzen statt einfach vector: Ab 10-100 Elementen.
2. Den Algorithmus selbst an große Datenmengen anpassen: Wenn du mehr als 5-10 % des Hauptspeichers mit einer Datenstruktur belegst. Derzeit also ab ein paar hundert MB Daten.
-
SeppJ schrieb:
Derzeit also ab ein paar hundert MB Daten.
Dafür müsste man auf meinem Lappi bei einem
std::vector<int>ja bei ca. 100 Millionen Elementen sein, das ist - ganz ohne Übertreibung - eine Wahnsinnsmenge :d
-
Hacker schrieb:
Dafür müsste man auf meinem Lappi bei einem
std::vector<int>ja bei ca. 100 Millionen Elementen sein, das ist - ganz ohne Übertreibung - eine Wahnsinnsmenge :dNö. Eine große Menge
.Eine Wahnisnnsmenge wäre etwas, wofür man Spezialrechner braucht. Zum Beispiel kannte ich jemanden der numerische Rechnungen auf einem Rechner mit 64 GB Arbeitsspeicher machte, als 1 GB Hauptspeicher noch als dickes Verkaufsargument beim Mediamarkt galt.
-
out schrieb:
Ich habe mal ein Video von Bjarne Stroustrup gesehen, in dem er gesagt hat, 10000 Elemente in einem
std::vectorseien wenig.Ich halte die Aussage für Unsinn, weil es std::vector schlicht und ergreifend egal ist wie viel Elemente er hat. 10K sind also weder wenig noch viel "für" den vector. 10K Elemente die je 1 MB haben sind vermutlich viel, aber ganz egal davon wo man die ablegt. Und 10K Elemente die je 4 Byte haben sind halt nicht wirklich viel.
out schrieb:
Damit hängt ja dann auch die Frage zusammen, ab wann ein Assoziative Container bemerkbar schneller ist, als der Defaultcontainer
std::vector?Wenn du map und (unsortierten) vector beim "Lookup" vergleichst (normaler Lookup in der map vs. lineare Suche im vector), dann wird map schon bei relativ wenig Elementen schneller, sagen wir so 10-20.
-
hustbaer schrieb:
(normaler Lookup in der map vs. lineare Suche im vector)
Der "normale Lookup" in einem (sortierten) assoziativen Container ist eine binäre Suche. Oder?
-
Eine std::map verwendet einen Suchbaum, std::unordered_map eine Hashfunktion.
