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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
13.04.2014, 22:11     Многопоточность при сортировке массивов #1
Уважаемые, столкнулся с ситуацией, имею 3 массива, содержимое которых одинаково (координаты точек в 3д пространстве), произвожу сортировку каждого массива по определенному измерению (x, y, z), хотел спросить, можно ли как-то ускорить процесс, возникла идея многопоточности (т.е. одновременно выполнять сортировку 3-х массивов), но я не уверен что я корректно мыслю т.к. не разу не сталкивался с многопоточностью, подскажите как правильно ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newbie666
Заблокирован
13.04.2014, 22:22     Многопоточность при сортировке массивов #2
да конечно лучше делать в трёх потоках, для такой примитивной цели можешь не гемороиться с ручным созданием потоков, советую использовать Intel TBB и его parallel_for и на будущее, поставь себе Intel Parallel Studio - много чего узнаешь вдобавок ...

Добавлено через 1 минуту
выкладывай свой код - распарралелю
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
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 соответсвенно количестов элементов (входные значения функции: массив, индекс первого элемента, индекс последнего элемента)*/
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;
}
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
13.04.2014, 23:28  [ТС]     Многопоточность при сортировке массивов #5
так полагаю функция CreateThread создает поток ? а как его потом освобождать или тут это не требуется ? или это вообще псевдокод ?)
newbie666
Заблокирован
13.04.2014, 23:32     Многопоточность при сортировке массивов #6
Цитата Сообщение от NEvOl Посмотреть сообщение
или это вообще псевдокод
нет, это рабочий код
Цитата Сообщение от NEvOl Посмотреть сообщение
так полагаю функция CreateThread создает поток ?
да
Цитата Сообщение от NEvOl Посмотреть сообщение
а как его потом освобождать или тут это не требуется ?
поток освобождать не надо, поток заканчивает свою работу по завершению поточной функции. Тоесть как только
C++
1
SortThread
выходит - поток автоматический закрывается
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
14.04.2014, 00:46  [ТС]     Многопоточность при сортировке массивов #7
newbie666, хм.. можете пояснить как вообще происходит выполнение программы, я немного не понимаю, создается поток и сразу вызывается функция с соответствующими данными, при этом программа продолжает работать дальше и как только функция выполнится данные обновтяся или как?
newbie666
Заблокирован
14.04.2014, 00:56     Многопоточность при сортировке массивов #8
честно говоря я сам тут немного накосячил, здесь процесс раньше завершится, чем отработают потоки скорее всего, так что в данном примитивном примере перед return 0; в мэйне надо поставить какую то паузу или std::cin или гет чар

Я не понял вопроса, ты конкретно спроси.
Если что - функция main - это так сказать Entry Point процесса, которая соответственно создаёт главный поток, в котором и выполняется, в данном примере создаётся дополнительно три потока (в цикле), в каждый из которого передаётся элемент массива. Для каждого потока будет вызван код поточной функции, в котором будет произведена сортировка.
Если же ты хочешь сделать какие - то операции над общими данными несколькими потоками - нужно учесть синхронизацию потоков, в Windows лучше делать через EnterCriticalSection, в Linux - мьютексами
alsav22
5282 / 4801 / 442
Регистрация: 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;
}
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
14.04.2014, 08:41  [ТС]     Многопоточность при сортировке массивов #10
newbie666, вопрос заключается в том когда я получу отсортированный массив ?) если работать без потоков то программа ведь пошагово выполняется, т.е. сначала сортируется 1-ый массив, после него второй и так далее, а тут я как понимаю параллельно все происходит ?

Добавлено через 17 минут
alsav22, странно у меня говорит что thread не является членом std, это говорит о том что у меня компилятор не поддерживает С++11 ?
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>
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
14.04.2014, 10:44     Многопоточность при сортировке массивов #12
Цитата Сообщение от newbie666 Посмотреть сообщение
#include <thread>
Цитата Сообщение от alsav22 Посмотреть сообщение
#include <thread>
Цитата Сообщение от NEvOl Посмотреть сообщение
это говорит о том что у меня компилятор не поддерживает С++11 ?
Среда какая?
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
14.04.2014, 12:29  [ТС]     Многопоточность при сортировке массивов #13
alsav22, заинклюдил, Microsoft Visual Studio 2012, всеравно ругается.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
14.04.2014, 12:47     Многопоточность при сортировке массивов #14
Цитата Сообщение от NEvOl Посмотреть сообщение
alsav22, заинклюдил
Это не мне, я и так знаю, что у меня в коде есть #include <thread>.
Т.е., на #include <thread> не ругается, а на std::thread ругается? Код какой пробуете? Чисто мой?
Сейчас проверю на 13-й студии.
newbie666
Заблокирован
14.04.2014, 12:53     Многопоточность при сортировке массивов #15
да гонит он, у меня VS2012 - всё работает...
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
14.04.2014, 13:13  [ТС]     Многопоточность при сортировке массивов #16
извиняюсь, перезапустил студию, перестало выпендриваться, иногда бывает что чушь начинает нести) а если использовать thread класс, то как тут ? можете пояснить, как отловить событие о том что массив отсортировался ?
newbie666
14.04.2014, 13:20
  #17

Не по теме:

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

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

Добавлено через 1 минуту
newbie666, нет, но я не совсем понимаю, при отслеживании события "завершения сортировки", нам нужны дескрипторы потоков ?
C++
1
threadEvent[i] = data[i].first;
или что это ?)
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);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.04.2014, 15:31     Многопоточность при сортировке массивов
Еще ссылки по теме:

C++ Ошибка при сортировке Шелла
Ошибка при сортировке пузырьком C++
C++ Почему программа падает при сортировке массивов больших размерностей

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

Или воспользуйтесь поиском по форуму:
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
14.04.2014, 15:31  [ТС]     Многопоточность при сортировке массивов #20
хм.. а метод join() что-то типа "уничтожает" поток ?
Yandex
Объявления
14.04.2014, 15:31     Многопоточность при сортировке массивов
Ответ Создать тему
Опции темы

Текущее время: 10:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru