deque container performance ??

Hallo zusammen,

Warum besteht ein performance unterschied wenn man elemente am anfangs eines deque container einfuegt und am ende eines deque containers? Wo koennte ich hilfreiches Material zu diesem Thema finden?

mfg
Daniel

Schau doch in den Sourcecode deiner STL.

Muss nicht so sein. Der Standard schreibt ja nicht vor wie man die Klassen implementieren muss.

Da gibts doch sicherlich schon Analysen zu oder? Bei google hab ich nichts gefunden, da wurden halt nur alle Container miteinander verglichen.

Danke fuer die Hilfe!
Daniel

Wie kommst du überhaupt darauf das es langsamer ist vorne einzufügen? Hast du Test gemacht? Wenn ja dann zeig die uns doch mal...

Wenn ich nen deque v hab und 1000000 elemente am ende einfuege, dann dauert es genau 2.679s.

for (int a=1; a<=d; a++)
v.insert(v.end(),a);

d=1000000

Wenn ich 1000000 elemente am anfang einfuege dauert es 3.097s

for (int a=1; a<=d; a++)
v.insert(v.begin(),a);

d=1000000

Wie misst du die Zeit?

int main( )
{ LARGE_INTEGER LI1,LI2,LIF;             
QueryPerformanceFrequency(&LIF);
double number = (double)LIF.HighPart * UINT_MAX + (double)LIF.LowPart;
double dt, fq = 1.0/number;
int f = LIF.LowPart;
vector<int> v;
QueryPerformanceCounter(&LI1);   
for (int a=1; a<=100000; a++)    //irgend ein container auffuellen
v.insert(v.begin(),a);
QueryPerformanceCounter(&LI2);   
dt = ( ( (double)(LI2.HighPart)*UINT_MAX + (double)LI2.LowPart )
- ( (double)(LI1.HighPart)*UINT_MAX + (double)LI1.LowPart ) )*fq;
cout << "\tfinished with time " << dt << endl;
return 0;
}

CStoll

Hmm, du verwendest in deiner Messung keine deque, sondern einen Vektor (und der ist bei Insert's am Anfang nicht besonders performant)

7H3 N4C3R

Endurance schrieb:

Warum besteht ein performance unterschied wenn man elemente am anfangs eines deque container einfuegt und am ende eines deque containers?

Die Garantie, die der C++-Standard dir gibt, ist dass das Einfügen in ein Deque am Anfang wie am Ende konstante Zeit benötigt - sofern keine Reallokation des Speichers anfällt. Konstant heißt: nicht von der Anzahl der enthaltenen Elemente abhängig. Es heißt aber nicht, dass das Einfügen am Anfang wie am Ende gleich-schnell sein muss.

Informationen dazu findest zu z.B. im Stroustrup. Das wird in den Kapiteln über die verschiedenen Container-Klassen recht genau behandelt.

Falls du dir die Zeitunterschiede nicht erklären kannst - versuch es doch mal selbst und gleich-schnell zu implementieren (oder zumindest die Überlegung anstellen wie du es machen würdest)

camper

7H3 N4C3R schrieb:

Die Garantie, die der C++-Standard dir gibt, ist dass das Einfügen in ein Deque am Anfang wie am Ende konstante Zeit benötigt - sofern keine Reallokation des Speichers anfällt.

allerdings garantiert der standard für deque gerade, dass beim einfügen am anfang oder ende NIEMALS eine reallokation stattfindet.
auch ist das konzept der (amortisiert) konstanten zeit ist etwas anders - es heisst nicht soweit keine reallokation stattfindet sondern trotzdem eine reallokation stattfinden kann. nur deshalb muss std::vector zwingend eine expotentielle wachstumsfunktion benutzen.

7H3 N4C3R

Ups, ich habe mich im Wort vertan. Nicht Reallokation, sondern allgemein Allokation.

Was ist denn Stroustrup, und wo finde ich den, ihn, das???

Endurance schrieb:

Was ist denn Stroustrup, und wo finde ich den, ihn, das???

Google.

Ach nae, google.
Wenn ich Stroustrup in google eingebe kommen 1000000000000000000 seiten mit allen moeglichen Sachen. Gibts da keine genaue quelle, wo uber die ST container peformance gesprochen wird?

Daniel

klick den ersten link an. dann kommst du auf die seite vom erfinder von c++. der hat ein paar bücher geschrieben. und davon sollste dir "The C++ Programming Language" kaufen. gibts auch auf deutsch.

Ok mach ich ma, aber lieber in engl...... meine Kurse sind auch in engl.

Hat denn keiner nen Hinweis wo ich ne antwort auf meine Frage bekomme, ausser bei Stroustrup??

Daniel

Warum benutzt du in deinem Code std::vector aber fragst dann nach std::deque? Irgendwas stimmt doch da nicht.

Weil ich mehrere Aufgaben bewaeltigen muss. Der code ist nen Standard code wo man timen kann wie lange es dauert einen bestimmten Container aufzufuellen. Ich hab 8 Aufgaben, und eine davon fragt halt wieso ein performance unterschied besteht wenn man Elemnte am Anfang und am Ende einer deque einfuegt.

Das ist dann wohl eine Scherzfrage. Es besteht nämlich kein Performance-Unterschied.

Ok das kann natuerlich auch sein, aber warum bekomm ich dann andere ergebnisse?
Versuch mal meinen timing code mit 6000000 elementen die du mit insert in eine deque einfuegst: Einmal mit

v.insert(v.end(), a)

und einmal mit

v.insert(begin(), a)

Je groesser die Anzahl der Elemente, desto groesser is der unterschied.
Das muss irgendwas mit der Speicherreservierung zu tun haben, oder wie eine deque die iterators hin und her schiebt wenn man neue elemente einfuegt.

Daniel