3. passender STL-Container gesucht

passender STL-Container gesucht

  • B

    Hi Leute! :schland:
    Ich brauche für meinen ModelRenderer eine effektive Verwaltung. Die Aufgaben wären folgende:
    - Speichern von Informationen, die für das Renden benötigt werden: Model und Instanzdaten -> Objektdaten
    - Hinzufügen beliebig vieler Objektdaten -> Keine Begrenzung in der Größe
    - Sortieren der Objektdaten nach dem Model -> selbstdefinierte Funktion
    - Abarbeiten (Rendern) der sortierten Objektdaten

    Gibt es da etwas besseres als std::list?

    0
  • D

    Intuitiv würde ich da auch mal zu einer Liste tendieren. Kommt aber dann extrem auf die tatsächliche Auslastung drauf an. Sortieren ist halt bei einer Liste teurer, als bei anderen Containern (vector, dequeue), aber ob das wirklich relevant ist muss sich zeigen, dann könnte sich allerdings auch etwas baumartiges (AVL, RB) lohnen, welche allerdings nicht in der Standardbibliothek enthalten sind (zumindest nicht zu einem solchem Gebrauch).

    0
  • B

    Mit Dequeue hast du mich auf Queue gebracht. Gefällt mir.
    Wie sieht es da mit der Perfocmance aus?
    Im Prinzip läuft das so ab:
    - nach und nach mit push_back füllen
    - sortieren
    - abarbeiten
    - leeren

    0
  • N

    Container-Auswahl

    0
  • 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
Anmelden zum Antworten