C++: Geschwindigkeit mit Vektor/Array optimieren?

Question

Ich habe eine verschachtelte Struktur for-Schleife und jetzt bin ich zu Beginn jeder Iteration des Vektors erneut erklärt:

void function (n1,n2,bound,etc){ 

    for (int i=0; i<bound; i++){ 
      vector< vector<long long> > vec(n1, vector<long long>(n2)); 
      //about three more for-loops here 
    } 
} 

Dies ermöglicht es mir bei jeder Iteration zu „neu beginnen“, das, weil meine große Werke interne Operationen sind weitgehend in Form von vec [a] [b] + = ein Wert. Aber ich mache mir Sorgen, dass es für große n1 oder große n2 langsam ist. Ich kenne die zugrundeliegende Architektur von Vektoren/Arrays/etc nicht, also bin ich mir nicht sicher, was der schnellste Weg ist, um mit dieser Situation umzugehen. Soll ich stattdessen ein Array verwenden? Sollte ich es anders klären? Soll ich die Logik ganz anders handhaben?

EDIT: Die Größe des Vektors ändert technisch nicht jede Iteration (aber es kann sich auf Basis von Funktionsparametern ändern). Ich versuche einfach, es zu löschen/etc, so dass das Programm unter allen anderen Umständen so schnell wie möglich ist.

EDIT:

Meine Ergebnisse verschiedener Methoden:

Timings (for a sample set of data): 
reclaring vector method: 111623 ms 
clearing/resizing method: 126451 ms 
looping/setting to 0 method: 88686 ms 

Answer 1

Hier ist ein Code, der ein paar verschiedene Methoden testet.

#include <chrono> 
#include <iostream> 
#include <vector> 

int main() 
{ 
    typedef std::chrono::high_resolution_clock clock; 

    unsigned n1 = 1000; 
    unsigned n2 = 1000; 

    // Original method 
    { 
    auto start = clock::now(); 
    for (unsigned i = 0; i < 10000; ++i) 
    { 
     std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2)); 
     // vec is initialized to zero already 

     // do stuff 
    } 
    auto elapsed_time = clock::now() - start; 

    std::cout << elapsed_time.count() << std::endl; 
    } 


    // reinitialize values to zero at every pass in the loop 
    { 
    auto start = clock::now(); 
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2)); 
    for (unsigned i = 0; i < 10000; ++i) 
    { 
     // initialize vec to zero at the start of every loop 
     for (unsigned j = 0; j < n1; ++j) 
     for (unsigned k = 0; k < n2; ++k) 
      vec[j][k] = 0; 

     // do stuff 
    } 
    auto elapsed_time = clock::now() - start; 

    std::cout << elapsed_time.count() << std::endl; 
    } 

    // clearing the vector this way is not optimal since it will destruct the 
    // inner vectors 
    { 
    auto start = clock::now(); 
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2)); 
    for (unsigned i = 0; i < 10000; ++i) 
    { 
     vec.clear(); 
     vec.resize(n1, std::vector<long long>(n2)); 

     // do stuff 
    } 
    auto elapsed_time = clock::now() - start; 

    std::cout << elapsed_time.count() << std::endl; 
    } 

    // equivalent to the second method from above 
    // no performace penalty 
    { 
    auto start = clock::now(); 
    std::vector<std::vector<long long>> vec(n1, std::vector<long long>(n2)); 
    for (unsigned i = 0; i < 10000; ++i) 
    { 
     for (unsigned j = 0; j < n1; ++j) 
     { 
     vec[j].clear(); 
     vec[j].resize(n2); 
     } 

     // do stuff 
    } 
    auto elapsed_time = clock::now() - start; 

    std::cout << elapsed_time.count() << std::endl; 
    } 
} 

bearbeiten: Ich habe den Code aktualisiert, um einen gerechteren Vergleich zwischen den Methoden zu machen. Edit 2: Bereinigt den Code ein wenig, Methoden 2 oder 4 sind der Weg zu gehen.

Hier sind die Zeitpunkte der vier oben genannten Methoden auf meinem Computer:

16327389 
15216024 
16371469 
15279471 

Der Punkt ist, dass man verschiedene Methoden und Profil ausprobieren sollte Ihren Code.

Answer 2

ich eine klare Präferenz für kleine Bereiche (dh die Variable in der innersten Schleife deklarieren, wenn sie nur dort verwendet wird), aber für große Größen Dies könnte viele Zuweisungen verursachen. Wenn diese Schleife ein Leistungsproblem ist, versuchen Sie, die Variable außerhalb der Schleife zu deklarieren und sie nur innerhalb der Schleife zu löschen - dies ist jedoch nur dann vorteilhaft, wenn die (reservierte) Größe des Vektors identisch bleibt. Wenn Sie die Größe des Vektors ändern, werden Sie trotzdem neu zugeordnet.

Verwenden Sie kein RAW-Array - es bringt Ihnen keinen Vorteil und nur Ärger.

Answer 3

Der Aufwand für die Verwendung eines Vektors im Vergleich zu einem Array ist gering, besonders wenn Sie eine Menge nützlicher Funktionen aus dem Vektor erhalten. Intern weist ein Vektor ein Array zu. Also Vektor ist der Weg zu gehen.

Answer 4

Warum nicht so etwas wie das:

{ 
    vector< vector<long long> > vec(n1, vector<long long>(n2)); 

    for (int i=0; i<bound; i++){ 

     //about three more for-loops here 

     vec.clear(); 
    } 
} 

bearbeiten: hinzugefügt Umfang Zahnspange ;-)

Answer 5

Zusätzlich zu den vorherigen Kommentaren:

wenn verwenden Sie Robinsons Swap-Methode, Sie könnte durch das asynchrone Abwickeln dieses Swaps immer schneller werden.

Answer 6

Wenn ein Container Auswahl i in der Regel dieses Diagramm verwenden, um mir zu helfen:

source

---

Other than that,

Wie zuvor geschrieben, wenn diese Leistung verursacht Probleme deklarieren den Container außerhalb der for-Schleife und löschen ihn einfach zu Beginn jeder Iteration

Answer 7

Nun, wenn Sie wirklich besorgt über die Leistung sind (und Sie wissen, die Größe n1 und n2 im Voraus), aber nicht ein C-style-Array verwenden möchten, kann Ihr Freund sein.

EDIT: Angesichts Ihrer Bearbeitung, scheint es, ein ist kein geeigneter Ersatz, da, während die Vektorgröße nicht jede Iteration ändert, es noch nicht vor der Kompilierung bekannt ist.

Answer 8

Da Sie die Vektorwerte in jeder Iteration auf 0 zurücksetzen müssen, läuft diese Frage praktisch so ab, "ob die Kosten für die Zuordnung und Freigabe des Speichers für den Vektor im Vergleich zu den Berechnungen innerhalb der Schleifen billig oder teuer sind" .

Unter der Annahme, dass die Berechnungen der teure Teil des Algorithmus sind, ist die Art, wie Sie sie codiert haben, sowohl klar als auch präzise, ​​zeigt den beabsichtigten Umfang und ist wahrscheinlich genauso schnell wie alternative Ansätze.

Wenn jedoch Ihre Berechnungen und Updates sind extrem schnell und die Zuordnung/Aufhebung der Zuordnung des Vektors ist relativ teuer, könnten Sie std::fill verwenden Nullen aufzufüllen zurück in das Array am Ende/Anfang jeder Iteration durch die Schleife.

Natürlich kann man nur mit einem Profiler messen. Ich vermute, dass Sie feststellen werden, dass die von Ihnen gewählte Vorgehensweise nicht als Hotspot angezeigt wird und Sie den offensichtlichen Code an Ort und Stelle lassen sollten.