当我用线程实现合并排序时得到不正确的输出，无法弄清楚出了什么问题
Getting incorrect output when I implement merge sort with threads, can't figure out what's wrong
我已经解决这个问题大约 3 天了，我梳理了我的整个代码，试图找出为什么我得到不正确的输出。该程序的目的是使用线程进行合并排序。第一部分只是简单地将元素并行排序为用户输入的多个段。测试的唯一输入将是 2、5 和 10。要排序的数组将始终是随机生成的 50 int 数组 numbers.My 当输入段时代码工作正常（由变量 'segments' 表示在 main 的顶部）是 2。但是，当我将段更改为 5 或 10 时，最后我没有得到排序数组。我已经尝试使用 print 语句进行调试（我已将其注释掉，但您仍然可以看到）并且在前两次合并迭代期间似乎存在问题。出于某种原因，这些合并迭代的结果没有按顺序排列，并且它们包含重复的数字，这些数字在传递给它的原始数组中不重复存在。当我只将数组传递给它们并且不使用线程时，我的排序方法和合并方法工作正常，但是当我使用线程时，我会得到无法解释的行为。下面是我的完整程序，要合并一个 50 的数组，它应该执行以下操作：
- 将数组分成 10 段，每段 5 段，并对每个段进行排序。
- 成对地轮流传递片段。因此，第一轮应该在一个段中通过段 0-5，在另一个段中通过段 5-10，10-15 和 15-20、20-25 和 25-30，依此类推，直到达到 40-45 和 45-50。
- 然后它将进入第二轮，与第一轮做同样的事情，但它以 10 对的形式通过段。所以 0-10 和 10-20、20-30 和 30-40，然后它离开10 的最后一部分未受影响
- 第三轮通过分段合并成对 20：0-20 和 20-40，然后停止。
- 最后它应该将段 0-40 与 40-50 合并。
我的程序：（你应该主要关注我的主要功能，排序很好，合并似乎也很好，但我还是把它们包括在内以防万一）
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <pthread.h>
/**
* Struct to contain an array partition as well as the size of the partition.
* Use struct to pass multiple parameters to pthread_create
*/
struct array_struct{
int *partition;
int size;
};
/**
* Struct that contains two arrays (should be sorted) to merge
* Use struct to pass multiple parameters to pthread_create
*/
struct arrays_to_merge{
int *array1;
int *array2;
int size1;
int size2;
};
//comparison function to use with qsort, sorts in ascending order
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
/**
* Method that takes a struct containing a pointer to the first int in an array
* partition, as well as the partition size. Object must be type void, used with pthread_create
* @param pointer to the partition object. Type void
*/
void *sort(void *object){
struct array_struct *structure;
structure = (struct array_struct *) object;
int *array = structure->partition;
int size = structure->size;
int *i, j = 0;
qsort(array, size, sizeof(int), cmpfunc);
printf("Sorted %d elements.\n", size);
}
void *merge(void * object){
struct arrays_to_merge *arrays_struct;
arrays_struct = (struct arrays_to_merge *) object;
int *array1 = arrays_struct->array1;
int *array2 = arrays_struct->array2;
int size1 = arrays_struct->size1;
int size2 = arrays_struct->size2;
int tempArray[size1 + size2];
int i = 0, j = 0, k = 0, duplicates = 0;
while (i < size1 && j < size2) {
// printf("Merge number : %d Comparing %d and %d\n", mergenumber, array1[i], array2[j]);
if (array1[i] <= array2[j]) {
// printf("Picking %d\n", array1[i]);
tempArray[k] = array1[i];
if (array1[i] == array2[j])
{
duplicates++;
}
i++;
k++;
}else {
// printf("Merge number : %d Picking %d\n", mergenumber, array2[j]);
tempArray[k] = array2[j];
k++;
j++;
}
}
while (i < size1) {
// printf("Merge number : %d left over Picking %d\n", mergenumber, array1[i]);
tempArray[k] = array1[i];
i++;
k++;
}
while (j < size2) {
// printf("Merge number : %d left over Picking %d\n", mergenumber, array2[j]);
tempArray[k] = array2[j];
k++;
j++;
}
array1 = arrays_struct->array1;
for(i = 0; i < size1 + size2; i++){
array1[i] = tempArray[i];
}
printf("Merged %d and %d elements with %d duplicates\n", size1, size2, duplicates);
}
//return an array of size 50 with randomly generated integers
int *randomArray(){
srand(time(NULL));
static int array[50];
int i;
for (i = 0; i < 50; ++i){
array[i] = rand() % 51;
}
return array;
}
int main(int argc, char const *argv[])
{
int segments = 10;//make equal to argv input after testing
pthread_t threads[segments];
int i, *numbers; //iterator i, and pointer to int array 'numbers'
numbers = randomArray(); //return an array of random ints and store in 'numbers'
struct array_struct array[segments];
for(i = 0; i < segments; i++){
int *partition = numbers + (i * (50/segments));//obtain the first index of partition
array[i].partition = partition;
array[i].size = 50/segments;
pthread_create(&threads[i], NULL, sort, (void *) &array[i]);
}
for(i = 0; i < segments; i++){
pthread_join(threads[i], NULL);
}
int count = segments;
struct arrays_to_merge arrays[segments];
int j;
int size = 50/ segments;
while(count > 1){
for(i = 0, j = 0; i < count-1; j++, i += 2){
int *partition = numbers + (i * (size));
int *partition2 = numbers + (i+1 * (size));
arrays[j].array1 = partition;
arrays[j].array2 = partition2;
arrays[j].size1 = size;
arrays[j].size2 = size;
pthread_create(&threads[j], NULL, merge, (void *) &arrays[j]);
}
for(i = 0; i < j; i++){
pthread_join(threads[i], NULL);
}
size = size * 2;
count = count/2;
}
if(segments != 2){//for segments = 2, no need for his
int *partition = numbers;
int *partition2 = numbers + (size);
arrays[0].array1 = partition;
arrays[0].array2 = partition2;
arrays[0].size1 = size;
arrays[0].size2 = 50 - size;
pthread_create(&threads[0], NULL, merge, (void *) &arrays[0]);
pthread_join(threads[0], NULL);
}
for(i = 0; i < 50; i++){
printf("%d\n", numbers[i]);
}
pthread_exit(NULL);
return 0;
}
这是我的输出：
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 10 and 10 elements with 3 duplicates
Merged 10 and 10 elements with 1 duplicates
Merged 20 and 20 elements with 7 duplicates
Merged 40 and 10 elements with 17 duplicates
0
6
9
11
12
13
13
14
15
17
19
23
25
25
25
26
26
28
28
28
28
30
32
32
32
34
39
41
41
44
44
44
44
44
50
50
9
15
50
9
15
19
26
50
50
9
15
11
14
50
抱歉，文字太长了，我已经尝试自己解决这个问题，但经过无数次的努力后，我无法弄清楚。请帮我弄清楚我做错了什么。我 认为 我的问题在于我加入线程的方式或我的合并功能，但由于我不能确定，我只是包括了整个事情。
花了一些时间，但终于到了那里:)
这一行有问题：
int *partition2 = numbers + (i+1 * (size));
相当于（由于运算符优先级）。
int *partition2 = numbers + (i + size);
这不是你想要的。
应该是：
int *partition2 = numbers + ((i+1) * (size));
注意额外的括号。没有它， partition2 索引计算不正确。因此，合并与数组的不同部分。
我已经解决这个问题大约 3 天了，我梳理了我的整个代码，试图找出为什么我得到不正确的输出。该程序的目的是使用线程进行合并排序。第一部分只是简单地将元素并行排序为用户输入的多个段。测试的唯一输入将是 2、5 和 10。要排序的数组将始终是随机生成的 50 int 数组 numbers.My 当输入段时代码工作正常（由变量 'segments' 表示在 main 的顶部）是 2。但是，当我将段更改为 5 或 10 时，最后我没有得到排序数组。我已经尝试使用 print 语句进行调试（我已将其注释掉，但您仍然可以看到）并且在前两次合并迭代期间似乎存在问题。出于某种原因，这些合并迭代的结果没有按顺序排列，并且它们包含重复的数字，这些数字在传递给它的原始数组中不重复存在。当我只将数组传递给它们并且不使用线程时，我的排序方法和合并方法工作正常，但是当我使用线程时，我会得到无法解释的行为。下面是我的完整程序，要合并一个 50 的数组，它应该执行以下操作：
- 将数组分成 10 段，每段 5 段，并对每个段进行排序。
- 成对地轮流传递片段。因此，第一轮应该在一个段中通过段 0-5，在另一个段中通过段 5-10，10-15 和 15-20、20-25 和 25-30，依此类推，直到达到 40-45 和 45-50。
- 然后它将进入第二轮，与第一轮做同样的事情，但它以 10 对的形式通过段。所以 0-10 和 10-20、20-30 和 30-40，然后它离开10 的最后一部分未受影响
- 第三轮通过分段合并成对 20：0-20 和 20-40，然后停止。
- 最后它应该将段 0-40 与 40-50 合并。
我的程序：（你应该主要关注我的主要功能，排序很好，合并似乎也很好，但我还是把它们包括在内以防万一）
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <pthread.h>
/**
* Struct to contain an array partition as well as the size of the partition.
* Use struct to pass multiple parameters to pthread_create
*/
struct array_struct{
int *partition;
int size;
};
/**
* Struct that contains two arrays (should be sorted) to merge
* Use struct to pass multiple parameters to pthread_create
*/
struct arrays_to_merge{
int *array1;
int *array2;
int size1;
int size2;
};
//comparison function to use with qsort, sorts in ascending order
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
/**
* Method that takes a struct containing a pointer to the first int in an array
* partition, as well as the partition size. Object must be type void, used with pthread_create
* @param pointer to the partition object. Type void
*/
void *sort(void *object){
struct array_struct *structure;
structure = (struct array_struct *) object;
int *array = structure->partition;
int size = structure->size;
int *i, j = 0;
qsort(array, size, sizeof(int), cmpfunc);
printf("Sorted %d elements.\n", size);
}
void *merge(void * object){
struct arrays_to_merge *arrays_struct;
arrays_struct = (struct arrays_to_merge *) object;
int *array1 = arrays_struct->array1;
int *array2 = arrays_struct->array2;
int size1 = arrays_struct->size1;
int size2 = arrays_struct->size2;
int tempArray[size1 + size2];
int i = 0, j = 0, k = 0, duplicates = 0;
while (i < size1 && j < size2) {
// printf("Merge number : %d Comparing %d and %d\n", mergenumber, array1[i], array2[j]);
if (array1[i] <= array2[j]) {
// printf("Picking %d\n", array1[i]);
tempArray[k] = array1[i];
if (array1[i] == array2[j])
{
duplicates++;
}
i++;
k++;
}else {
// printf("Merge number : %d Picking %d\n", mergenumber, array2[j]);
tempArray[k] = array2[j];
k++;
j++;
}
}
while (i < size1) {
// printf("Merge number : %d left over Picking %d\n", mergenumber, array1[i]);
tempArray[k] = array1[i];
i++;
k++;
}
while (j < size2) {
// printf("Merge number : %d left over Picking %d\n", mergenumber, array2[j]);
tempArray[k] = array2[j];
k++;
j++;
}
array1 = arrays_struct->array1;
for(i = 0; i < size1 + size2; i++){
array1[i] = tempArray[i];
}
printf("Merged %d and %d elements with %d duplicates\n", size1, size2, duplicates);
}
//return an array of size 50 with randomly generated integers
int *randomArray(){
srand(time(NULL));
static int array[50];
int i;
for (i = 0; i < 50; ++i){
array[i] = rand() % 51;
}
return array;
}
int main(int argc, char const *argv[])
{
int segments = 10;//make equal to argv input after testing
pthread_t threads[segments];
int i, *numbers; //iterator i, and pointer to int array 'numbers'
numbers = randomArray(); //return an array of random ints and store in 'numbers'
struct array_struct array[segments];
for(i = 0; i < segments; i++){
int *partition = numbers + (i * (50/segments));//obtain the first index of partition
array[i].partition = partition;
array[i].size = 50/segments;
pthread_create(&threads[i], NULL, sort, (void *) &array[i]);
}
for(i = 0; i < segments; i++){
pthread_join(threads[i], NULL);
}
int count = segments;
struct arrays_to_merge arrays[segments];
int j;
int size = 50/ segments;
while(count > 1){
for(i = 0, j = 0; i < count-1; j++, i += 2){
int *partition = numbers + (i * (size));
int *partition2 = numbers + (i+1 * (size));
arrays[j].array1 = partition;
arrays[j].array2 = partition2;
arrays[j].size1 = size;
arrays[j].size2 = size;
pthread_create(&threads[j], NULL, merge, (void *) &arrays[j]);
}
for(i = 0; i < j; i++){
pthread_join(threads[i], NULL);
}
size = size * 2;
count = count/2;
}
if(segments != 2){//for segments = 2, no need for his
int *partition = numbers;
int *partition2 = numbers + (size);
arrays[0].array1 = partition;
arrays[0].array2 = partition2;
arrays[0].size1 = size;
arrays[0].size2 = 50 - size;
pthread_create(&threads[0], NULL, merge, (void *) &arrays[0]);
pthread_join(threads[0], NULL);
}
for(i = 0; i < 50; i++){
printf("%d\n", numbers[i]);
}
pthread_exit(NULL);
return 0;
}
这是我的输出：
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Sorted 5 elements.
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 5 and 5 elements with 0 duplicates
Merged 10 and 10 elements with 3 duplicates
Merged 10 and 10 elements with 1 duplicates
Merged 20 and 20 elements with 7 duplicates
Merged 40 and 10 elements with 17 duplicates
0
6
9
11
12
13
13
14
15
17
19
23
25
25
25
26
26
28
28
28
28
30
32
32
32
34
39
41
41
44
44
44
44
44
50
50
9
15
50
9
15
19
26
50
50
9
15
11
14
50
抱歉，文字太长了，我已经尝试自己解决这个问题，但经过无数次的努力后，我无法弄清楚。请帮我弄清楚我做错了什么。我 认为 我的问题在于我加入线程的方式或我的合并功能，但由于我不能确定，我只是包括了整个事情。
花了一些时间，但终于到了那里:)
这一行有问题：
int *partition2 = numbers + (i+1 * (size));
相当于（由于运算符优先级）。
int *partition2 = numbers + (i + size);
这不是你想要的。
应该是：
int *partition2 = numbers + ((i+1) * (size));
注意额外的括号。没有它， partition2 索引计算不正确。因此，合并与数组的不同部分。