Заполнение вектора в порядке с использованием потоков в C++

Question

Я пытаюсь заполнить огромный двойной вектор (1929x1341, может даже увеличиться) с данными, которые сейчас занимают около 10 секунд.

для справки, это код до сих пор:

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); 
} 

Я думаю, что я должен быть в состоянии сократить рабочее время пути деления работы над отдельными потоками. В частности, я мог бы отделить второй цикл for в каждом своем потоке.

К сожалению, я не очень хорошо разбираюсь с темами. Основная проблема заключается в том, что векторы необходимо заполнять в порядке. Поэтому я не могу просто отделить второй вектор от своих собственных потоков и объединить их позже, поскольку это поставит их в полуслучайный порядок. Я просмотрел мьютекс и переменные условий, но я не могу найти хорошее решение этой конкретной проблемы.

Может кто-нибудь захочет помочь мне здесь?

Answer 1

Вы можете сделать что-то вроде:

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

Хитрость здесь имеющий несколько потоков все работают одновременно. Когда один из потоков становится свободным, другой берет на себя, чтобы создать новый вектор.

Для этого std::future полезен, поскольку он позволяет нам синхронизировать коллекцию результатов, совместно используемых между потоками. Мы можем запустить одну задачу asynchronous для каждого потока и собирать ее результаты в объекте std::future.

Для этого я использовал std::async создавать темы:

#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'; 
} 

Выход:

{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