c - 合并排序与 C 中的 PThreads
问题描述
旁注:我开始学习如何使用 pthreads,并且开始了解这个概念。我一直在这里使用这个示例脚本(用 C++ 编写)来管理带有线程的合并排序:https ://www.geeksforgeeks.org/merge-sort-using-multi-threading/
由于我是用 C 而不是 C++ 编写自己的合并排序,因此我重写了这个示例脚本来测试并注意到一个问题。MAX 20
我决定使用 15 个元素,而不是20 个元素的数组。我注意到排序/合并是无效的(但有点接近),我不知道为什么......此外,我已经更改了要使用的代码不同数量的线程而不是,THREAD_MAX 4
所以我可以将其更改为 5 或 10 个线程。
会不会是 Merge 产生了无效的结果?我在 main() 中对它进行了评论。
我的 C++ 到 C 转换如下:
#include <pthread.h>
#include <time.h>
#include <stdlib.h>
// number of elements in array
#define MAX 15
// number of threads
#define THREAD_MAX 4
//using namespace std;
// array of size MAX
int a[MAX];
int part = 0;
// merge function for merging two parts
void merge(int low, int mid, int high)
{
int* left = (int*) malloc( (mid - low + 1) * sizeof(int));
int* right = (int*) malloc( (high - mid) * sizeof(int));
// n1 is size of left part and n2 is size
// of right part
int n1 = mid - low + 1,
n2 = high - mid,
i, j;
// storing values in left part
for (i = 0; i < n1; i++)
left[i] = a[i + low];
// storing values in right part
for (i = 0; i < n2; i++)
right[i] = a[i + mid + 1];
int k = low;
i = j = 0;
// merge left and right in ascending order
while (i < n1 && j < n2) {
if (left[i] <= right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
}
// insert remaining values from left
while (i < n1) {
a[k++] = left[i++];
}
// insert remaining values from right
while (j < n2) {
a[k++] = right[j++];
}
free(left);
free(right);
}
// merge sort function
void merge_sort(int low, int high)
{
// calculating mid point of array
int mid = low + (high - low) / 2;
if (low < high) {
// calling first half
merge_sort(low, mid);
// calling second half
merge_sort(mid + 1, high);
// merging the two halves
merge(low, mid, high);
}
}
// thread function for multi-threading
void* merge_sort123(void* arg)
{
// which part out of 4 parts
int thread_part = part++;
// calculating low and high
int low = thread_part * (MAX / THREAD_MAX);
int high = (thread_part + 1) * (MAX / THREAD_MAX) - 1;
// evaluating mid point
int mid = low + (high - low) / 2;
if (low < high) {
merge_sort(low, mid);
merge_sort(mid + 1, high);
merge(low, mid, high);
}
return 0;
}
// Driver Code
int main()
{
// generating random values in array
for (int i = 0; i < MAX; i++){
a[i] = rand() % 100;
// printf("%d ", a[i]);
}
pthread_t threads[THREAD_MAX];
// creating 4 threads
for (int i = 0; i < THREAD_MAX; i++)
pthread_create(&threads[i], NULL, merge_sort123,
(void*)NULL);
// joining all 4 threads
for (int i = 0; i < THREAD_MAX; i++)
pthread_join(threads[i], NULL);
///////////////////////////////////////////////////////////////
// --- THIS MAY BE THE PART WHERE THE MERGING IS INVALID --- //
///////////////////////////////////////////////////////////////
// merging the final 4 parts
merge(0, (MAX / 2 - 1) / 2, MAX / 2 - 1);
merge(MAX / 2, MAX/2 + (MAX-1-MAX/2)/2, MAX - 1);
merge(0, (MAX - 1)/2, MAX - 1);
// displaying sorted array
printf("\n\nSorted array: ");
for (int i = 0; i < MAX; i++)
printf ("%d ", a[i]);
printf("\n");
return 0;
}
解决方案
正如我在顶部评论中提到的,原始代码存在一些问题。
上述比赛条件。
delete
底部的[看似]缺失merge
数组元素的数量必须是线程数的倍数。如果不是,最后一个线程的范围将被错误计算。
主线程中的最终合并是固定/硬连线的 4 个线程。
一个通用的解决方案是可能的。但是,除非数组大小非常大,否则它不会节省大量时间,所以它主要用于多线程练习[我相信这是你想要的]。请参阅:多线程快速排序或合并排序
使用控制结构将多个参数传递给线程更容易。一般来说,这是多线程的好技术。
主线程可以使用每个线程的数组范围预填充它。它稍后可以使用这些控制结构来概括最终的合并。
这是适用于任意数组大小和任意数量线程的清理版本:
#include <stdio.h>
#include <pthread.h>
#include <time.h>
#include <stdlib.h>
int opt_a;
int opt_t;
int opt_r;
// number of elements in array
//#define MAX 15
//#define MAX 16
int MAX;
// number of threads
//#define THREAD_MAX 4
int THREAD_MAX;
//using namespace std;
// array of size MAX
int *a;
// thread control parameters
struct tsk {
int tsk_no;
int tsk_low;
int tsk_high;
};
// merge function for merging two parts
void
merge(int low, int mid, int high)
{
// n1 is size of left part and n2 is size of right part
int n1 = mid - low + 1;
int n2 = high - mid;
int *left = malloc(n1 * sizeof(int));
int *right = malloc(n2 * sizeof(int));
int i;
int j;
// storing values in left part
for (i = 0; i < n1; i++)
left[i] = a[i + low];
// storing values in right part
for (i = 0; i < n2; i++)
right[i] = a[i + mid + 1];
int k = low;
i = j = 0;
// merge left and right in ascending order
while (i < n1 && j < n2) {
if (left[i] <= right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
}
// insert remaining values from left
while (i < n1)
a[k++] = left[i++];
// insert remaining values from right
while (j < n2)
a[k++] = right[j++];
free(left);
free(right);
}
// merge sort function
void
merge_sort(int low, int high)
{
// calculating mid point of array
int mid = low + (high - low) / 2;
if (low < high) {
// calling first half
merge_sort(low, mid);
// calling second half
merge_sort(mid + 1, high);
// merging the two halves
merge(low, mid, high);
}
}
// thread function for multi-threading
void *
merge_sort123(void *arg)
{
struct tsk *tsk = arg;
int low;
int high;
// calculating low and high
low = tsk->tsk_low;
high = tsk->tsk_high;
// evaluating mid point
int mid = low + (high - low) / 2;
if (low < high) {
merge_sort(low, mid);
merge_sort(mid + 1, high);
merge(low, mid, high);
}
return 0;
}
// Driver Code
int
main(int argc, char **argv)
{
char *cp;
struct tsk *tsk;
--argc;
++argv;
MAX = 15;
THREAD_MAX = 4;
// use new/general algorithm by default
opt_a = 1;
for (; argc > 0; --argc, ++argv) {
cp = *argv;
if (*cp != '-')
break;
switch (cp[1]) {
case 'M': // array count
MAX = atoi(cp + 2);
break;
case 'T': // thread count
THREAD_MAX = atoi(cp + 2);
break;
case 'a': // change algorithm
opt_a = !opt_a;
break;
case 'r': // do _not_ use rand -- use linear increment
opt_r = !opt_r;
break;
case 't': // tracing
opt_t = !opt_t;
break;
default:
break;
}
}
// allocate the array
a = malloc(sizeof(int) * MAX);
// generating random values in array
if (opt_t)
printf("ORIG:");
for (int i = 0; i < MAX; i++) {
if (opt_r)
a[i] = MAX - i;
else
a[i] = rand() % 100;
if (opt_t)
printf(" %d", a[i]);
}
if (opt_t)
printf("\n");
pthread_t threads[THREAD_MAX];
struct tsk tsklist[THREAD_MAX];
int len = MAX / THREAD_MAX;
if (opt_t)
printf("THREADS:%d MAX:%d LEN:%d\n", THREAD_MAX, MAX, len);
int low = 0;
for (int i = 0; i < THREAD_MAX; i++, low += len) {
tsk = &tsklist[i];
tsk->tsk_no = i;
if (opt_a) {
tsk->tsk_low = low;
tsk->tsk_high = low + len - 1;
if (i == (THREAD_MAX - 1))
tsk->tsk_high = MAX - 1;
}
else {
tsk->tsk_low = i * (MAX / THREAD_MAX);
tsk->tsk_high = (i + 1) * (MAX / THREAD_MAX) - 1;
}
if (opt_t)
printf("RANGE %d: %d %d\n", i, tsk->tsk_low, tsk->tsk_high);
}
// creating 4 threads
for (int i = 0; i < THREAD_MAX; i++) {
tsk = &tsklist[i];
pthread_create(&threads[i], NULL, merge_sort123, tsk);
}
// joining all 4 threads
for (int i = 0; i < THREAD_MAX; i++)
pthread_join(threads[i], NULL);
// show the array values for each thread
if (opt_t) {
for (int i = 0; i < THREAD_MAX; i++) {
tsk = &tsklist[i];
printf("SUB %d:", tsk->tsk_no);
for (int j = tsk->tsk_low; j <= tsk->tsk_high; ++j)
printf(" %d", a[j]);
printf("\n");
}
}
// merging the final 4 parts
if (opt_a) {
struct tsk *tskm = &tsklist[0];
for (int i = 1; i < THREAD_MAX; i++) {
struct tsk *tsk = &tsklist[i];
merge(tskm->tsk_low, tsk->tsk_low - 1, tsk->tsk_high);
}
}
else {
merge(0, (MAX / 2 - 1) / 2, MAX / 2 - 1);
merge(MAX / 2, MAX / 2 + (MAX - 1 - MAX / 2) / 2, MAX - 1);
merge(0, (MAX - 1) / 2, MAX - 1);
}
// displaying sorted array
printf("\n\nSorted array:");
for (int i = 0; i < MAX; i++)
printf(" %d", a[i]);
printf("\n");
return 0;
}
推荐阅读
- java - Selenium Cucumber 功能文件在 Eclipse 中未启用
- ruby-on-rails - Rails 中的急切加载多态关联(包括清晰的代码示例)
- mysql - 检查失败时阻止插入
- ruby - 基于Ruby中的背景颜色反转前景色(文本颜色)
- powershell - 在 if 语句中检查 $null
- git - 创建分支和进行软重置之间的区别?回到旧工作版本的最佳方法是什么?
- python - Heroku 应用程序在邮递员访问 django api 时出现 503 服务不可用错误
- c# - 实体框架缓慢的第一个数据库连接
- javascript - 有人可以解释 createStore 函数以及如何将计数器函数传递给它使其了解状态吗?
- c# - 获取具有某些特定条件的行