Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
#1

Многопоточность при сортировке массивов - C++

13.04.2014, 22:11. Просмотров 2750. Ответов 84
Метки нет (Все метки)

Уважаемые, столкнулся с ситуацией, имею 3 массива, содержимое которых одинаково (координаты точек в 3д пространстве), произвожу сортировку каждого массива по определенному измерению (x, y, z), хотел спросить, можно ли как-то ускорить процесс, возникла идея многопоточности (т.е. одновременно выполнять сортировку 3-х массивов), но я не уверен что я корректно мыслю т.к. не разу не сталкивался с многопоточностью, подскажите как правильно ?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2014, 22:11
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Многопоточность при сортировке массивов (C++):

Не могу найти ошибку при сортировке массивов
Даны два числа n и m и два упорядоченных по неубыванию массива A<=A<=....<=A и...

Почему программа падает при сортировке массивов больших размерностей
Добрый день! Подскажите почему прога крашится при размере массива 10000, при...

Задача по сортировке массивов
Используя метод сортировки выбором, переставить элементы так, чтобы непарные...

Обработка массивов и многопоточность
Здравствуйте. Одна из функций обрабатывает массивы и постоянно изменяет...

Ошибка при сортировке
При сортировке массива вылетает причем именно на последнем числе сортирую...

Ошибка при сортировке Шелла
Сортирую массив, вношу в него 46 элементов случайных значений в диапазоне от 1...

84
newbie666
Заблокирован
13.04.2014, 22:22 #2
да конечно лучше делать в трёх потоках, для такой примитивной цели можешь не гемороиться с ручным созданием потоков, советую использовать Intel TBB и его parallel_for и на будущее, поставь себе Intel Parallel Studio - много чего узнаешь вдобавок ...

Добавлено через 1 минуту
выкладывай свой код - распарралелю
0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
13.04.2014, 22:35  [ТС] #3
ну вот допустим:
C++
1
2
3
4
        nodeKdTree::qSortX(x, 0, num-1);
    nodeKdTree::qSortY(y, 0, num-1);
    nodeKdTree::qSortZ(z, 0, num-1);
/*где x, название массива, num соответсвенно количестов элементов (входные значения функции: массив, индекс первого элемента, индекс последнего элемента)*/
0
newbie666
Заблокирован
13.04.2014, 23:03 #4
ну вот смотри, надеюсь разберёшся.... TBB не использовал, предполагая что ты не догадаешься, как его подключить
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
#include <tchar.h>
#include <windows.h>
#include <vector>
#include <algorithm>
 
DWORD WINAPI SortThread(LPVOID lpParameter);
 
int _tmain(int argc, _TCHAR* argv[])
{   
    std::vector<std::vector<int>> data;
    for(int i = 0; i < 3; i++)
    {
        std::vector<int> item;
        for(int j = 0; j < 100; j++)
        {
            item.push_back(rand());
        }
        data.push_back(item);
    }
 
    for(int i = 0; i < data.size(); i++)
        CreateThread(NULL, NULL, SortThread, &data[i], NULL, NULL);
    
    return 0;
}
 
DWORD WINAPI SortThread(LPVOID lpParameter)
{
    std::vector<int> *item = static_cast<std::vector<int>*>(lpParameter);
    std::sort(item->begin(), item->end(), [](const int a, const int b) { return a < b; });
    return 0;
}
1
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
13.04.2014, 23:28  [ТС] #5
так полагаю функция CreateThread создает поток ? а как его потом освобождать или тут это не требуется ? или это вообще псевдокод ?)
0
newbie666
Заблокирован
13.04.2014, 23:32 #6
Цитата Сообщение от NEvOl Посмотреть сообщение
или это вообще псевдокод
нет, это рабочий код
Цитата Сообщение от NEvOl Посмотреть сообщение
так полагаю функция CreateThread создает поток ?
да
Цитата Сообщение от NEvOl Посмотреть сообщение
а как его потом освобождать или тут это не требуется ?
поток освобождать не надо, поток заканчивает свою работу по завершению поточной функции. Тоесть как только
C++
1
SortThread
выходит - поток автоматический закрывается
1
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 00:46  [ТС] #7
newbie666, хм.. можете пояснить как вообще происходит выполнение программы, я немного не понимаю, создается поток и сразу вызывается функция с соответствующими данными, при этом программа продолжает работать дальше и как только функция выполнится данные обновтяся или как?
1
newbie666
Заблокирован
14.04.2014, 00:56 #8
честно говоря я сам тут немного накосячил, здесь процесс раньше завершится, чем отработают потоки скорее всего, так что в данном примитивном примере перед return 0; в мэйне надо поставить какую то паузу или std::cin или гет чар

Я не понял вопроса, ты конкретно спроси.
Если что - функция main - это так сказать Entry Point процесса, которая соответственно создаёт главный поток, в котором и выполняется, в данном примере создаётся дополнительно три потока (в цикле), в каждый из которого передаётся элемент массива. Для каждого потока будет вызван код поточной функции, в котором будет произведена сортировка.
Если же ты хочешь сделать какие - то операции над общими данными несколькими потоками - нужно учесть синхронизацию потоков, в Windows лучше делать через EnterCriticalSection, в Linux - мьютексами
0
alsav22
5438 / 4833 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
14.04.2014, 03:03 #9
Если компилятор поддерживает С++11:
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
#include <thread>
#include <iostream>
 
namespace nodeKdTree
{
 
void qSortX(int* x, int ib, int ie)
{
    for (int j = 0; j < 100; ++j)
        for (int i = ib; i <= ie; ++i)
        {
            std::cout << "X ";
        }
}
 
void qSortY(int* x, int ib, int ie)
{
    for (int j = 0; j < 100; ++j)
        for (int i = ib; i <= ie; ++i)
        {
            std::cout << "Y ";
        }
}
 
void qSortZ(int* x, int ib, int ie)
{
    for (int j = 0; j < 100; ++j)
        for (int i = ib; i <= ie; ++i)
        {
            std::cout << "Z ";
        }
}
 
}
 
int main()
{
    const int num = 20;
    int x[num];
    int y[num];
    int z[num];
 
    std::thread th1(nodeKdTree::qSortX, x, 0, num - 1);
    std::thread th2(nodeKdTree::qSortY, y, 0, num - 1);
    std::thread th3(nodeKdTree::qSortZ, z, 0, num - 1);
    th1.join();
    th2.join();
    th3.join();
 
    return 0;
}
1
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 08:41  [ТС] #10
newbie666, вопрос заключается в том когда я получу отсортированный массив ?) если работать без потоков то программа ведь пошагово выполняется, т.е. сначала сортируется 1-ый массив, после него второй и так далее, а тут я как понимаю параллельно все происходит ?

Добавлено через 17 минут
alsav22, странно у меня говорит что thread не является членом std, это говорит о том что у меня компилятор не поддерживает С++11 ?
0
newbie666
Заблокирован
14.04.2014, 08:48 #11
Цитата Сообщение от NEvOl Посмотреть сообщение
а тут я как понимаю параллельно все происходит ?
правильно понимаешь, если хочешь конкретно знать когда всё потоки завершаться, то есть твой массив массивов полностью отсортируется, примени события например:
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
#include <tchar.h>
#include <windows.h>
#include <vector>
#include <algorithm>
 
DWORD WINAPI SortThread(LPVOID lpParameter);
 
int _tmain(int argc, _TCHAR* argv[])
{   
    std::vector<std::pair<HANDLE, std::vector<int>>> data;
    for(int i = 0; i < 3; i++)
    {
        std::vector<int> item;
        for(int j = 0; j < 100; j++)
        {
            item.push_back(rand());
        }       
        data.push_back(std::make_pair(CreateEvent(NULL, TRUE, FALSE, NULL), item));
    }
    HANDLE *threadEvent = new HANDLE[data.size()];
    for(unsigned int i = 0; i < data.size(); i++)
    {
        threadEvent[i] = data[i].first;
        CreateThread(NULL, NULL, SortThread, &data[i], NULL, NULL);
    }   
 
    WaitForMultipleObjects(data.size(), threadEvent, TRUE, INFINITE);
 
    delete[] threadEvent;
 
    return 0;
}
 
DWORD WINAPI SortThread(LPVOID lpParameter)
{
    std::pair<HANDLE, std::vector<int>> *item = static_cast<std::pair<HANDLE, std::vector<int>>*>(lpParameter);
    std::sort(item->second.begin(), item->second.end(), [](const int a, const int b) { return a < b; });
    SetEvent(item->first);
    return 0;
}
Добавлено через 1 минуту
Цитата Сообщение от NEvOl Посмотреть сообщение
alsav22, странно у меня говорит что thread не является членом std, это говорит о том что у меня компилятор не поддерживает С++11 ?
#include <thread>
1
alsav22
5438 / 4833 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
14.04.2014, 10:44 #12
Цитата Сообщение от newbie666 Посмотреть сообщение
#include <thread>
Цитата Сообщение от alsav22 Посмотреть сообщение
#include <thread>
Цитата Сообщение от NEvOl Посмотреть сообщение
это говорит о том что у меня компилятор не поддерживает С++11 ?
Среда какая?
0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 12:29  [ТС] #13
alsav22, заинклюдил, Microsoft Visual Studio 2012, всеравно ругается.
0
alsav22
5438 / 4833 / 831
Регистрация: 04.06.2011
Сообщений: 13,587
14.04.2014, 12:47 #14
Цитата Сообщение от NEvOl Посмотреть сообщение
alsav22, заинклюдил
Это не мне, я и так знаю, что у меня в коде есть #include <thread>.
Т.е., на #include <thread> не ругается, а на std::thread ругается? Код какой пробуете? Чисто мой?
Сейчас проверю на 13-й студии.
0
newbie666
Заблокирован
14.04.2014, 12:53 #15
да гонит он, у меня VS2012 - всё работает...
0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 13:13  [ТС] #16
извиняюсь, перезапустил студию, перестало выпендриваться, иногда бывает что чушь начинает нести) а если использовать thread класс, то как тут ? можете пояснить, как отловить событие о том что массив отсортировался ?
0
newbie666
14.04.2014, 13:20
  #17

Не по теме:

Цитата Сообщение от NEvOl Посмотреть сообщение
а если использовать thread класс
а зачем? собрался под пингвинов софт писать? )))

0
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 13:23  [ТС] #18
хм.. теперь вроде все работает, спасибо большое всем

Добавлено через 1 минуту
newbie666, нет, но я не совсем понимаю, при отслеживании события "завершения сортировки", нам нужны дескрипторы потоков ?
C++
1
threadEvent[i] = data[i].first;
или что это ?)
0
newbie666
Заблокирован
14.04.2014, 13:27 #19
Цитата Сообщение от NEvOl Посмотреть сообщение
нам нужны дескрипторы потоков ?
не - это не дескрипторы потоков, это хэндлы обытий, которые создаются здесь:
C++
1
[CPP] data.push_back(std::make_pair(CreateEvent(NULL, TRUE, FALSE, NULL), item));
[/CPP] и суются в first пары вектора ...
Дальше мы ждём, пока все 3 события просигналят (а не хотя бы одно из них)
C++
1
WaitForMultipleObjects(data.size(), threadEvent, TRUE, INFINITE);
(это 3-й параметр TRUE)
как только все три события просигналять - программа поедет дальше....
А в сигнальное состояние каждое событие каждого потока устанавливается тут:
Цитата Сообщение от newbie666 Посмотреть сообщение
SetEvent(item->first);
2
NEvOl
19 / 18 / 1
Регистрация: 13.08.2012
Сообщений: 734
14.04.2014, 15:31  [ТС] #20
хм.. а метод join() что-то типа "уничтожает" поток ?
0
14.04.2014, 15:31
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.04.2014, 15:31
Привет! Вот еще темы с решениями:

Ошибка при сортировке пузырьком
Видимо выход за предел массива, не пойму где ошибка #include &lt;iostream&gt;...

Использование массива индексов при сортировке
Задали задачку отсортировать обычный одномерный массив. Так же, нужно...

Анимация интерфейса при сортировке массива
Доброго времени суток! Подскажите, с помощью чего удобнее всего реализовать...

Не совсем корректный вывод при сортировке
В скриншоте видно что у меня с файла выводит имя цветка, цвет, количество...


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

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

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