在c。中写出一个平行的快速排序 [英] Writing a parallel quick sort in c
问题描述
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
#include< pthread.h>
#include< unistd.h> // sleep（）
#include< stdio.h>
#include< stdlib.h> // EXIT_SUCCESS
#include< string.h> // strerror（）
#include< errno.h>
#define SIZE_OF_DATASET 6
void * quickSort（void * data）;
int partition（int * a，int，int）;
struct info {
int start_index;
int * data_set;
int end_index;
};
int main（int argc，char ** argv）
{
int a [] = {7，12， 1，-2,8,2};
pthread_t thread_id;
struct info * info = malloc（sizeof（struct info））;
info-> data_set = malloc（sizeof（int）* SIZE_OF_DATASET）;
info-> data_set = a;
info-> start_index = 0;
info-> end_index = SIZE_OF_DATASET-1;
if（pthread_create（& thread_id，NULL，quickSort，info））{
fprintf（stderr，No threads for you.\\\
）;
return 1;
}
pthread_join（thread_id，NULL）;
printf（\\\
\\\
Sorted array is：）;
int i; （i = 0; i< SIZE_OF_DATASET; ++ i）
printf（％d，info-> data_set [i]）;
return 0;
}
void * quickSort（void * data）
{
struct info * info = data;
int j，l，r;
l = info-> start_index;
r = info-> end_index;
pthread_attr_t attr;
pthread_t thread_id1;
pthread_t thread_id2;
pthread_attr_init（& attr）;
if（l
j = partition（info-> data_set，l，r）;
info-> start_index = l;
info-> end_index = j-1;
if（info-> end_index< 0）info-> end_index = 0;
if（pthread_create（& thread_id1，NULL，quickSort，info））{
fprintf（stderr，No threads for you.\\\
）;
返回NULL;
}
info-> start_index = j + 1;
info-> end_index = r;
if（pthread_create（& thread_id2，NULL，quickSort，info））{
fprintf（stderr，No threads for you.\\\
）;
返回NULL;
}
pthread_join（thread_id1，NULL）;
pthread_join（thread_id2，NULL）;
}
返回NULL;
}
int分区（int * a，int l，int r）{
int pivot，i，j，t;
pivot = a [l];
i = l; j = r + 1;
while（1）
{
do ++ i;而（a [i]< = pivot&& i< = r）;
do --j;而（a [j]>枢轴）;
if（i> = j）break;
t = a [i]; a [i] = a [j]; a [j] = t;
}
t = a [l]; a [l] = a [j]; a [j] = t;
return j;
}
但是，快速排序功能只能调用第一个线程。不明白这里发生了什么。
注意：串口版本的代码已经过测试。没有问题
更新：
这是基于John的修改版本布林格的解决方案但是在quicksort里面新创建的线程采取的数组的后半部分并不排序。
int main（int argc，char ** argv）
{
int a [] = {7，12，1，-2，0，15，4，11，9,5,3,24,5,23,3,1,56,8,4,32,23,51};
struct info * info = malloc（sizeof（struct info））;
info-> data_set = malloc（sizeof（int）* SIZE_OF_DATASET）;
info-> data_set = a;
info-> start_index = 0;
info-> end_index = SIZE_OF_DATASET-1;
quickSort（info）;
printf（\\\
\\\
Sorted array is：）;
int i; （i = 0; i< SIZE_OF_DATASET; ++ i）
printf（％d，info-> data_set [i]）;
return 0;
}
void * quickSort（void * data）
{
struct info * info = data;
struct info * info1 = data;
int j，l，r;
l = info-> start_index;
r = info-> end_index;
pthread_attr_t attr;
pthread_t thread_id1;
pthread_attr_init（& attr）;
if（l
j = partition（info-> data_set，l，r）;
info1-> start_index = j + 1;
info1-> end_index = r;
info1> data_set = info-> data_set;
if（info1-> end_index< 0）info1-> end_index = 0;
if（pthread_create（& thread_id1，NULL，quickSort，info1））{
fprintf（stderr，No threads for you.\\\
）;
返回NULL;
}
info-> start_index = l;
info-> end_index = j-1;
if（info-> end_index< 0）info-> end_index = 0;
quickSort（info）; / *不关心返回值* /
pthread_join（thread_id1，NULL）;
}
返回NULL;
}
程序是不正确的，因为你的线程都共享相同的 struct info 结构，描述他们应该在工作的子问题。它们同时运行（或者可以做），并且它们在进行时修改该结构，所以任何特定线程看到的值是不确定的。
为了解决这个问题， quickSort 框架必须至少创建一个新的 struct info ，以便两个 quickSort（） 调用它在不同的线程中每个都有自己的。作为一个效率问题，在每个 quickSort（）调用中只能生成一个线程。例如：
void * quickSort（void * data）
{
struct info * info = data ;
struct info other_info;
/ * ... * /
/ *启动一个新线程来处理一个分区：* /
other_info.start_index = j + 1;
other_info.end_index = r;
other_info.data_set = info-> data_set;
if（pthread_create（& thread_id1，NULL，quickSort，& other_info））{
fprintf（stderr，No threads for you.\\\
）;
返回NULL;
}
/ *处理当前线程中的其他分区：* /
info-> start_index = l;
info-> end_index = j - 1;
if（info-> end_index< 0）info-> end_index = 0;
quickSort（info）; / *不关心返回值* /
/ *在这个线程完成后，等待另一个线程完成* /
pthread_join（thread_id1，NULL）;
/ * ... * /
}
注意这不能确保任何特定的一对线程并行运行，既不在多核心意义上也不在时间切片的意义上。这取决于操作系统。然而，当然，多核的并行意义仅适用于主机上实际上有多个核心可用于操作系统愿意安排您的进程的地方。
I need to write a parallel quick sort in c using pthreads. This is what I did so far.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <unistd.h> // sleep()
#include <stdio.h>
#include <stdlib.h> // EXIT_SUCCESS
#include <string.h> // strerror()
#include <errno.h>
#define SIZE_OF_DATASET 6
void* quickSort( void* data);
int partition( int* a, int, int);
struct info {
int start_index;
int* data_set;
int end_index;
};
int main(int argc, char **argv)
{
int a[] = { 7, 12, 1, -2,8,2};
pthread_t thread_id;
struct info *info = malloc(sizeof(struct info));
info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
info->data_set=a;
info->start_index=0;
info->end_index=SIZE_OF_DATASET-1;
if (pthread_create(&thread_id, NULL, quickSort, info)) {
fprintf(stderr, "No threads for you.\n");
return 1;
}
pthread_join(thread_id, NULL);
printf("\n\nSorted array is: ");
int i;
for(i = 0; i < SIZE_OF_DATASET; ++i)
printf(" %d ", info->data_set[i]);
return 0;
}
void* quickSort( void *data)
{
struct info *info = data;
int j,l,r;
l = info->start_index;
r = info->end_index;
pthread_attr_t attr;
pthread_t thread_id1;
pthread_t thread_id2;
pthread_attr_init(&attr);
if( l < r )
{
j = partition( info->data_set, l, r);
info->start_index=l;
info->end_index=j-1;
if(info->end_index<0)info->end_index=0;
if (pthread_create(&thread_id1, NULL, quickSort, info)) {
fprintf(stderr, "No threads for you.\n");
return NULL;
}
info->start_index=j+1;
info->end_index=r;
if (pthread_create(&thread_id2, NULL, quickSort, info)) {
fprintf(stderr, "No threads for you.\n");
return NULL;
}
pthread_join(thread_id1, NULL);
pthread_join(thread_id2, NULL);
}
return NULL;
}
int partition( int* a, int l, int r) {
int pivot, i, j, t;
pivot = a[l];
i = l; j = r+1;
while( 1)
{
do ++i; while( a[i] <= pivot && i <= r );
do --j; while( a[j] > pivot );
if( i >= j ) break;
t = a[i]; a[i] = a[j]; a[j] = t;
}
t = a[l]; a[l] = a[j]; a[j] = t;
return j;
}
But inside quick sort function only call first thread only. Cant understand what is been happening here.
Note : serial version of code has been tested. no issue with that
UPDATE:
This is modified version based on John Bollinger's solution. But still second half of array which is taken by newly created thread inside quicksort is not sorted.
int main(int argc, char **argv)
{
int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9,5,3,24,5,23,3,1,56,8,4,34,23,51};
struct info *info = malloc(sizeof(struct info));
info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
info->data_set=a;
info->start_index=0;
info->end_index=SIZE_OF_DATASET-1;
quickSort(info);
printf("\n\nSorted array is: ");
int i;
for(i = 0; i < SIZE_OF_DATASET; ++i)
printf(" %d ", info->data_set[i]);
return 0;
}
void* quickSort( void *data)
{
struct info *info = data;
struct info *info1 = data;
int j,l,r;
l = info->start_index;
r = info->end_index;
pthread_attr_t attr;
pthread_t thread_id1;
pthread_attr_init(&attr);
if( l < r )
{
j = partition( info->data_set, l, r);
info1->start_index=j+1;
info1->end_index=r;
info1->data_set = info->data_set;
if(info1->end_index<0)info1->end_index=0;
if (pthread_create(&thread_id1, NULL, quickSort, info1)) {
fprintf(stderr, "No threads for you.\n");
return NULL;
}
info->start_index=l;
info->end_index=j-1;
if(info->end_index < 0) info->end_index = 0;
quickSort(info); /* don't care about the return value */
pthread_join(thread_id1, NULL);
}
return NULL;
}
The program is incorrect because your threads all share the same struct info structure describing the sub-problem they are supposed to be working on. They run concurrently (or may do, anyway) and they modify that structure as they proceed, so the values that any particular thread sees are indeterminate.
To resolve this, each quickSort frame must create at least one new struct info, so that the two quickSort() calls it makes in different threads each has its own. As a matter of efficiency, it would also be better to spawn only one additional thread in each quickSort() call. For example:
void* quickSort( void *data)
{
struct info *info = data;
struct info other_info;
/* ... */
/* launch a new thread to handle one partition: */
other_info.start_index = j + 1;
other_info.end_index = r;
other_info.data_set = info->data_set;
if (pthread_create(&thread_id1, NULL, quickSort, &other_info)) {
fprintf(stderr, "No threads for you.\n");
return NULL;
}
/* handle the other partition in the current thread: */
info->start_index = l;
info->end_index = j - 1;
if(info->end_index < 0) info->end_index = 0;
quickSort(info); /* don't care about the return value */
/* after this thread is done, wait for the other thread to finish, too */
pthread_join(thread_id1, NULL);
/* ... */
}
Note that this does not ensure that any particular pair of threads runs concurrently, neither in a multi-core sense nor in a time-slicing sense. That's up to the OS. Certainly, however, the multi-core sense of parallelism applies only where there are in fact multiple cores available on the host machine on which the OS is willing to schedule your process.
这篇关于在c。中写出一个平行的快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
