deque container performance ??

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

sorry,

v.insert(v.begin(),a)

meinte ich, NICHT

v.insert(begin(),a)

Jester

camper schrieb:

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.

Huh? Amortisiert konstant heißt doch: im Mittel konstant. Wenn aber eine Allokation anfällt, dann kann es langsamer sein (n Elemente umkopieren kostet O(n), auch wenn es im Schnitt wieder nur O(1) ist). Wenn ich Deine Aussage hier richtig lese behauptest Du aber gerade das Gegenteil.

void push_front(const _Ty& _Val)
	{	// insert element at beginning

#if _HAS_ITERATOR_DEBUGGING
	this->_Orphan_all();
#endif /* _HAS_ITERATOR_DEBUGGING */

	if (_Myoff % _DEQUESIZ == 0
		&& _Mapsize <= (_Mysize + _DEQUESIZ) / _DEQUESIZ)
		_Growmap(1);
	size_type _Newoff = _Myoff != 0 ? _Myoff
		: _Mapsize * _DEQUESIZ;
	size_type _Block = --_Newoff / _DEQUESIZ;
	if (_Map[_Block] == 0)
		_Map[_Block] = this->_Alval.allocate(_DEQUESIZ);
	this->_Alval.construct(_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
	_Myoff = _Newoff;
	++_Mysize;
	}

void push_back(const _Ty& _Val)
	{	// insert element at end

#if _HAS_ITERATOR_DEBUGGING
	this->_Orphan_all();
#endif /* _HAS_ITERATOR_DEBUGGING */

	if ((_Myoff + _Mysize) % _DEQUESIZ == 0
		&& _Mapsize <= (_Mysize + _DEQUESIZ) / _DEQUESIZ)
		_Growmap(1);
	size_type _Newoff = _Myoff + _Mysize;
	size_type _Block = _Newoff / _DEQUESIZ;
	if (_Mapsize <= _Block)
		_Block -= _Mapsize;
	if (_Map[_Block] == 0)
		_Map[_Block] = this->_Alval.allocate(_DEQUESIZ);
	this->_Alval.construct(_Map[_Block] + _Newoff % _DEQUESIZ, _Val);
	++_Mysize;
	}

sind kleine unterschiede zu sehen...

Cool, is das der Quellcode der deque Class??
Wie gesagt ich benutze ja insert, nicht push_front und push_back, also kann ich glaube ich mit dem code nich das meiste anfangen. Aber selbst wenn ich push_font verwenden wuerde haette ich glaube ich so meine Probleme mit dem code.

Daniel

Der Quellcode stammt aus Visual Studio 2005. Einfach die Datei "deque" öffnen, da steht alles drin.

Bei insert werden diese Funktionen aufgerufen.

if(iterator == begin())
{
    push_front(...);
}
else if(iterator == end())
{
    push_back(...);
}
else
{
    ...
}

Ich verstehe den Code auch nicht, da muss man sich schon länger mit beschäftigen. Aber versuch doch mal selbst eine Deque Klasse zu schreiben.

Danke fuer den Quellcode tip, da guck ich auf jedenfall mal rein.

Selber ne deque class zu schreiben hab ich leider keine Zeit fuer, muss 8 Hypothesen analysieren die mit STL containern zu tun haben.

Ich hab mich auch mit der Aufgabenstellung vertan, da stand nich das es einen performance unterschied, da stand man sollte ueberpruefen OB es einen gibt.
Bis jetzt hab ich verschiedene Meinungen gehoert, aber ich weiss es leider immer noch nich.
Wenn man meinen timing code benutzt ist es ja eigentlich eindeutig das es einen unterschied gibt.

Daniel