主页 / 问题 / 1271290
Accepted
Rikitikitavi
Asked:2022-04-17 17:25:52 +0000 UTC2022-04-17 17:25:52 +0000 UTC

并行执行快速排序

  • 772

这是快速排序的实现：

template<class iterator>
void qsort(iterator begin, iterator end)
{
    if (begin == end)
        return;

    const auto distance = std::distance(begin, end);
    iterator p = std::next(begin, distance / 2);
    iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
    iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});

    qsort(begin, it1);
    qsort(it2,  end);
}

我想实现这个算法的并行执行。你当然可以这样做：

template<class iterator>
void qsort(iterator begin, iterator end)
{
    if (begin == end)
        return;

    const auto distance = std::distance(begin, end);
    iterator p = std::next(begin, distance / 2);
    iterator it1 = std::partition(begin, end, [&p](const auto& v){ return v < *p;});
    iterator it2 = std::partition(it1, end, [&p](const auto& v) { return !(v > *p);});

    std::thread t1(qSort<Iterator>, begin, middle1);
    std::thread t2(qSort<Iterator>, middle2, end);

    t1.join();
    t2.join();
}

但这显然远非最佳实现。线程数将是log(n)。

问题：如何正确实现多线程快速排序算法？您可以编写一个限制线程数的类并将其传递给函数，但标准实现std::sort可以在多个线程中执行，而它的签名不会改变，我想实现类似的东西。

c++

2 个回答

  1. Best Answer

    要解决签名的问题，只需不要向用户显示带有附加参数的函数，并且客户端应该使用的函数应该与现在具有相同的签名：

    template<class iterator>
void qsort(iterator begin, iterator end)
{
  qsort_internal(begin, end, 4);
}

template<class iterator>
void qsort_internal(iterator begin, iterator end, int max_threads)
{

  ...
  if (max_threads > 1) {
    //сортируем многопоточно
    // но уменьшаем max_threads в рекурсивном вызове
  } else {
    // сортируем в этом же потоке 
  }

}

    您需要了解，这种幼稚的实现很可能不会带来特别的增加，但很可能会更慢，甚至在小型阵列上会明显变慢。看这里，与通过并行化加速算法，特别是加速快速排序相关的问题和困难已经被反复讨论过。

    • 4

  2. 对于此类任务，通常使用具有固定数量线程（其实现之一）的线程池，在性能方面将任务添加到池中相当于在最坏的情况下锁定互斥锁。

    并行算法的标准实现通常使用对用户隐藏的（全局）线程池。或者 OpenMP，其实现也使用线程池，但可能会使用一些额外的平台功能。

    您可以找到使用 std::async 进行排序的示例，它也可以使用全局线程池。但在实践中，标准库的实现可能会创建一个新线程而不是使用池，这使得这毫无意义。

    如果我们专门讨论排序，您不太可能接近标准实现。此类算法在 CPU 上的并行性通常很差，这就是为什么使用许多不明显的技巧来实现它们的原因（结果仍然值得怀疑）。如果您真的对排序加速感兴趣，我建议您关注 GPU（例如，thrust::sort）。

    • 3

相关问题