1

我一直在尝试使用线程优化排序算法（快速排序）。我知道它在 std::sort() 实现中已经相当不错了，但我正试图通过我的计算机上的优化来击败它，同时了解线程。

所以，我的问题是，如何在递归快速排序函数中使用线程？

这是函数（删除了对问题不重要的东西）：

template <typename T>
void quicksort(T arr[], const int &size, const int &beginning, const int &end)
{
    // Algorithm here
    thread t1(quicksort, arr, size, beginning, slow - 1);
    thread t2(quicksort, arr, size, slow + 1, end);
}

如果我错了，您最终需要更多代码，请告诉我，我会更新它。

我正在使用 Visual Studio 2012，截至目前，错误状态：

error C2661: 'std::thread::thread' : no overloaded function takes 5 arguments

我也尝试在每个参数上调用 ref(arr) 等，但我得到了同样的错误。

编辑：在尝试@mfontanini 的解决方案后，我可以毫无错误地编译，但在运行时，我得到：

Debug Error!

Program: ...sktop\VisualStudio\Projects\SpeedTester\Debug\SpeedTester.exe

R6010
- abort() has been called


(Press Retry to debug the application)

一遍一遍地重复。最终，它以代码 3 退出。

4

2 回答 2

3

您需要明确指出哪个是T模板参数：

thread t1(&quicksort<T>, arr, size, beginning, slow - 1);

否则编译器会看到你指的是一个函数模板，而不是哪个特定的特化；它不能凭空推断T。

于 2013-02-24T02:09:15.300 回答
1

您的主要问题可能是您需要生成join()的thread（s）。如果线程对象在没有事先join()或detach()实现调用的情况下被破坏std::terminate()。

您不想要detach()，因为您需要知道所有部分排序都已完成才能完成整体排序，因此joining 是正确的做法。

此外，还有一些您可以改进的地方：

  • 您不应该int通过引用传递 s。对于简单的标量类型，按值传递更有效，并且从其他线程引用局部变量通常不是一个好主意（除非您有充分的理由和协议）
  • 你启动了太多线程。分区后，两个子排序需要两个线程，但您有三个：当前线程也继续运行，因此您应该只创建一个新线程并在当前线程中执行另一个子排序。（join()完成后的另一部分。）
  • 当分区变小时，您不应该继续创建新线程。为您的快速排序设置一个截止大小并为较小的大小使用非递归（如插入排序）通常是一个好主意，因为递归开销变得高于算法复杂性的好处。类似的截止对于并发排序更为重要：线程的开销比简单的递归调用高得多，并且对于小的（和附近的）分区，线程将开始频繁地访问相同的缓存行，从而减慢速度更。
  • 无限制地创建线程通常不是一个好主意。这最终会遇到平台限制。您可能希望限制要使用的线程数（使用原子计数器）或使用类似std::async默认启动策略的东西，以避免启动超过平台可以处理的线程数。
于 2013-02-24T13:38:56.777 回答