c - 使用 C 中的 pthread 库为大数组开发合并排序

Question

我在作业中被要求根据下图所示的算法开发一个并行合并排序程序，对于任何数组大小 N=2^M (20 <= M <= 28 ) 和任何 K (1 <= K <= 5)。该图显示了 K=3 的示例。

我必须使用 Linux pthread 库用 C(不是 C++)编写程序。

而且我必须对图中的排序模块使用mergesort算法。

M 和 K 都是 main() 函数的输入命令行参数，例如，

./a.out  20  3 

到目前为止，我编写了以下程序:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

#define REP 3
#define MAX 50

//K
unsigned int K;

//input array
int* values;
unsigned int N;

//sorted array
int* sorted;

using namespace std;

//input of thread functions. position of the array for that thread.
typedef struct Arr {
   int low;
   int high;
} ArrayIndex;


void fillarray(int* data, unsigned int N)
{
    unsigned int i;
    for (i = 0; i < N; i++)
        data[i] = rand();
}



void *pms(void *a)
{
        ArrayIndex *pa = (ArrayIndex *)a;
        partition (values, pa->low,pa->high);
        return 0;
}



void partition(int *arr,int low,int high){

    int mid;
    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

void check(){

    unsigned int i;
    for (i = 0; i <= N-2; i++)
        if (sorted[i] > sorted[i+1]) {
            printf("ERROR %d %d %d", i, sorted[i], sorted[i+1]);
            return;
        }

    printf("CORRECT\n");
}



int main( int argc, char *argv[] )
{
    int thread;
    // N = 2 ^ M
    long M = stol(argv[1]);
    N = (unsigned int) pow (2.0, M);

    // K
    K = (unsigned int) stoi(argv[2]) ;
    //test N and K:
    printf("N=%d K=%d\n", N, K);

    int thread_count = pow(2 ,K);
    ArrayIndex ai[thread_count];

    int i=0;
    for(i =0; i <thread_count; i++)
    {
        ai[i].low = i * (N / thread_count);
        ai[i].high = (i + 1) * (N / thread_count);
    }


    pthread_t* thread_handles;
    thread_handles = malloc(thread_count * sizeof(pthread_t));


    srand(time(0));

    time_t t1, t2;
    double dt; //t2-t1
    double tavg=0.0;

    //input array
    values = (int*) malloc ( sizeof(int) * N );

    int r; 
    for (r = 0; r < REP; r++)
    {
        //fill in the input array with random numbers
        fillarray(values, N);

        //t1
        t1 = time(0);

        //sort the array
        //parallel merge sort 


        thread=0;

        for(thread; thread<thread_count; thread++)
        {
            pthread_create(&thread_handles[thread], NULL, pms, &ai[thread]);
        }
        thread=0;
        for(thread=0; thread<thread_count; thread++)
        {
        pthread_join(thread_handles[thread], NULL);
        }


        //t2
            t2 = time(0);

        //t2-t1
            dt = t2 - t1;

        //average time
            tavg += (dt / REP);

        //check for correctness
            check();
    }

    printf ( "%g seconds\n", tavg );

    return 0;
}

到目前为止我的方法是否正确？

这是我想编译我的程序时的输出:

user@sharifvm:~/the04a$ gcc -O2 -pthread  msort.c -lm
msort.c:45:6: warning: conflicting types for âpartitionâ [enabled by default]
 void partition(int *arr,int low,int high){
      ^
msort.c:39:3: note: previous implicit declaration of âpartitionâ was here
   partition (values, pa->low,pa->high);
   ^
msort.c:56:6: warning: conflicting types for âmergeSortâ [enabled by default]
 void mergeSort(int arr[],int low,int mid,int high){
      ^
msort.c:52:10: note: previous implicit declaration of âmergeSortâ was here
          mergeSort(arr,low,mid,high);
          ^
/tmp/ccCKc6qF.o: In function `main':
msort.c:(.text.startup+0x1e): undefined reference to `stol'
msort.c:(.text.startup+0x62): undefined reference to `stoi'
collect2: error: ld returned 1 exit status
user@sharifvm:~/the04a$

stol 和 stoi 函数有什么问题？

请同时检查算法。我只有 3 个小时来完成这个家庭单词:(

我该怎么做才能使其在内存和速度方面更有效率？

提前致谢。

Answer 1

这应该在评论中，但我没有太多的声誉来发表评论。

您不能将命令行参数直接作为 int。但是您可以使用以下语句将字符串转换为整数 -

int N = (int) strtol(M,(char **)NULL,10);

添加string.h库