线程合并排序给出无效结果

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

我得到无效的结果。

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;
}

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

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 没有完全使用（25M 上的 8-8 % 所以只有一个内核）

需要考虑的几点：

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

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

相关内容

最新更新

热门标签：