0

我创建了一个适用于非重复整数数组的合并排序。我正在尝试制作相同的多线程版本。

我得到了无效的结果。

void mergesort(int data[ ], size_t n)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray

    if (n > 1)
    {
        // Compute sizes of the subarrays.
        n1 = n / 2;
        n2 = n - n1;

        mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        mergesort((data + n1), n2);  // Sort from data[n1] to the end

        // Merge the two sorted halves.
        merge(data, n1, n2);
    }
}

DWORD WINAPI threadedmergesort(LPVOID params)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray
    Params* parameters = (Params*) params;
    if (parameters->size > 1)
    {
        // Compute sizes of the subarrays.
        n1 = parameters->size / 2;
        n2 = parameters->size - n1;

        Params* p1 = new Params(parameters->dataArray, n1);
        //mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        Params* p2 = new Params(parameters->dataArray, n2);
        //mergesort((data + n1), n2);  // Sort from data[n1] to the end
        HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
        WaitForSingleObject(h1, INFINITE);
        WaitForSingleObject(h2, INFINITE);

        // Merge the two sorted halves.
        merge(parameters->dataArray, n1, n2);
    }
    return (DWORD)0x0; //null
}

struct Params
{
    int* dataArray;
    int size;
    Params(int _dataArray[], int _size);
};
Params::Params(int _dataArray[], int _size)
{
    dataArray = _dataArray;
    size = _size;
}

有人可以评论为什么我会使用合并排序的线程版本得到无效的结果，以及我可以做些什么来纠正这个问题？

4

2 回答 2

1 
Params* p1 = new Params(parameters->dataArray, n1);
//mergesort(data, n1);         // Sort from data[0] through data[n1-1]
HANDLE h1 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);
Params* p2 = new Params(parameters->dataArray, n2);
//mergesort((data + n1), n2);  // Sort from data[n1] to the end
HANDLE h2 = CreateThread(NULL, 0, threadedmergesort, (LPVOID)p1, 0, NULL);

看起来您将 p1 两次发送到合并排序器。因此，您只是对列表的前半部分进行排序。改变你的第二个参数，一切都应该是正确的。

我的合并排序如下所示：

DWORD WINAPI Mergesorter::mergesort_MT(LPVOID param)
{
    Mergesort_Params* i_mergesortParams = (Mergesort_Params*)param;
    unsigned int half = i_mergesortParams->numberOfValues / 2;
    DWORD threadId[2] = {0,0};
    HANDLE h[2];
    Mergesort_Params* mergesortParams;

    if(i_mergesortParams->numberOfValues > 1)
    {
        mergesortParams = new Mergesort_Params[2];
        mergesortParams[0].l_list = i_mergesortParams->l_list;
        mergesortParams[1].l_list = i_mergesortParams->l_list + half;
        mergesortParams[0].numberOfValues = half;
        mergesortParams[1].numberOfValues = i_mergesortParams->numberOfValues - half;

        h[0] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[0],0,&threadId[0]);
        //WaitForSingleObject(h[0],INFINITE);
        h[1] = CreateThread(0,0,mergesort_MT,(void*)&mergesortParams[1],0,&threadId[1]);        
        //WaitForSingleObject(h[1],INFINITE);
        WaitForMultipleObjects(2,h,TRUE,INFINITE);
        merge_ST(i_mergesortParams->l_list,half,i_mergesortParams->numberOfValues - half);


    }

//delete threadId;
//delete h;
//delete mergesortParams;

return 0;
}

你解决了你的问题吗？现在我的问题是，我无法对足够的值进行排序 100000 太多（单线程没问题）并且我的 CPU 没有完全使用（我的 A8-3500M 上 25%，所以只有一个核心）

于 2012-06-16T13:27:14.520 回答
0

需要考虑的几点：

  1. 不要使用CreateThread，beginThreadEx而是使用，请参阅 MSDN 了解更多信息。
  2. 正如 TOAOGG 已经指出的那样，您有数据竞争，因为多个线程访问同一内存，并且您没有同步。
  3. 您应该使用操作系统线程池而不是显式创建自己的线程。由于这是一种递归算法，因此对于较大的数据集，您将面临耗尽系统资源的风险。每个线程在用户空间中获得 1MB 的默认堆栈大小（不确定，但我认为内核空间中还有另外 1MB），因此对于 32 位进程，您将很快撞到那堵墙。另外，快速创建新线程会产生大量开销，这将减少您在此处想要的任何并发收益。请参阅SubmitThreadPoolWork 和相关 API

使用线程池 API 的另一种替代方法是使用 OpenMP 在 C++ 中执行并行 for 循环。Visual Studio 2008 及更高版本支持该选项（当然还有英特尔编译器）。

于 2012-06-16T13:49:28.133 回答