mardi 28 novembre 2017

Sort a vector of vectors in parallel using a conditional variable?

I am trying to sort a NxN vector of vectors in parallel by dispatching N threads for each vector. I want to display the vector of vectors every time each vector within the vector of vectors has been sorted. Please see example below.

Initially

2,1,3,4
1,3,2,4
3,4,1,2
3,2,1,4

Sorting . . Display

1,2,3,4
1,2,3,4
1,4,3,2
2,3,1,4

. . Sorting . .

1,2,3,4
1,2,3,4
1,3,4,2
2,1,3,4

... and so on..

I have some executable code to do this sequentuially and I have tried to do this using a conditional variable but I can't get it to work with the conditional variable at all.

Below is the sequential code which is working in terms of sorting the vector of vectors but it can't produce the display that I desire.

#include<iostream>
#include<vector>
#include <ctime> 
#include <random>


std::vector<int> row;
std::vector<std::vector<int>> block;
int cols = 10;
auto rng = std::default_random_engine{};


void init()
{

        srand((unsigned)time(0));
        for (int i = 0; i < 10; i++)
        {
            int j;
            j = (rand() % 100) + 1;
            row.push_back(j);
    }

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

                std::vector<int> y;
                std::shuffle(std::begin(row), std::end(row), rng);
                y = row;
                block.push_back(y);
            }

    for (int i = 0; i < cols; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            std::cout << block[i][j] << ", "; 

        }
        std::cout << "\n";
    }
}

void Sort(std::vector<int> &Row)
{

        for (int i = 0; i < cols; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (Row[i] < Row[j])
                {
                    int temp = Row[i];
                    Row[i] = Row[j];
                    Row[j ] = temp;
                }
            }
        }

}

void display()
{
    for (int i = 0; i < cols; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            std::cout << block[i][j] << ", ";

        }
        std::cout << "\n";
    }
}


int main() {

    std::cout << "test\n";
    init();
    std::cout << "\n";
    std::cout << "Sorting";
    std::cout << "\n";
    for(int i =0; i < cols; i++)    
        Sort(block[i]);
    std::cout << "\n";
    display();
    std::cout << "Sorted";
    getchar();
}

The output for the above code is as follows

98, 15, 13, 10, 44, 63, 85, 93, 39, 43,
93, 10, 15, 13, 43, 44, 39, 63, 85, 98,
93, 13, 63, 15, 43, 85, 98, 39, 44, 10,
44, 98, 39, 85, 13, 10, 63, 43, 93, 15,
10, 98, 63, 93, 85, 44, 39, 15, 13, 43,
63, 39, 44, 98, 93, 15, 43, 85, 13, 10,
43, 63, 93, 44, 15, 39, 10, 85, 98, 13,
39, 85, 13, 63, 44, 98, 93, 43, 10, 15,
39, 44, 85, 63, 43, 93, 98, 10, 15, 13,
15, 43, 44, 93, 85, 39, 63, 10, 98, 13,

Sorting

10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
10, 13, 15, 39, 43, 44, 63, 85, 93, 98,
Sorted

The multi-threaded approach that I have taken below is not working as expected. I have tried a number of things but to no success.

#include<iostream>
#include <thread>
#include<vector>
#include <ctime> 
#include <mutex>
#include<chrono>
#include <algorithm>
#include <random>
#include <deque>

std::deque<int> q;
std::mutex mu;
std::condition_variable cond;
int count = 4;
std::vector<int> x{ 5,2,1,3,4 };
std::vector<std::vector<int>> xx;
void init() {
    for (int i = 0; i < 5; i++)
    {
        xx.push_back(x);
    }
}

void display()
{
    for (int i = 0; i < xx.size(); i++)
    {
        for (int j = 0; j < xx[i].size(); j++)
        {
            std::cout << xx[i][j] << " ,";
        }
        std::cout << "\n";
    }

}

bool isSorted(int z)
{
    for (int i = 0; i < 5; i++)
    {
        if (xx[z][i] > xx[z][i + 1])
            return false;
    }
    return true;
}

void function_1(int &row)
{

    while (!isSorted(row))
    {
        std::unique_lock<std::mutex> locker(mu);
        for (int i = 0; i < 4; i++)
        {
            if (xx[row][i] > xx[row][i + 1])
            {
                int temp = xx[row][i];
                xx[row][i] = xx[row][i + 1];
                xx[row][i + 1] = temp;
            }
        }
        count--;
        locker.unlock();
        cond.notify_one();
        std::this_thread::sleep_for(std::chrono::seconds(2));

    }
}

void function_2() {
    int data = 0;
    while (data != 1)
    {
        std::unique_lock<std::mutex> locker(mu);
        cond.wait(locker, []() {return (count == 0); });
        q.clear();
        display();
        count = 4;
        locker.unlock();

    }
}

int main()
{
    init();
    for (int i = 0; i < 4; i++) {
        std::thread *t1 = new std::thread(function_1, std::ref(i));
    }
    std::thread t2(function_2);
    //  t2.join();
    std::cout << " all threads done";
    getchar();
}

Aucun commentaire:

Enregistrer un commentaire