Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
mishula
0 / 0 / 0
Регистрация: 01.10.2014
Сообщений: 87
#1

Многопоточная сортировка: синхронизация - C++

27.03.2016, 15:22. Просмотров 307. Ответов 3
Метки нет (Все метки)

Добрый день, только начал изучать параллельное программирование и решил написать параллельную битоническую сортировку. Суть её в том, что за одну итерацию мы проходим по массиву 2 раза, первый раз переставляя 1 и 2, 3 и 4 и т.д., а второй раз переставляем 2 и 3, 4 и 5 и т.д.
Как я понимаю, нужно использовать n/2 потоков, если всего в массиве n элементов. После прохождения в первый раз массива нужно все подождать все потоки, чтобы вывести промежуточные результаты и затем сортировать со второго элемента. Но с этой синхронизацией у меня и возникли проблемы, несмотря на то, что разделяемых объектов нет и мьютексы использовать не нужно. Вот мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <thread>
#include <vector>
#include <iostream>
 
 
void compareAndSwap(std::vector<int> &v, int i) {
    if (v[i] > v[i + 1])//если 10 элементов сортирую, то пишет standart c++ libraries out of range
    {
        int t = v[i];
        v[i] = v[i + 1];
        v[i + 1] = t;
    }
}
class Storage {
 
    std::mutex _mu1;
public:
    Storage() {
        std::cout << "I'm created!" << std::endl;
    }
    ~Storage() {
        data.clear();
        std::cout << "I'm die!" << std::endl;
    }
    int Size() {
        return data.size();
    }
    void sort() {
        
        std::vector<std::thread>th;
        for (int k = 0; k < data.size(); ++k)
        {
 
            for (int i = 0, j = 0; i < th.size() - 1; i += 2, j++)
            {
                th.push_back(std::thread(compareAndSwap, std::ref(data), i));
                if (th[j].joinable())
                    th[j].join();
            }
                
            th.clear();
            std::cout << *this;//почему-то если написать cout<<data, то пишет, что нет оператора вывода, соотв двум операндам
            //Print(x, l);
            for (int j = 1, i = 0; j < data.size(); j += 2, i++)
            {
                th.push_back(std::thread(compareAndSwap, std::ref(data), j));
                if (th[i].joinable())
                    th[i].join();
            }
            th.clear();
            std::cout << *this;//почему-то если написать cout<<data, то пишет, что нет оператора вывода, соотв двум операндам
        }
    }
    void pushToData(int num) {
        data.push_back(num);
    }
    friend std::ostream& operator<<(std::ostream &os, Storage &st) {
        for (int i = 0; i < st.data.size(); i++){
             os<< st.data[i]<<" ";
        }
        return std::cout << std::endl;
    }
private:
    std::vector<int>data;
 
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int x;
    Storage st;
    while (std::cin >> x) {
        st.pushToData(x);
    }
    const int size = st.Size();
    st.sort();
    std::cout << st;
    system("pause");
    
    return 0;
}
Если элементов меньше 10, то сортировка просто идет неправильно, однако если 10 и более, то выводит ошибку expression subscript out of range. Помогите, пожалуйста, решить с этим проблему и по возможности покажите, как можно бы было в моем примере один и тот же поток использовать несколько раз, так как если написать
C++
1
th[i](compareAndSwap, std::ref(data), i);
, то пишет term doesn't evaluate to a function, taking 3 arguments.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2016, 15:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Многопоточная сортировка: синхронизация (C++):

Многопоточная сортировка - C++
Здравствуйте, форумчане. Решаю задачу обработки данных большого размера 1 гб . Данные нужно отсортировать по возрастанию за ограниченное...

Многопоточная сортировка Шелла - C++
Задача стоит в том, что надо создать массив чисел, разделить его на две части, в разных потоках отсортировать с помощью сортировки Шелла....

Многопоточная сортировка Шелла не делится потоки - C++
Здравствуйте! Мне нужно сделать многопоточную сортировку методом Шелла с визуализацией работы потоков. Почему-то поток у меня создается...

многопоточная программа - C++
есть вот такая программа-при нажатии символа, добавляет его справа(1-ая операция); при нажатии клавиши Backspace-стирает последний...

Многопоточная программа, thread не поддерживается моим компилятором - C++
Библиотека theard не поддерживается моим компилятором.Компилятор g++ 4.9.3.Как узнать поддерживает ли мой компилятор c++11? и как...

Многопоточная версия программы работает медленнее однопоточной - C++
Доброго времени суток! Возник довольно странный вопрос, запускаю примерно такую конструкцию: auto l = () { int a = 5, b = 1, c; ...

3
cordfield
44 / 44 / 15
Регистрация: 04.05.2014
Сообщений: 184
27.03.2016, 16:21 #2
Как я понимаю, нужно использовать n/2 потоков, если всего в массиве n элементов
Это точно неправильный подход. А если элементов миллион, создавать 500 000 потоков?
Обычно создают столько потоков, сколько ядер у процессора. Большее количество потоков компьютер одновременно выполнять не сможет (будет происходить переключение процессора с выполнения одного потока на выполнение другого потока).

Зачем создавать поток и сразу после этого ожидать, когда он завершится (выполнять join)? У вас всё равно одновременно не больше 1 потока будет выполняться.

Попробуйте сначала написать однопоточную программу, выполняющую вашу задачу.
0
mishula
0 / 0 / 0
Регистрация: 01.10.2014
Сообщений: 87
27.03.2016, 16:38  [ТС] #3
cordfield, вот я не понимаю, если я в начале объявил объект-поток
C++
1
(std::thread th;
), а потом хочу запустить в этом потоке функцию(
C++
1
th(compareAndSwap, std::ref(data), i);
), то у меня подчеркивает строчку и выводит ошибку call of an object of a class without appropriate function () or conversation to poiter-to-function type.
0
cordfield
44 / 44 / 15
Регистрация: 04.05.2014
Сообщений: 184
27.03.2016, 16:54 #4
mishula, стандартные потоки не такие умные. Им можно сказать только при их создании, какую функцию выполнять. Как только произойдёт выход из этой функции, поток завершится.

Можно создать так называемый "thread pool". Он состоит из N потоков и очереди задач. Каждый поток, когда свободен, ждёт появление задачи в очереди. Когда задача появляется, поток берёт её из очереди и выполняет. Когда задач нет, завершения потока не происходит, а вызывается функция ожидания появления задач в очереди.
0
27.03.2016, 16:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2016, 16:54
Привет! Вот еще темы с ответами:

Многопоточная программа. Вывод в общий файл из нескольких потоков - C++
Здравствуйте! Ооочень нужна ваша помощь. Необходимо разработать программу, состоящую из 3 потоков. С функцией -последовательный вывод в...

Синхронизация - C++
Помогите, пожалуйста, в общих чертах рассказать про синхронизацию процессов на основе механизма обмена сообщениями. как это примерно должно...

синхронизация потоков - C++
проблема в следующем: есть 2 потока один считает некоторую сумму в цикле по столбцам матрицы второй должен выводить промежуточную...

синхронизация в windows - C++
есть два консольных приложения, родительского и дочернего процесса (должны ли они быть консольными), хочу обменяться между ними...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.