c++ - 需要有关多线程合并排序的建议

Question

基本上，如果合并排序中的列表数量等于计算机中的核心数量，它将产生一个线程来对每个列表进行排序。它目前有效，但我面临的问题是它实际上比正常的合并排序花费更长的时间进行排序。它需要更长的时间，因为它不是同时产生 4 个线程，而是产生一个线程，它会在继续调用下一个线程之前经历整个过程。下面是我写的代码，它可以工作，但由于我上面提到的问题，它又变慢了。如果有人熟悉在排序算法中使用线程，我们将不胜感激任何反馈。此外，这不是家庭作业，我的类项目是设计一个普通的合并排序，我只是想尝试使用这种语言并尝试不同的东西。

void MergeSortThreading(int low, int high, int* source, int* destination, int count)
{
if (low == high)
    return;
int mid = (low + high) / 2;
int start_1 = low, end_1 = mid, start_2 = (mid + 1), end_2 = high, dest = start_1;

if (pow(2, count) == cores())
{
    thread* processes = new thread[cores()];
    int j = 1;
    for (int i = 0; i < cores(); i++)
    {
        processes[i] = thread(MergeSortThreading, j, (j + (high)), destination, source, 1000);
        j += (high - 1);
    }

    for (int i = 0; i < cores(); i++)
        processes[i].join();
}

MergeSortThreading(low, mid, destination, source, ++count);
MergeSortThreading((mid + 1), high, destination, source, 150);

while (start_1 <= end_1 && start_2 <= end_2)
{
    if (source[start_1] > source[start_2])
        destination[dest++] = source[start_2++];
    else
        destination[dest++] = source[start_1++];
}

if (start_1 > end_1)
{
    for (; start_2 <= end_2; start_2++)
    {
        destination[dest] = source[start_2];
        dest++;
    }
}
else
{
    for (; start_1 <= end_1; start_1++)
    {
        destination[dest] = source[start_1];
        dest++;
    }
}

Answer 1

一种非常简单的并行化递归的方法，在每一步都分成两部分，结构如下:

void recursive_function(int threads_to_use)
{
    if(threads_to_use == 1) {
        recursive_function(1);
        recursive_function(1);
    } else {
        int half = threads_to_use / 2;
        thread th(recursive_function, half);
        recursive_function(threads_to_use - half);
        th.join();
    }
}

这不是理想的解决方案，但它是一个不错的解决方案，并且如果两个调用可以同时完成，则相对容易附加到现有的单线程设计上。

如果您的 C++ 库提供了一个很好的实现，那么使用 std::async 进行异步函数调用可能比创建低级线程更好……但是我我用过的并不是那么有用(要么创建太多线程，要么根本不使用多线程)，所以我真的不建议尝试学习使用它。