多线程合并排序比迭代方法C++慢[关闭]

b5buobof  于 2024-01-09  发布在  其他
关注(0)|答案(2)|浏览(163)

已关闭。此问题需要details or clarity。目前不接受回答。
**要改进此问题吗?**通过editing this post添加详细信息并阐明问题。

4天前关闭。
Improve this question

  1. #include <iostream>
  2. #include <vector>
  3. #include <thread>
  4. void mergeSort(std::vector<int>& v, int left, int right) {
  5. if (left < right) {
  6. int mid = left + (right - left) / 2;
  7. std::thread t1(mergeSort, std::ref(v), left, mid);
  8. std::thread t2(mergeSort, std::ref(v), mid + 1, right);
  9. t1.join();
  10. t2.join();
  11. merge(v, left, mid, right);
  12. }
  13. }

我尝试了多线程方法来实现归并排序算法,但是当测试多线程和迭代之间的差异时,即使输入高达1M,迭代方法也要快得多。我的算法有什么问题,我如何才能让它按预期工作?

ut6juiuv

ut6juiuv1#

使用线程时,重要的是要考虑以下几点:

  • 一次可以运行的最大线程数是多少(给定硬件?)。通常是系统上的逻辑核心数。
  • 如何降低线程启动/加入的频率?启动线程是一个开销很大的操作,线程所做的工作要超过启动它的开销。
  • 如何(尽管这对于您的特定用例不太重要)尽可能减少线程访问相同数据的数量?

在你的例子中,我认为你最终会产生比你的系统实际上可以处理的多得多的线程。让我们举一个最简单的例子,假设你在一个双核机器上;你想把你的工作分成两个线程来实现最大的吞吐量。
你可能想要这样的东西:

  1. void mergeSort(std::vector<int>& v, int left, int right, bool shouldThread) {
  2. if (left < right) {
  3. int mid = left + (right - left) / 2;
  4. if (shouldThread) {
  5. std::thread t1(mergeSort, std::ref(v), left, mid, false);
  6. std::thread t2(mergeSort, std::ref(v), mid + 1, right, false);
  7. t1.join();
  8. t2.join();
  9. }
  10. else
  11. {
  12. mergeSort(std::ref(v), left, mid, false);
  13. mergeSort(std::ref(v), mid + 1, right, false);
  14. }
  15. merge(v, left, mid, right);
  16. }
  17. }

字符串
这将跨两个线程启动第一级,每个线程将向下递归树的一半。
假设这是可行的(未经测试),下一步就是让它启动线程,只要你有有用的硬件来执行它们。

展开查看全部
tmb3ates

tmb3ates2#

将线程数限制为核心数或核心数的2倍。链接到示例4线程合并排序,它比单线程合并排序快3倍。
https://codereview.stackexchange.com/q/148025/59065

相关问题