Вот что у меня получилось.
| Код |
#include <stdlib.h>
#include <windows.h>
#include <iostream>
#include <time.h>
using namespace std;
// массив для сортировки
int *super_array;
// структура для передачи параметров потоку
struct param_RL{
int R, L;
};
CRITICAL_SECTION cs;
CRITICAL_SECTION inc_cs;
int ThreadCount = 0; // содержит текущее число потоков
int MaxThreads = 2; // максимальное число потоков
void m_qsort(int l, int r);
DWORD WINAPI thread_sort(LPVOID lpParameter){
param_RL *p = (param_RL*)lpParameter;
// сортируем в потоке
m_qsort(p->L,p->R);
delete p;
// выходим, уменьшаем счетчик потоков
EnterCriticalSection(&inc_cs);
ThreadCount--;
LeaveCriticalSection(&inc_cs);
ExitThread(0);
return 0;
}
void m_qsort(int l, int r){
int i = l;
int j = r;
int x = super_array[(r + l) /2];
do {
while(super_array[i]<x)
i++;
while(super_array[j]>x)
j--;
if (i<=j){
EnterCriticalSection(&cs);
swap(super_array[i++], super_array[j--]);
LeaveCriticalSection(&cs);
}
}while(i<=j);
if (i < r){
// выбираем метод запуска для сортировки новой части
if (ThreadCount>=MaxThreads){
m_qsort(i,r); // вызываем рекурсию внутри потока
}
else{ // создаем новый поток
EnterCriticalSection(&inc_cs);
ThreadCount++;
LeaveCriticalSection(&inc_cs);
param_RL *p = new param_RL;
p->L=i;
p->R=r;
CreateThread(NULL,0,thread_sort,(PVOID)p,0,0);
}
}
if (l < j){
// выбираем метод запуска для сортировки новой части
if (ThreadCount>=MaxThreads){
m_qsort(l,j);
}
else{
EnterCriticalSection(&inc_cs);
ThreadCount++;
LeaveCriticalSection(&inc_cs);
param_RL *p = new param_RL;
p->L=l;
p->R=j;
CreateThread(NULL,0,thread_sort,(PVOID)p,0,0);
}
}
}
void main(){
InitializeCriticalSection(&cs);
InitializeCriticalSection(&inc_cs);
int n = 1000000; // число элементов
long s1, s2; // для замера времени
super_array=new int[n];
srand((unsigned)time(NULL));
for (int i=0; i<n; i++){
super_array[i]=rand();
// cout<<super_array[i]<<" ";
}
s1=GetTickCount();
// запускаем сортировку
m_qsort(0,n-1);
// ждем завершения всех потоков
while (true){
EnterCriticalSection(&inc_cs);
if (!ThreadCount){
LeaveCriticalSection(&inc_cs);
break;
}
LeaveCriticalSection(&inc_cs);
}
s2=GetTickCount();
//cout<<endl<<endl;
//for (int i=0; i<n; i++){
// cout<<super_array[i]<<" ";
//}
cout<<endl<<endl<<s2-s1<<" ms.";
delete []super_array;
cin.get();
DeleteCriticalSection(&cs);
DeleteCriticalSection(&inc_cs);
}
|
В общем схема такая, как расписал Silent.
| Цитата |
Первый проход будет в однопоточном режиме, массив отсортируется относительно среднего элемента. Потом запускаем по потоку на правую и левую часть, и так рекурсивно, то есть один поток после упорядочивания создает два дочерних потока и завершается. Можно ввести ограничение на количество одновременно выполняемых потоков.
|
Все вроде правильно - верно сортируется массив, работает заданное число потоков. Но вот что я не пойму - почему при чистой рекурсии (если MaxThreads=0) массив сортируется быстрее (загружая на 50% процессор), хотя 2 поточная версия использует каждое ядро и грузит проц на 100%...
Вот данные замеров (число элементов = 10`000`000):
Число спец. потоков для сортировки / время в миллисек.
0 / 13000
2 / 15203
4 / 49250
Вот такая картина. По идее на моем 2-ядерном процессоре, должна быстрее работать версия, которая используется на всю два ядра. Но почему-то выигрывает чисто рекурсивная версия...
Есть мысли?
|
