deque container performance ??

[Endurance]

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.

[quellcode.]

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...

[Endurance]

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

[quellcode.]

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.

[Endurance]

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.

[Endurance]

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.

[Jester]

camper schrieb:

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.

Bau mal ne schleife, die immer nur durchlaufen wird, wenn man ne Taste drückt. Und in der Schleife drin wird was angehängt.

So, jetzt dauert der Ablauf unterschiedlich lange. Mal O(n), wenn er gerade kopieren muß, mal O(1) wenn noch Platz da ist. Die Laufzeit ist im Mittel O(1). Insbesondere ist sie im Widerspruch zu Deiner obigen Aussage O(1) sofern keine Reallikation stanntfindet. Wenn eine stattfindet zahlen wir O(n). Daß das bei der Analyse natürlich wohl zu berücksichtigen ist sieht man leicht am Beispiel von Echtzeitsystemen. Wenn die garantiert O(1) sein sollen darf sowas genau nicht passieren.

[camper]

Jester schrieb:

camper schrieb:

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.

Bau mal ne schleife, die immer nur durchlaufen wird, wenn man ne Taste drückt. Und in der Schleife drin wird was angehängt.

So, jetzt dauert der Ablauf unterschiedlich lange. Mal O(n), wenn er gerade kopieren muß, mal O(1) wenn noch Platz da ist. Die Laufzeit ist im Mittel O(1). Insbesondere ist sie im Widerspruch zu Deiner obigen Aussage O(1) sofern keine Reallikation stanntfindet. Wenn eine stattfindet zahlen wir O(n). Daß das bei der Analyse natürlich wohl zu berücksichtigen ist sieht man leicht am Beispiel von Echtzeitsystemen. Wenn die garantiert O(1) sein sollen darf sowas genau nicht passieren.

und dabei vernachlässigst du einfach mal die wichtigste bedingung: "im Mittel". schliesslich macht die O Notation niemals aussagen über die laufzeit einer einzelnen operation, denn diese kann von nebenbedingungen abhängen. wir müssen stets eine hinreichend grosse anzahl von operationen durchführen und die O notation gibt uns dann die möglichkeit, eine obere grenze für die laufzeit dieser n operationen (bzw. ein mittel für jede einzelne operation) zu bestimmen, die mit sicherheit nicht überschritten wird, sofern n hinreichend gross ist. und es ist eben so, dass zwar jede beliebige push_back operation mit einer reallokation verbunden sein kann - die häufigkeit einer reallokation dagegen ist wohlbestimmt: ~(1/n) oder weniger. unter diesen voraussetzungen "amortisieren" sich die kosten dieser reallokation, da sie über alle operationen (auch slche ohne reallokation) verteilt werden und führen zu einem konstanten maximalen overhead je operation. im übrigen sei auf 23.1.1/12 verwiesen:

Table 68 lists sequence operations that are provided for some types of sequential containers but not others. An implementation shall provide these operations for all container types shown in the "container" column, and shall implement them so as to take amortized constant time.

wohlgemerkt, von reallokation etc. ist dort überhaupt nicht die rede, das ist ein integraler bestandteil dieser operation.

[Jester]

camper schrieb:

und dabei vernachlässigst du einfach mal die wichtigste bedingung: "im Mittel".

Moment mal, Du hast doch behauptet nicht nur im mittel sondern trotz Reallokation.

schliesslich macht die O Notation niemals aussagen über die laufzeit einer einzelnen operation, denn diese kann von nebenbedingungen abhängen.

Das ist falsch. Lies es nach. Das O-Kalkül macht Aussagen über das Wachstum von Funktionen. Man kann damit sagen: diese eine Operation hat diesen Zeitaufwand, man kann aber auch Aussagen über ganze Folgen oder Mengen von Operationen machen. Es geht beides.

wir müssen stets eine hinreichend grosse anzahl von operationen durchführen und die O notation gibt uns dann die möglichkeit, eine obere grenze für die laufzeit dieser n operationen (bzw. ein mittel für jede einzelne operation) zu bestimmen, die mit sicherheit nicht überschritten wird, sofern n hinreichend gross ist.

Diese hinreichend große Anzahl brauchst Du aber nur, wenn Du amortisiert anschaust und das sagt gerade "im Mittel". Und obwohl im Mittel O(1) gilt kann doch eine einzelne Operation mal O(n) Zeit brauchen. Dadurch daß vector aber so schnell wächst fällt dieses einzelne O(n) nicht ins gewicht und im Mittel landen wir bei O(1).

edit: Mir geht es hier auch nicht um irgendwelche C++-Standard-Details, Du mußt also nicht jedesmal die Stellen raussuchen. Mein Einwand ist rein komplexitätstheoretischer Natur.

Fakt ist doch: Im Mittel hat push_back Laufzeit O(1). Eine einzelne Operation kann aber eine Laufzeit von O(n) aufweisen. Genau bedeutet amortisierte Laufzeit.

[camper]

Jester schrieb:

camper schrieb:

und dabei vernachlässigst du einfach mal die wichtigste bedingung: "im Mittel".

Moment mal, Du hast doch behauptet nicht nur im mittel sondern trotz Reallokation.

ich glaube nicht, die formulierung "nicht nur im mittel" verwendet zu haben (kann sie jedenfalls auch nicht beim überfliegen meiner beiträge finden). das wäre auch falsch. bezogen auf standard c++ ist eigentlich immer nur von amortisiert konstanter zeit die rede, insofern wird "im Mittel" impliziert.

schliesslich macht die O Notation niemals aussagen über die laufzeit einer einzelnen operation, denn diese kann von nebenbedingungen abhängen.

Das ist falsch. Lies es nach. Das O-Kalkül macht Aussagen über das Wachstum von Funktionen. Man kann damit sagen: diese eine Operation hat diesen Zeitaufwand, man kann aber auch Aussagen über ganze Folgen oder Mengen von Operationen machen. Es geht beides.

ja ok, hab mich verlesen.

Fakt ist doch: Im Mittel hat push_back Laufzeit O(1). Eine einzelne Operation kann aber eine Laufzeit von O(n) aufweisen. Genau bedeutet amortisierte Laufzeit.

wir sind uns einig.

[Jester]

camper schrieb:

ich glaube nicht, die formulierung "nicht nur im mittel" verwendet zu haben (kann sie jedenfalls auch nicht beim überfliegen meiner beiträge finden).

Stimmt. Ich habe die zu anfang von mir zitierte Aussage wohl falsch verstanden. Da wo du schriebst, daß trotz einer Reallokation O(1) Laufzeit ist. Du meintest wohl, daß obwohl diese Reallokationen auftreten können im Mittel O(1) ist. Ich hatte es aber so verstanden, daß Du sagen willst, daß jede Operation O(1) hat, obwohl ne Reallokation stattfinden kann.

Das Verhalten jedes O(1) kann man btw auch hinkriegen. Man muß nur bei jedem Einfügen gleich noch ein paar alte Elemente in nen neuen Buffer rüberkopieren. Das macht's zwar langsamer und speicheraufwendiger, dafür kann man aber konstante Laufzeit bei jeder Operation garantieren.