c - 当我用线程实现合并排序时得到不正确的输出，无法弄清楚出了什么问题

Question

我已经解决这个问题大约 3 天了，我梳理了我的整个代码，试图找出为什么我得到不正确的输出。该程序的目的是使用线程进行合并排序。第一部分只是简单地将元素并行排序为用户输入的多个段。测试的唯一输入将是 2、5 和 10。要排序的数组将始终是 50 int 随机生成的数字数组。输入段时我的代码工作正常(由顶部的变量“段”表示) 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

抱歉，文字太长了，我已经尝试自己解决这个问题，但经过无数次的尝试后，我无法弄清楚。请帮我弄清楚我做错了什么。我认为我的问题在于我加入线程的方式或我的合并函数，但由于我不能确定，所以我只是包括了整个事情。

Answer 1

花了一段时间，但我终于到了那里:)

问题出在这一行:

    int *partition2 = numbers + (i+1 * (size));

这等同于(由于运算符优先级)。

int *partition2 = numbers + (i + size);

这不是你想要的。

应该是:

    int *partition2 = numbers + ((i+1) * (size));

注意额外的括号。没有它，partition2 索引计算不正确。因此，合并数组的不同部分。