3. passender STL-Container gesucht

passender STL-Container gesucht

  • Mod

    Das klingt für mich eindeutig nach Vector. Die einzigen Schwächen des Vektors (Einfügen und Löschen mittendrin) tauchen nämlich nicht auf. Und da der Vector den anderen (komplizierteren) Containern in der Performance überlegen ist, sollte man zu ihm greifen.

    0
  • D

    SeppJ schrieb:

    Das klingt für mich eindeutig nach Vector. Die einzigen Schwächen des Vektors (Einfügen und Löschen mittendrin) tauchen nämlich nicht auf.

    Das stimmt wohl. Meine Intuition lenkte mich auf die Liste, weil bei ich oftmals bei solchen Aufgaben ebenfalls mittdendrin Zeugs rausschmeissen muss oder in O(n) durchgehe und Sachen entferne.
    Aber wenn nichts entfernt wird (was Blaze mit seinem letzten Post bekräftig), dann ist da wohl ein vector idealer.

    0
  • B

    Danke, mit der Container-Wahl komme ich auf dequeue.
    Ist der vector dafür geeignet, schnell mit push_back befüllt und schnell wieder geleert zu werden?

    0
  • D

    Blaze schrieb:

    Ist der vector dafür geeignet, schnell mit push_back befüllt und schnell wieder geleert zu werden?

    Amortisiert geht das in O(n). Das leeren ist allerdings eine andere Sache. (siehe hier)

    0
  • B

    Sorry, ich merk's gerade. Ich meine Deque und nicht Dequeue.

    0
  • B

    Hab mal schnell gebencht:
    Ergebnisse:

    Start Deque ...
Start Vector ...
Zeit Deque  (in ms): 3278
Zeit Vector (in ms): 889
Drücken Sie eine beliebige Taste . . .

    Demzufolge ist der Vector ~4 mal schneller als die Deque! Die Entscheidung steht fest. Thanks for help!

    Und das ist der Sourcecode des Programmes:

    #include<iostream>
#include<deque>
#include<vector>
#include<windows.h>
using namespace std;

int main()
{
	deque<int> D;
	vector<int> V;

	static const int iRounds= 1024 * 64, iCapacity= 1024;

	cout<<"Start Deque ..."<<endl;
	DWORD dwDStart= timeGetTime();
	for(int i= 0; i < iRounds; i++)
	{
		//Fill
		for(int u= 0; u < iCapacity; u++)
			D.push_back(u);

		//Sort
		sort(D.begin(), D.end());

		//Traverse
		deque<int>::iterator Iter= D.begin();
		for(; Iter != D.end(); Iter++)
			int a= *Iter;

		//Clear
		D.clear();
	}
	DWORD dwDStop= timeGetTime();

	cout<<"Start Vector ..."<<endl;
	DWORD dwVStart= timeGetTime();
	for(int i= 0; i < iRounds; i++)
	{
		//Fill
		for(int u= 0; u < iCapacity; u++)
			V.push_back(u);

		//Sort
		sort(V.begin(), V.end());

		//Traverse
		vector<int>::iterator Iter= V.begin();
		for(; Iter != V.end(); Iter++)
			int a= *Iter;

		//Clear
		V.clear();
	}
	DWORD dwVStop= timeGetTime();

	cout<<"Zeit Deque  (in ms): "<<dwDStop-dwDStart<<endl;
	cout<<"Zeit Vector (in ms): "<<dwVStop-dwVStart<<endl;

	return(0);
}
    0
  • D

    Release kompiliert?

    0
  • B

    Nichtmal mit den VC. Der Compiler war ein alter BCC55. Den nehm ich immer mit TextPad um schnell mal was zu testen, ohne gleich ganze Projekte zu starten.
    Ich probiers aber trotzdem nochmal mit dem VC.

    0
  • B

    Wow! Die Implementierung des VC einer Deque ist aber mal abartig!
    Ich habe die Rundenzahl auf ein 16tel des vorherigen gesetzt.
    Ja, Release!

    Ergibnisse:

    Start Deque ...
Start Vector ...
Zeit Deque  (in ms): 5959 (* 16 = 95344) -> Mannomann!
Zeit Vector (in ms): 47   (* 16 = 752) -> Fast wie BCC, nur bisschen schneller

    Probierts am besten selbst mal aus.
    PS: WinMM.lib linken und algorithm includen für VC!

    0
  • O

    Ich schätze (hoffe) mal, dass das im Release-Mode ganz anders aussieht.

    0
  • B

    Mit "Ja, Release!" meinte ich auch Release.

    Der Debug sagt übrigens:

    Start Deque ...
Start Vector ...
Zeit Deque  (in ms): 26520
Zeit Vector (in ms): 10015
    0
  • Mod

    Blaze schrieb:

    Danke, mit der Container-Wahl komme ich auf dequeue.
    Ist der vector dafür geeignet, schnell mit push_back befüllt und schnell wieder geleert zu werden?

    Befüllen geht ziemlich schnell, einzig deque könnte möglicherweise ein kleines bisschen schneller sein (sofern man vorher kein reserve macht, dann dürfte vector schneller sein). Dafür geht beim vector jeder Zugriff sehr viel schneller als bei anderen Containern. Auch das Löschen geht maximal schnell, sofern du nicht darauf bestehst, dass der Vector dabei den Speicher tatsächlich frei gibt.

    Dem von drakon verlinkten Artikel von 1999 würde ich bei der Performance nicht unbedingt trauen. Ich habe das mal nachprogrammiert:

    #include <vector>
#include <deque>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <sys/time.h>

using namespace std;

typedef vector<unsigned int> container;
//typedef deque<unsigned int> container;

long miliseconds(timeval start, timeval end)
{
  long mtime, seconds, useconds;    
  seconds  = end.tv_sec  - start.tv_sec;
  useconds = end.tv_usec - start.tv_usec;
  mtime = ((seconds) * 1000 + useconds/1000.0) + 0.5;

  return mtime;
}

int main()
{

  container foo;
  const unsigned int max=100000000;

  timeval start, end;

  // Füllen
  gettimeofday(&start, NULL);
  foo.reserve(max);  // Bei deque auskommentieren
  for(unsigned int i=0; i<max; ++i) foo.push_back(rand());
  gettimeofday(&end, NULL);

  cout<<"Füllen: "<<miliseconds(start,end)<<" Milisekunden"<<endl;

   // Iterieren
  unsigned long sum=0;
  gettimeofday(&start, NULL);
  container::iterator end_iterator=foo.end();
  for(container::iterator i=foo.begin(); i<end_iterator; ++i) sum+=*i;
  gettimeofday(&end, NULL);

  cout<<"Iterieren: "<<miliseconds(start,end)<<" Milisekunden         Anti-Optimierungsausgbe: "<<sum<<endl;

   // Random access
  gettimeofday(&start, NULL);
  for(unsigned int i=0; i<max; ++i) sum+=foo[i];
  gettimeofday(&end, NULL);

  cout<<"Random access, "<<max<<" mal: "<<miliseconds(start,end)<<" Milisekunden         Anti-Optimierungsausgbe: "<<sum<<endl;

   // Random shuffle
  gettimeofday(&start, NULL);
  random_shuffle(foo.begin(),foo.end());
  gettimeofday(&end, NULL);

  cout<<"Random shuffle: "<<miliseconds(start,end)<<" Milisekunden"<<endl;

   // Sortieren
  gettimeofday(&start, NULL);
  sort(foo.begin(),foo.end());
  gettimeofday(&end, NULL);

  cout<<"Sortieren: "<<miliseconds(start,end)<<" Milisekunden"<<endl;

   // Löschen
  gettimeofday(&start, NULL);
  foo.clear();
  gettimeofday(&end, NULL);

  cout<<"Löschen: "<<miliseconds(start,end)<<" Milisekunden"<<endl;
}

    Alle Zeiten auf dem System an dem ich gerade sitze compiliert mit GCC, O3-Optimierung. Das System war zu der zeit unbeschäftigt, die Unterschiede zwischen verschiedenen Läufen sind im niedrigen Prozentbereich, meisten noch kleiner. Alle Läufe mit 100.000.000 unsigned ints:

    [b]vector<unsigned int>:
[/b]Füllen: 1536 Milisekunden
Iterieren: 86 Milisekunden         Anti-Optimierungsausgbe: 107376510835882961
Random access, 100000000 mal: 84 Milisekunden         Anti-Optimierungsausgbe: 214753021671765922
Random shuffle: 13349 Milisekunden
Sortieren: 12136 Milisekunden
Löschen: 0 Milisekunden

[b]vector<unsigned int>, Füllen ohne reserve():
[/b]Füllen: 2078 Milisekunden

[b]deque<unsigned int>:[/b]
Füllen: 1641 Milisekunden
Iterieren: 160 Milisekunden         Anti-Optimierungsausgbe: 107376510835882961
Random access, 100000000 mal: 340 Milisekunden         Anti-Optimierungsausgbe: 214753021671765922
Random shuffle: 19180 Milisekunden
Sortieren: 14341 Milisekunden
Löschen: 132 Milisekunden

    edit: Oh, da hat sich ja ganz schön was getan im Thread während ich programmieren und Messen war. Ich hoffe es passt noch zum Thema.

    edit2: Ich habe auch noch Löschen mittels clear() hinzugefügt.

    0
  • I

    Blaze schrieb:

    Wow! Die Implementierung des VC einer Deque ist aber mal abartig!
    Ich habe die Rundenzahl auf ein 16tel des vorherigen gesetzt.
    Ja, Release!

    Ergibnisse:

    Start Deque ...
Start Vector ...
Zeit Deque  (in ms): 5959 (* 16 = 95344) -> Mannomann!
Zeit Vector (in ms): 47   (* 16 = 752) -> Fast wie BCC, nur bisschen schneller

    Probierts am besten selbst mal aus.
    PS: WinMM.lib linken und algorithm includen für VC!

    Ein bisschen schneller bekommt mans noch mit höchster Optimierung, Präferierung von schnellem Code statt platzsparendem und #define _SECURE_SCL 0 , aber den echten Booster-Compilerschalter hab ich auch noch nicht gefunden.

    0
  • Mod

    ipsec schrieb:

    Ein bisschen schneller bekommt mans noch mit höchster Optimierung, Präferierung von schnellem Code statt platzsparendem und #define _SECURE_SCL 0 , aber den echten Booster-Compilerschalter hab ich auch noch nicht gefunden.

    Kennt der VC profile guided optimization? Ich habe damit beim Intel-Compiler und beim GCC sehr gute Erfahrungen gemacht. Damit kann man auch aus gut optimierten Programmen noch ein paar Prozente gegenüber herkömmlicher Optimierung rausholen. Bei einem sehr schlecht programmierten Programm habe ich sogar schon eine so sagenhafte Steigerung gesehen das schreib ich lieber nicht, das glaubt mir sowieso niemand.

    0
  • B

    Optimierung hin oder her. MS wird schriftlich gelyncht. 😋 Macht alle mit, damit sich auch was ändert!
    Und die Frage ob vector oder deque hat sich damit auch geklärt.

    Und der Sieger ist: std::vector

    0
  • N

    Debug-Laufzeitumgebung aus? Ich frage nicht aus Spass, sondern weil das hier schon etliche Male der Grund für verfälschte Benchmarks war. Und nein, ich meine nicht Debug-Modus.

    0
  • L

    SeppJ schrieb:

    [b]vector<unsigned int>:
[/b]Füllen: 1536 Milisekunden
Iterieren: 86 Milisekunden        
Random access, 100000000 mal: 84 Milisekunden         
Random shuffle: 13349 Milisekunden
Sortieren: 12136 Milisekunden
Löschen: 0 Milisekunden

[b]vector<unsigned int>, Füllen ohne reserve():
[/b]Füllen: 2078 Milisekunden

[b]deque<unsigned int>:[/b]
Füllen: 1641 Milisekunden
Iterieren: 160 Milisekunden        
Random access, 100000000 mal: 340 Milisekunden       
Random shuffle: 19180 Milisekunden
Sortieren: 14341 Milisekunden
Löschen: 132 Milisekunden

    Mit VS2010:

    [b]vector<unsigned int>:[/b]
Füllen: 2278 Milisekunden
Iterieren: 124 Milisekunden   
Random access, 100000000 mal: 94 Milisekunden     
Random shuffle: 14446 Milisekunden
Sortieren: 7269 Milisekunden
Löschen: 0 Milisekunden

[b]vector<unsigned int>, Füllen ohne reserve():[/b]
Füllen: 3245 Milisekunden

[b]deque<unsigned int>:[/b]
Füllen: 4680 Milisekunden
Iterieren: 296 Milisekunden         
Random access, 100000000 mal: 874 Milisekunden       
Random shuffle: 25007 Milisekunden
Sortieren: 21466 Milisekunden
Löschen: 1279 Milisekunden
    0
  • Mod

    Wow, VS2010 hat aber einen ziemlich guten Sortieralgorithmus für vector (Komisch das er für deque überproportional schlecht abschneidet). Könnte natürlich an einer günstig zu sortierenden Zufallsverteilung liegen, aber dennoch bin ich irgendwie beeindruckt. Da sieht man mal wo die Entwicklungszeit geblieben ist die nicht zur Verbesserung der deque benutzt wurde 😉 .

    edit: Warum ist Iterieren bei VS langsamer als Random access? Wie kann das überhaupt möglich sein?

    edit2: Ups ich sehe gerade, dass mein Code gar keinen Random-access macht, sondern iteriert. Das heißt, life hat bei seiner Messung vermutlich checked iterators noch an.

    Wenn ich tatsächlich Random access mache ( foo[rand()%max] ), dann bekomme ich für vector 6800 ms und für deque 23000 ms.

    0
Anmelden zum Antworten