#ifndef _SORT_H
#define _SORT_H
#include <algorithm>
#include <QTimer>
#include <QtGlobal>
#include <QThread>
#include <QDebug>
class MyThread : public QThread
{
Q_OBJECT
public:
MyThread(){}
void run()
{
//
exec();
}
};
template <typename T>class _Sort
{
static void sort(T* Buff, int l, int r)
{
int i=l;
int j=r;
int x=Buff[(l+r)/2];
do
{
while(Buff<x) ++i;
while(Buff[j]>x) --j;
if(i<=j)
{
std::swap(Buff,Buff[j]);
i++; j--;
}
} while(i<=j);
if(l<j) sort(Buff,l,j);
if(i<r) sort(Buff,i,r);
}
public:
static bool qSort(T* Buff, size_t Size, uint ThreadCount)
{
if (Buff == NULL || Size <= 1 || ThreadCount%2 != 0 || ThreadCount < 2)
{
qDebug() << "Error in params";
return false;
}
//ГДЕ_ТО ТУТ РАССЧИТАЕТСЯ КОЛИЧЕСТВО ПОТОКОВ И УРОВЕНЬ, ГДЕ ОНИ ДОЛЖНЫ ЗАПУСТИТЬСЯ
sort(Buff,0,Size-1);
return true;
}
};
#endif // _SORT_H
Qt QThread
Нужно распараллелить быструю сортировку.
Может, у кого есть ссылки по теме распараллеливания или так подскажет? Что-то не совсем пойму, сколько объектов QThread нужно создавать и когда запускать start. Число потоков кратно 2 и > 1.
Может, у кого есть ссылки по теме распараллеливания или так подскажет? Что-то не совсем пойму, сколько объектов QThread нужно создавать и когда запускать start. Число потоков кратно 2 и > 1.
Код:
public static void qSort(int[] A, int low, int high) {
int i=low;
int j=high;
int x=A[(low+high)/2];
do {
while(A<x) ++i;
while(A[j]>x) --j;
if(i<=j){
int temp=A;
A=A[j];
A[j]=temp;
i++; j--;
}
} while(i<=j);
if(low<j) qSort(A,low,j);//<<==Запускаем в 1-м потоке
if(i<high) qSort(A,i,high);//<<==Запускаем во 2-м потоке
//<<== ожидание закрытия потоков
}
int i=low;
int j=high;
int x=A[(low+high)/2];
do {
while(A<x) ++i;
while(A[j]>x) --j;
if(i<=j){
int temp=A;
A=A[j];
A[j]=temp;
i++; j--;
}
} while(i<=j);
if(low<j) qSort(A,low,j);//<<==Запускаем в 1-м потоке
if(i<high) qSort(A,i,high);//<<==Запускаем во 2-м потоке
//<<== ожидание закрытия потоков
}
Добавить ограничение на кол-во потоков (фиксированное + в зависимости от размера сортируемого массива - если маленький сортировать без потока). Ну и отладить чтоб при равных i и j потоки не пересеклись на 1-м элементе.
Примерно так:
Код:
...
QMutex thread_cnt_mutex;
int thread_cnt=0;
...
void qSort(int *array, int &start, int &end)
{
//сортировка, изменяет start и end
}
...
int * QSortThread::array;
int QSortThread::start;
int QSortThread::end;
...
void QSortThread::run()
{
thread_cnt_mutex.lock();
int thread_cnt+=1;
thread_cnt_mutex.unlock();
int i=start,j=end;
qSort(array,i,j);//сортируем свой кусочек
QSortThread * a=NULL;
QSortThread * b=NULL;
//************
if(start<j)
{
thread_cnt_mutex.lock();
if(thread_cnt<THREADS_MAX && j-start>100500)
{
thread_cnt_mutex.unlock();
a=new QSortThread(array,start,j);
a->start();
}
else
{
thread_cnt_mutex.unlock();
qSort(array,start,j);
}
...
//**********аналогично для второй половины массива
..
if(a)
a->wait();
if(b)
b->wait();
}
thread_cnt_mutex.lock();
int thread_cnt-=1;
thread_cnt_mutex.unlock();
}
...
void gui::sortButtonClick()
{
mysortthread=new QSortThread(array,0,count);
connect(mysortthread,SIGNAL(finished()),this,SLOT(sortFinished()));
mysortthread->start();
}
void gui::sortFinished()
{
//Както так в общем
}
...
QMutex thread_cnt_mutex;
int thread_cnt=0;
...
void qSort(int *array, int &start, int &end)
{
//сортировка, изменяет start и end
}
...
int * QSortThread::array;
int QSortThread::start;
int QSortThread::end;
...
void QSortThread::run()
{
thread_cnt_mutex.lock();
int thread_cnt+=1;
thread_cnt_mutex.unlock();
int i=start,j=end;
qSort(array,i,j);//сортируем свой кусочек
QSortThread * a=NULL;
QSortThread * b=NULL;
//************
if(start<j)
{
thread_cnt_mutex.lock();
if(thread_cnt<THREADS_MAX && j-start>100500)
{
thread_cnt_mutex.unlock();
a=new QSortThread(array,start,j);
a->start();
}
else
{
thread_cnt_mutex.unlock();
qSort(array,start,j);
}
...
//**********аналогично для второй половины массива
..
if(a)
a->wait();
if(b)
b->wait();
}
thread_cnt_mutex.lock();
int thread_cnt-=1;
thread_cnt_mutex.unlock();
}
...
void gui::sortButtonClick()
{
mysortthread=new QSortThread(array,0,count);
connect(mysortthread,SIGNAL(finished()),this,SLOT(sortFinished()));
mysortthread->start();
}
void gui::sortFinished()
{
//Както так в общем
}
...
Это много не то, но спасибо. Точнее: как и где создать объект QThread с чем-то и как создать один поток из другого.
Цитата: Alm3n
Это много не то, но спасибо.
А что не то то? Распараллеливает же сортировку на несколько потоков.
Цитата: Alm3n
Точнее: как и где создать объект QThread с чем-то
Как хочешь и где хочешь, на сколько фантазии хватит.
Цитата: Alm3n
и как создать один поток из другого.
Создаешь в потоке еще один объект QThread и start вызываешь.
Более конкретно поставь задачу :D Чего ты хочешь добиться то этим?
Ладно, пока ничего не понятно. Может, сейчас начну практически этим заниматься и вопрос более конкретизируется, пока это всё было только в голове. Хотя один вопрос вот есть, но его, наверное, и в документации можно посмотреть: как передать параметры функции, что находится в QThread?
для run() - никак. Параметры делаешь членами наследованного от QThread класса и заполняешь перед вызовом start()
Цитата: arrjj
для run() - никак. Параметры делаешь членами наследованного от QThread класса и заполняешь перед вызовом start()
Получается, что всё-таки придётся делать N-е количество экземпляров?
Хотя вот нашёл какой-то пример распараллеливания с одним экземпляром.
Цитата: Alm3n
Хотя вот нашёл какой-то пример распараллеливания с одним экземпляром.
1 экземпляр QThread = 1 поток, дай ссылку на тот пример.
Тот самый пример
С потоками вроде бы разобрался. Для передачи аргументов сортировке в потоке сигналы же подойдут? Если передавать в сигнале адрес массива и параметры сортировки?
Вообще, вот то, что у меня есть
Как мне кажется, функцию sort нужно перенести в метод run потока. Добавить одним из параметров глубину рекурсии для этой функции, чтобы в процессе сортировки глубина рекурсии сравнивалась с глубиной, где должно происходить распараллеливание и создавались новые потоки. На этом мысли мои заканчиваются. Это же хорошая идея?
С потоками вроде бы разобрался. Для передачи аргументов сортировке в потоке сигналы же подойдут? Если передавать в сигнале адрес массива и параметры сортировки?
Вообще, вот то, что у меня есть
Код:
Как мне кажется, функцию sort нужно перенести в метод run потока. Добавить одним из параметров глубину рекурсии для этой функции, чтобы в процессе сортировки глубина рекурсии сравнивалась с глубиной, где должно происходить распараллеливание и создавались новые потоки. На этом мысли мои заканчиваются. Это же хорошая идея?
Цитата: Alm3n
Код:
...
void MainThread::Run() {
for (int i = 0; i < 3; i++) {
ChildThread *child = new ChildThread(i + 1);//И где тут 1 экземпляр?
...
void MainThread::Run() {
for (int i = 0; i < 3; i++) {
ChildThread *child = new ChildThread(i + 1);//И где тут 1 экземпляр?
...
Цитата: Alm3n
С потоками вроде бы разобрался.
ИМХО почитай на doc.qt.nokia.com статьи по потокам и сигналам/слотам для закрепления понимания.
Цитата: Alm3n
Для передачи аргументов сортировке в потоке сигналы же подойдут?
Пока поток не запущен можно хоть явно членам QThread значения присваивать.
Цитата: Alm3n
Если передавать в сигнале адрес массива и параметры сортировки?
Я так тебе примерно так в своем примере и предложил.
Цитата: Alm3n
Вообще, вот то, что у меня есть
Код:
...
В сорсах еще конь не валялся :D
Цитата: Alm3n
Как мне кажется, функцию sort нужно перенести в метод run потока.
Можно, еслиб алгоритм был линейный, а вызывать run из run'а моветон. Кроме того run не принимает параметры.
Цитата: Alm3n
Добавить одним из параметров глубину рекурсии для этой функции, чтобы в процессе сортировки глубина рекурсии сравнивалась с глубиной, где должно происходить распараллеливание и создавались новые потоки.
ИМХО Распараллеливать надо не по глубине рекурсии а по объемам данных для сортировки.
Цитата: arrjj
...
void MainThread::Run() {
for (int i = 0; i < 3; i++) {
ChildThread *child = new ChildThread(i + 1);//И где тут 1 экземпляр?
...
[/code]
Это я на тот момент ещё в код не вник. :)
Цитата: arrjj
ИМХО почитай на doc.qt.nokia.com статьи по потокам и сигналам/слотам для закрепления понимания.
Сейчас параллельно читаю.
Цитата: arrjj
Пока поток не запущен можно хоть явно членам QThread значения присваивать.
Код:
class MyThread : public QThread
{
Q_OBJECT
T* Buff;
quint32 Size;
public:
MyThread(){}
MyThread(T* B,quint32 S) : Buff(B),Size(S){}
void run()
{
sort(Buff,0,Size-1);
exec();
}
};
{
Q_OBJECT
T* Buff;
quint32 Size;
public:
MyThread(){}
MyThread(T* B,quint32 S) : Buff(B),Size(S){}
void run()
{
sort(Buff,0,Size-1);
exec();
}
};
Так?
Цитата: arrjj
Я так тебе примерно так в своем примере и предложил.
Не очень восприятие кодом. Лучше бы словами. Also, запутало наличие мьютексов. Не планировал с ними делать.
Цитата: arrjj
Можно, еслиб алгоритм был линейный, а вызывать run из run'а моветон. Кроме того run не принимает параметры.
Я планировал где-нибудь в середине функции сортировки создавать новый экземпляр потока и вызывать там. Это "вызывать run из run'а"?
Цитата: arrjj
ИМХО Распараллеливать надо не по глубине рекурсии а по объемам данных для сортировки.
Так глубина же из объёма и высчитывается.
Допустим, если есть 4 потока и массив размером 40, то на втором уровне рекурсии создавать новые потоки, чтобы каждая часть массива была отсортирована одним. Верно?
Цитата: Alm3n
Код:
class MyThread : public QThread
{
Q_OBJECT
T* Buff;
quint32 Size;
public:
MyThread(){}
MyThread(T* B,quint32 S) : Buff(B),Size(S){}
void run()
{
sort(Buff,0,Size-1);
exec();
}
};
{
Q_OBJECT
T* Buff;
quint32 Size;
public:
MyThread(){}
MyThread(T* B,quint32 S) : Buff(B),Size(S){}
void run()
{
sort(Buff,0,Size-1);
exec();
}
};
Так?
Да, тип того.
Цитата: Alm3n
Не очень восприятие кодом. Лучше бы словами. Also, запутало наличие мьютексов. Не планировал с ними делать.
Мютекс там исключительно для изменения глобальной переменной количества из потока. Можно и без него обойтись если реализовывать через QThreadPool (он сам будет считать) и QRunnable (вместо QThread).
Цитата: Alm3n
Я планировал где-нибудь в середине функции сортировки создавать новый экземпляр потока и вызывать там. Это "вызывать run из run'а"?
Нет :) Ты всё правильно думал :) Я просто тебя не так понял.
Цитата: Alm3n
Так глубина же из объёма и высчитывается.
Допустим, если есть 4 потока и массив размером 40, то на втором уровне рекурсии создавать новые потоки, чтобы каждая часть массива была отсортирована одним. Верно?
В теории какбы хорошо, но на практике у тебя эти 4 части массива будут из разного кол-ва элементов состоять. В худшем случае у тебя получится так, что 3 потока будут сортировать массив из 1 элемента, а 4-й из 37. Или вообще до второго уровня рекурсии дойдет лишь одна ветка, остальные еще на 1-м закончатся.
С рекурсией я ещё подумаю, мне бы теперь с шаблонами разобраться. Значит, в правильном направлении иду - это хорошо. Спасибо за советы. Странно. Не могу тебе добавлять репутацию. Постоянно пишет, что перед этим нужно добавить её ещё кому-нибудь.
Вот примерчик. Интересно поиграться с максимальным кол-вом потоков и размером массива для сортировки рекурсивно и понаблюдать в таскманагере кол-во потоков (сейчас у меня в среднем в 25-30 потоков выполняется)
[ATTACH]5580[/ATTACH]
Но т.к. ноутик у меня всего двухядрёный объективно оценить производительность распараллеливания я не могу :)
[ATTACH]5580[/ATTACH]
Но т.к. ноутик у меня всего двухядрёный объективно оценить производительность распараллеливания я не могу :)
Наверное, лучше будет использоваться QRunnable. Он не требует макроса Q_OBJECT. Или всё-таки требует?
Цитата: Alm3n
Наверное, лучше будет использоваться QRunnable. Он не требует макроса Q_OBJECT. Или всё-таки требует?
Не требует. Естественно если производный класс не будешь наследовать от QObject еще.
Если не буду вызывать у QThreadPool метод waitForDone в главном треде, но при этом буду запускать start и сразу же возвращать управление в функцию main(управление вернётся из функции, которая вызывается в main), это чем-нибудь грозит нехорошим? Кроме того, что, если завершится основной поток, все остальные умрут тоже? Не подходит, чтобы Gui ждал возврата из waitForDone, думаю, прикрутить какое-нибудь средство синхронизации, но какое будет лучше? Желательно, чтобы не передавать лишних указателей в функцию сортировки и чтобы ожидание завершения не блокировало Gui.