Füllen eines Vektors in Reihenfolge mit Threads in C++

Question

Ich versuche, einen riesigen Doppelvektor (1929x1341, vielleicht sogar größer werden) mit Daten zu füllen, die jetzt dauert etwa 10 Sekunden zu tun.

als Referenz, dann ist dies der Code so weit:

vector<vector<float>> vector1; 
for (int x = 0; x < mapWidth; x++) { 
    vector<float> vector2; 
    for (int y = 0; y < mapHeight; y++) { 
     int someNumber = calculateNumber(x,y); 
     vector2.push_back(someNumber); 
    } 
    vector1.push_back(vector2); 
} 

Ich denke, ich sollte durch Teilung der Arbeit über separate Threads auf die Arbeitszeiten verkürzen können. Konkret könnte ich die zweite for-Schleife in jeden ihren eigenen Thread trennen.

Leider bin ich nicht gut mit Threads. Das Hauptproblem ist, dass die Vektoren in der Reihenfolge gefüllt werden müssen. Also kann ich den zweiten Vektor nicht einfach auf seine eigenen Threads aufteilen und sie später kombinieren, da dies sie in eine halb zufällige Reihenfolge bringen würde. Ich habe Mutex- und Bedingungsvariablen untersucht, aber ich kann keine gute Lösung für dieses spezielle Problem finden.

Würde jemand bereit sein, mir hier zu helfen?

Answer 1

Sie können so etwas wie tun:

std::vector<std::vector<float>> vector1(mapWidth); 
std::vector<std::thread> threads; 

for (int x = 0; x < mapWidth; x++) { 
    threads.emplace_back([&, x]() { 
     for (int y = 0; y < mapHeight; y++) { 
      int someNumber = calculateNumber(x, y); 
      vector1[x].push_back(someNumber); 
     } 
    }); 
} 

for (int x = 0; x < mapWidth; x++) { 
    threads[x].join(); 
} 

Answer 2

Der schwierige Teil ist hier ein paar Fäden alle zur gleichen Zeit arbeiten müssen. Wenn einer der Threads frei wird, übernimmt ein anderer einen neuen Vektor.

Dafür ist std::future nützlich, weil es uns ermöglicht, die Sammlung von Ergebnissen zwischen Threads zu synchronisieren. Wir können einen asynchronen Task für jeden Thread starten und sammelt seine Ergebnisse in einem std::future Objekt.

Dafür ich std::async verwendet, um die Fäden zu erstellen:

#include <queue> 
#include <vector> 
#include <future> 
#include <iostream> 

int width = 5; 
int height = 3; 

float calculateNumber(int x, int y) 
{ 
    return x * y; 
} 

std::vector<float> fill_info(int x, int height) 
{ 
    std::vector<float> v; 
    v.reserve(height); 

    for(int y = 0; y < height; ++y) 
     v.push_back(calculateNumber(x, y)); 

    return v; 
} 

int main() 
{ 
    // our thread limit 
    const auto number_of_threads = std::thread::hardware_concurrency(); 

    // our data container 
    std::vector<std::vector<float>> v; 

    // queue of asynchronous (shared) results 
    std::queue<std::future<std::vector<float>>> q; 

    for(int x = 0; x < width; x++) 
    { 
     if(q.size() >= number_of_threads) 
     { 
      v.push_back(q.front().get()); // blocks until thread is done 
      q.pop(); 
     } 

     q.emplace(std::async(std::launch::async, fill_info, x, height)); 
    } 

    // collect uncollected results 
    while(!q.empty()) 
    { 
     v.push_back(q.front().get()); // blocks until thread is done 
     q.pop(); 
    } 

    std::cout << v.size()<< '\n'; 

    for(int x = 0; x < width; ++x) 
     for(int y = 0; y < height; ++y) 
      std::cout << "{" << x << ", " << y << "}: " << v[x][y] << '\n'; 
} 

Ausgang:

{0, 0}: 0 
{0, 1}: 0 
{0, 2}: 0 
{1, 0}: 0 
{1, 1}: 1 
{1, 2}: 2 
{2, 0}: 0 
{2, 1}: 2 
{2, 2}: 4 
{3, 0}: 0 
{3, 1}: 3 
{3, 2}: 6 
{4, 0}: 0 
{4, 1}: 4 
{4, 2}: 8