STL und Performance
-
Ich würd dafür eher den Standard empfehlen, da wohl kein Buch zu jeder Funktion in der std lib die Komplexität aufführt.
-
Hem, also in dem Buch hier wird eigentlich alles sehr gut erklärt:
http://www.springeronline.com/sgw/cda/frontpage/0,11855,1-40109-22-48185313-0,00.htmlSelbst ein kleiner Maschinencode-Abschnitt zur kompilierten STL wird besprochen, um zu beweisen, das die STL performant ist. Den "Standard" möchte ich mir da ehrlich nicht antun, da lese ich lieber dieses Buch. Habe damit auch ganz gut die STL verstanden.
-
Die STL ist performant. Ich würde jedoch nicht auf die Schiene gehen, dass sie garantiert wird.
Du kannst die dort definierten Konstrukte auch so verwenden, dass sie ein Programm zum Stillstand bringen.
Ich benutzte aktuell die Container ziemlich intensiv und baue dabei Datenstrukturen auf die in extremen Fällen an die 2 Millionen Elemete besitzen und werte diese aus. Funktioniert einwandfrei und ist für die Menge der Daten sehr performant.
-
Mathias schrieb:
Die STL ist performant. Ich würde jedoch nicht auf die Schiene gehen, dass sie garantiert wird.
Du kannst die dort definierten Konstrukte auch so verwenden, dass sie ein Programm zum Stillstand bringen.
Ich benutzte aktuell die Container ziemlich intensiv und baue dabei Datenstrukturen auf die in extremen Fällen an die 2 Millionen Elemete besitzen und werte diese aus. Funktioniert einwandfrei und ist für die Menge der Daten sehr performant.
Ich würde auf die Schiene gehen, dass die Zeitkomplexität der STL garantiert ist. Ein Einfügen eines Elemente in eine std::map wird immer O(n*log(n)) benötigen. Du weißt natürlich nicht, wie lange es tatsächlich dauert, aber darum geht es bei Zeitkomplexität gar nicht. Aber ein sortiertes Einfügen geht halt nicht schneller als n*log(n).http://www.sgi.com/tech/stl/Map.html beschreibt die Komplexitäten beispielsweise.
-
Die Aussage "Ein Einfügen eines Elemente in eine std::map wird immer O(nlog(n)) benötigen." ist so nicht richtig.
Beim Einfügevorgang werden Vergleiche durchgeführt, genauso wie Konstruktor-Aufrufe wenn die Map die Objekte enthält. Wie sich die Vergleiche als auch die Konstruktoren verhalten liegt in der Hand des STL-Anwenders. Verhalten sich diese linear gilt O(nlog(n)), ist dies nicht der Fall hast du eine schlechtere Komplexität bzw. sogar eine während der Laufzeit sich ändernde.
Was durch die STL garantiert ist, ist dass das Einfügen eines Eintrages mindestens O(n*log(n)) dauert.
Ich denke daran wird auch erkennbar warum ich nicht von einer garantierten Performance der STL sprechen will.
-
Mathias schrieb:
Die Aussage "Ein Einfügen eines Elemente in eine std::map wird immer O(nlog(n)) benötigen." ist so nicht richtig.
Beim Einfügevorgang werden Vergleiche durchgeführt, genauso wie Konstruktor-Aufrufe wenn die Map die Objekte enthält. Wie sich die Vergleiche als auch die Konstruktoren verhalten liegt in der Hand des STL-Anwenders. Verhalten sich diese linear gilt O(nlog(n)), ist dies nicht der Fall hast du eine schlechtere Komplexität bzw. sogar eine während der Laufzeit sich ändernde.
Was durch die STL garantiert ist, ist dass das Einfügen eines Eintrages mindestens O(n*log(n)) dauert.Ich denke daran wird auch erkennbar warum ich nicht von einer garantierten Performance der STL sprechen will.
Bei den Komplexitätsbetrachtungen wird die Anzahl der Vergleiche herangezogen.
Diese Anzahl kann der Designer der STL durchaus bestimmen. Wie "teuer" jeder
Vergleich selbst ist, ist natürlich nicht global bekannt sondern hängt vom
"Hersteller" der Vergleichfunktion ab. Aus diesem Grund fliesst dieser Faktor
nicht mit ein.
Die Garantien die von den Designern der STL vorgegeben sind daher sowohl
sinnvoll als auch "richtig", wenn man weiss wie diese Garantien enstanden
und zu beurteilen sind.
-
@Mathias
Lies doch bitte einfach mal nach was garantiert wird. Die Komplexitätsaussagen beziehen sich auf die Anzahl der Operationen die der *Container* auf den beinhaltete Elementen aufruft. Wenn map::insert also O(log n) (und nicht n*logn wie hier fälschlicherweise behauptet wurde) als obere Schranke garantiert, dann heißt dass, das die Anzahl der Aufrufe des Comparator-Objekts logarithmisch in der Anzahl der enthaltenen Elemente beschränkt ist.
Das hat überhaupt absolut nichts mit der Komplexität des Comparator-Objekts zu tun. Es ist unabhängig davon. Wenn dein Comparator-Objekt selbst quadratisch ist, dann ist Einfügen in einem Map aus sicht der Map immer noch logarithmisch.Was durch die STL garantiert ist, ist dass das Einfügen eines Eintrages mindestens O(n*log(n)) dauert
Nein. Die STL garantiert dir für das Einfügen in eine Map eine allgemeine Komplexität von O(log n) und amortized O(1) im Fall, dass du an die passende Position einfügst.
Davon abgesehen ist hier auch ein Denkfehler. Es wird keine "Dauer" garantiert. Es werden obere Schranken für die Anzahl der aufgerufenen Operationen relativ zu der Zahl der gespeicherten Elemente festgelegt.
Die Komplexität-Garantien der STL sind kein Benchmark-Tool.Ich denke daran wird auch erkennbar warum ich nicht von einer garantierten Performance der STL sprechen will.
Ich glaube erkennbar wird daran nur, dass du nicht wirklich weißt, was garantiert wird und wie diese Garantien zu interpretieren sind.
-
@Redhead
Sorry war zwischendurch abgelenkt und habe vergessen zu aktualisieren
-
> Bei den Komplexitätsbetrachtungen wird die Anzahl der Vergleiche
> herangezogen. Diese Anzahl kann der Designer der STL durchaus bestimmen.
Hab ich was anderes geschrieben?
Ich habe nur etwas zum Verhalten der Funktion gesagt, die den Vergleich durchführt nicht zu der Anzahl wie oft diese von der Map aufgerufen wird.> Wie "teuer" jeder Vergleich selbst ist, ist natürlich nicht global bekannt >> sondern hängt vom "Hersteller" der Vergleichfunktion ab. Aus diesem Grund
> fliesst dieser Faktor nicht mit ein.
Genau darauf wollte ich ja hinaus.> Die Garantien die von den Designern der STL vorgegeben sind daher sowohl
> sinnvoll als auch "richtig", wenn man weiss wie diese Garantien enstanden
> und zu beurteilen sind.
Habe ich behauptet dass es schlecht ist zu wissen wie sich die Funktionen der STL verhalten?
Mir ging es doch nur darum festzustellen, dass die reine Verwendung der STL nicht garantiert, dass mein Programm perfomant ist. Daher würde ich nicht von einer Performanz garantie der STL sprechen.
-
Mir ging es doch nur darum festzustellen, dass die reine Verwendung der STL nicht garantiert, dass mein Programm perfomant ist.
Natürlich nicht. Sie garantiert ja auch keinen Weltfrieden.
Nur wer ging denn hier von dieser Idee aus? Ich habe bereits in meinem ersten Beitrag geschrieben was garantiert wird. Und jeder der weiß, was die Big-O-Nation ist, weiß das daraus keine Benchmark-Aussagen gefolgert werden können (nach dem Motto: Das Einfügen dauert immer 2.4 ms) Alle Anderen müssen sowieso erstmal nachlesen, was die Notation bedeutet.Insofern trägt dein Beitrag imo mehr zur Verwirrung als zur Klärung bei.