Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.82/11: Рейтинг темы: голосов - 11, средняя оценка - 4.82
0 / 0 / 1
Регистрация: 01.10.2014
Сообщений: 87
1

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

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

Author24 — интернет-сервис помощи студентам
Добрый день, только начал изучать параллельное программирование и решил написать параллельную битоническую сортировку. Суть её в том, что за одну итерацию мы проходим по массиву 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.03.2016, 15:22
Ответы с готовыми решениями:

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

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

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

Многопоточная быстрая сортировка (уменьшить время работы)
#include &quot;pch.h&quot; #include &lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;ctime&gt; #include&lt;vector&gt;...

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

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

Попробуйте сначала написать однопоточную программу, выполняющую вашу задачу.
0
0 / 0 / 1
Регистрация: 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
44 / 44 / 19
Регистрация: 04.05.2014
Сообщений: 190
27.03.2016, 16:54 4
mishula, стандартные потоки не такие умные. Им можно сказать только при их создании, какую функцию выполнять. Как только произойдёт выход из этой функции, поток завершится.

Можно создать так называемый "thread pool". Он состоит из N потоков и очереди задач. Каждый поток, когда свободен, ждёт появление задачи в очереди. Когда задача появляется, поток берёт её из очереди и выполняет. Когда задач нет, завершения потока не происходит, а вызывается функция ожидания появления задач в очереди.
0
27.03.2016, 16:54
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
27.03.2016, 16:54
Помогаю со студенческими работами здесь

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

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

Многопоточная версия программы работает медленнее однопоточной
Доброго времени суток! Возник довольно странный вопрос, запускаю примерно такую конструкцию: auto...

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


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru