deque container performance ??

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

camper

Jester schrieb:

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.

nein. die mögliche reallokation ist ja ein integraler bestandteil von push_back etc. dies bei der betrachtung der komplexität dieser funktion zu vernachlässigen, macht die gesamte überlegung sinnlos (und da die komplexität selbst eine ausschliesslich von der funktion selbst abhängt, können und müssen dinge wie capacity() etc. hier aus acht gelassen werden).
betrachten wir folgendes beispiel:

vector<int> a;
cout << a.size();
for(int i=0; i<n; ++i)
    a.push_back(0);
cout << a.size();
for(int i=0; i<n; ++i)
    a.push_back(0);
cout << a.size();

(cout hier nur um obervable behaviour zu erreichen). komplexität O(1) für push_back bedeutet, dass die beiden schleifen selbst eine komplexität von O(n) haben. offensichtlich benötigt das anfügen des elements selbst amortisiert konstante zeit und die allokation von neuen speicherblöcken ebenfalls (20.1.5/2). bleibt das problem des kopierens beim reallokieren. da eine einzelne kopie ein komplexität von O(n) hat, können wir eine lineare komplexität für jede schleife nur dadurch erreichen, dass die anzahl der nötigen reallokationen selbst eine funktion von n ist, so dass die gesamtzahl der kopieroperationen nur linear von n abhängt. (nur) expotentielles wachstum genügt dieser bedingung.
auf ähnliche weise kann man auf die interne struktur von deque schliessen. dem grunde nach sind nur 2 modelle denkbar, um random access zu erreichen:
- aufteilung in speicherblöcke gleicher grösse die über eine hashmap oder skiplist verknüpft sind
- aufteilung in speicherblöcke, deren grösse expotentiell wächst, welche über eine liste verknüpft sind
wobei die zweite alternative vermutlich seltener implementiert werden wird

soweit es um den unterschied zwischen push_front und push_back bei deque geht - diese beiden operation können sich höchtens um einen gewissen konstanten faktor unterscheiden - soweit es den standard betrifft ist das ein QOI problem und nicht durch die containerdefinition selbst begründbar.

Sauber! Astreiner Beitrag wenn alles stimmt !! Noch 10 mal durchlesen dann versteh ich vielleicht noch en bisschen mehr. Bis jetzt hab ich ma verstanden das push_back und push_front gleich schnell sind, richtig? Naja, oder das die unterschiede sehr marginal sind und die differenz immer konstant bleibt. Also kann ich daraus schliessen das push_front and push_back, bzw insert begin und inser end, was ja das gleiche is, die selbe performance haben.

Danke!

Daniel

b7f7

deque::push_back() ist konstant, weil es nicht von der Anzahl der in der Deque gespeicherten Objekte abhängt.
vector::push_back() ist eigentlich nicht O(1), weil es mit steigenden N stärker wächst als const, obwohl das Wachstum nur leicht darüber liegt.
Die Alokation des Speichers ist hir atomar nur die Copy zählt für die Komplexitätsbetrachtungen.

camper

b7f7 schrieb:

deque::push_back() ist konstant, weil es nicht von der Anzahl der in der Deque gespeicherten Objekte abhängt.
vector::push_back() ist eigentlich nicht O(1), weil es mit steigenden N stärker wächst als const, obwohl das Wachstum nur leicht darüber liegt.
Die Alokation des Speichers ist hir atomar nur die Copy zählt für die Komplexitätsbetrachtungen.

nein. amortisiert bedeutet im mittel - folglich dürfen wir nicht individuelle operationen betrachten. kleines beispiel

#include <vector>
#include <iostream>
using namespace std;

struct Element
{
	static unsigned copy_count;
	char foo;
	Element() {}
	Element(const Element&) { ++copy_count; }
	Element& operator=(const Element&)
	{
		++copy_count;
		return *this;
	}
};

unsigned Element::copy_count = 0;
Element x;

const double k = 100;
int main()
{
	for ( int i = 1; i < 1000000 ; ++i )
	{
		vector<Element> v( i );
		Element::copy_count = 0;
		for ( int j = i; j < k * i; ++j )
			v.push_back( x );
		double q = double( Element::copy_count ) / ( k * i );
		cout << i << '\t' << q << endl;
	}
}

der springende punkt hier ist, dass es einen maximalen (implementationsabhängigen) wert für q gibt (vc++7.1 ca.3,565) - völlig unabhängig davon, wie k gewählt wird (wir könnten auch eine andere beliebige andere monoton wachsende funktion zum auffüllen als k*i wählen), oder wieviele elemente bereits im container sind. die amortisierte komplexität von push_back ist nichts anderes als q_max kopieraktionen. wäre die komplexität von push_back grösser als O(1), so dürfte es keine solche obere schranke geben.