C++ Container sehr effizient beim Hinzufügen von Elementen zum Ende

Ich habe ein C++ - Programm für wissenschaftliche Zwecke ausgeführt und ich bin jetzt dabei, es zu optimieren.C++ Container sehr effizient beim Hinzufügen von Elementen zum Ende

Der Engpass scheint eine Funktion zu sein, wo ich Paare von Ganzzahlen stapeln muss. Ihre Nummer ist unmöglich von Anfang an zu wissen, und ich habe eine std::vector einer benutzerdefinierten Struktur mit zwei ints verwendet. Gibt es einen effizienteren Datencontainer für das wiederholte Hinzufügen von Elementen am Ende? Sollte ich es mit zwei ints anstelle eines Paares oder einer benutzerdefinierten Struktur verwenden?

edit: Nach Timing und mein Programm Profilieren, kann ich sagen, dass für meinen Gebrauch, vector als deque etwas schneller ist (nur um 3%). Meine Laien schließen daraus, dass die CPU die Kontiguität der Daten gut nutzt. Optimierung ist mehr denn je eine Zauberei für mich! Und denen kann es helfen: Ich habe meine Laufzeit deutlich verbessert, indem ich vom STL C++ 11 Zufallsgenerator auf den BOOST geschaltet habe.

Quelle

2015-06-09 Learning is a mess

Verwandte: http://stackoverflow.com/questions/471432/in-which-scenario-do -i-use-a-particular-stl-container – EdChum

Eine schnelle 'std :: list' – Bastien

Wie müssen Sie auf die Daten zugreifen? Müssen Sie von vorne, von hinten oder dazwischen zugreifen? Diese Information ist wichtig, um den zu verwendenden Container zu bestimmen. –

Die Kosten der logarithmischen Anzahl von Neuzuweisungen, die Sie tun müssen, ist wohl irrelevant. Sie können jedoch eine std::deque verwenden, die O(1) Einfügung an der Front und am Ende garantiert. Sie würden Kontiguität verlieren, aber einige Cachefreundlichkeit wird beibehalten. Eine deque ist normalerweise ein guter Kompromiss, vor allem, wenn Sie von vorne anfangen müssen.

Erwägen Sie auch, die Anzahl der Elemente zu schätzen, die der Vektor speichert, und reserve zu verwenden. Seien Sie vorsichtig, aber verschwenden Sie nicht zu viel Speicher oder Sie erhalten den gegenteiligen Effekt.

Quelle

2015-06-09 15:14:00 gd1

Eine schöne Studie dazu: http://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container – norisknofun

Danke für den Vorschlag, ich werde beide benchmarken und sehen wenn es Verbesserungen gibt. Ich hatte zwar Bedenken, die Reserve zu nennen, aber dann wurde mir klar, dass ich keine Ahnung von der Verteilung oder dem Mittelwert der endgültigen Größe hatte, und die Verwendung eines sehr großen Werts war ineffizient, wenn die Zeit abgelaufen war. Danke vielmals!! –

Denken Sie daran, auch dem @KerrekSB-Hinweis zu folgen, d. H., Wenn möglich, den Vektor wiederzuverwenden. – gd1

Wie bereits von gd1 erwähnt, ermöglicht eine std::deque (zweiseitige Warteschlange) schnelles Einfügen und Löschen an beiden Enden. Darüber hinaus macht das Einfügen und Löschen an einem Ende einer Deque niemals Zeiger oder Referenzen ungültig.

In Ihrem Fall Sie könnte zum Beispiel std::deque mit std::pair (definiert in <utility>) benutzen, um Ihre Bedürfnisse anzupassen:

// Small example: 
deque<pair<int, int>> deq; 
deq.push_back({1234, 4321}); 
cout << deq.at(0).first << " " << deq.at(0).second; 

// using 'at' above, should normally be inside a try block as it may throw 
// out_of_range exception

Quelle

2015-06-09 15:44:00

C++ Container sehr effizient beim Hinzufügen von Elementen zum Ende

Antwort

Verwandte Themen