Форум программистов, компьютерный форум CyberForum.ru

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

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

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

27.03.2016, 15:22. Просмотров 235. Ответов 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.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.03.2016, 15:22     Многопоточная сортировка: синхронизация
Посмотрите здесь:

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

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

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

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

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

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

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

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

Попробуйте сначала написать однопоточную программу, выполняющую вашу задачу.
mishula
0 / 0 / 0
Регистрация: 01.10.2014
Сообщений: 85
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.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.03.2016, 16:54     Многопоточная сортировка: синхронизация
Еще ссылки по теме:

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

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

Синхронизация потоков в c++ - C++
Совершенно не понятно что не так и как правильно. Задача: Отсортировать массив целых чисел. Программу разбить на два синхронизированных...

Синхронизация процессов - C++
std::mutex позволяет синхронизировать несколько разных потоков. А есть ли в std что ни будь для синхронизации процессов? То есть, программа...

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

Синхронизация потоков - C++
Есть статический класс к которому я хочу обращаться из разных потоков static class MyLog { public: static int log(std::string,...


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

Или воспользуйтесь поиском по форуму:
cordfield
38 / 38 / 13
Регистрация: 04.05.2014
Сообщений: 168
27.03.2016, 16:54     Многопоточная сортировка: синхронизация #4
mishula, стандартные потоки не такие умные. Им можно сказать только при их создании, какую функцию выполнять. Как только произойдёт выход из этой функции, поток завершится.

Можно создать так называемый "thread pool". Он состоит из N потоков и очереди задач. Каждый поток, когда свободен, ждёт появление задачи в очереди. Когда задача появляется, поток берёт её из очереди и выполняет. Когда задач нет, завершения потока не происходит, а вызывается функция ожидания появления задач в очереди.
Yandex
Объявления
27.03.2016, 16:54     Многопоточная сортировка: синхронизация
Ответ Создать тему
Опции темы

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