c++ - C ++合并排序与线程较慢
问题描述
我已经在 C++ 中实现了合并排序算法。
在算法内部,它检查数组的大小是否大于min_size_to_thread
以及是否大于:改为使用线程递归调用函数。
但是当我增加min_size_to_thread
: 减少正在使用的线程数时,函数变得更快。即使从 1 到 2 个线程。
我的假设是函数速度会随着更多线程的增加而增加,然后再次开始下降。这对我来说没有任何意义,所以我开始相信我的实现在某种程度上是错误的。
template <typename T>
void merge_sort(T S[], int S_size, int min_size_to_thread)
{
if (S_size < 2) return;
// Left Sequence
int L_size = S_size / 2;
T* L = new T[L_size];
for (int i = 0; i < L_size; i++)
{
L[i] = S[i];
}
// Right Sequence
int R_size = (S_size + 1) / 2;
T* R = new T[R_size];
for (int i = 0; i < R_size; i++)
{
R[i] = S[i + L_size];
}
if (S_size > min_size_to_thread)
{
std::thread thread_left(merge_sort<T>, L, L_size, min_size_to_thread);
std::thread thread_right(merge_sort<T>, R, R_size, min_size_to_thread);
thread_right.join();
thread_left.join();
}
else
{
merge_sort<T>(L, L_size, min_size_to_thread);
merge_sort<T>(R, R_size, min_size_to_thread);
}
int S_iterator = 0;
int L_iterator = 0;
int R_iterator = 0;
while ((L_iterator < L_size) && (R_iterator < R_size))
{
if (L[L_iterator] < R[R_iterator])
{
S[S_iterator] = L[L_iterator];
++L_iterator;
}
else
{
S[S_iterator] = R[R_iterator];
++R_iterator;
}
++S_iterator;
}
while (L_iterator < L_size)
{
S[S_iterator] = L[L_iterator];
++L_iterator;
++S_iterator;
}
while (R_iterator < R_size)
{
S[S_iterator] = R[R_iterator];
++R_iterator;
++S_iterator;
}
delete[] L;
delete[] R;
}
int main()
{
const int S_size = 500000;
unsigned char S[S_size];
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
int min_size_to_thread;
min_size_to_thread = 250;
auto t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
auto t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
min_size_to_thread = 500;
t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
min_size_to_thread = 1000;
t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
min_size_to_thread = 10000;
t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
min_size_to_thread = 250000;
t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
for (int i = 0; i < S_size; ++i)
{
S[i] = i % 255;
}
min_size_to_thread = 500000;
t1 = std::chrono::high_resolution_clock::now();
merge_sort(S, S_size, min_size_to_thread);
t2 = std::chrono::high_resolution_clock::now();
std::cout << "size > " << min_size_to_thread << ": " << (t2 - t1) / std::chrono::milliseconds(1) << std::endl;
return 0;
}
解决方案
我已经编译并运行了您的确切程序,除了添加包含之外没有任何修改,结果或多或少与您预期的一样:
size > 250: 169
size > 500: 85
size > 1000: 50
size > 10000: 29
size > 250000: 42
size > 500000: 89
根据您的屏幕截图,我推测您正在从 Visual Studio 中运行您的代码。默认运行按钮会将调试器附加到您的可执行文件并降低运行时性能。相反,请按 Ctrl+F5 以在没有调试器的情况下运行,或者从菜单 Debug -> Start without Debugging 中运行。
推荐阅读
- android - Android MediaBrowserService:onLoadChildren 为 id null 发送了 null 列表
- javascript - 无法遍历 AJAX 响应
- java - Drools:使用 Query 获取无状态会话结果
- sql - 通过计算记录并将其插入表中,我的 while 循环将永远运行
- c++14 - 使用内置 (==) 运算符比较 C++ 中的 2 个有序集合的复杂性是什么?(假设集合大小 = n))
- excel - 如何删除 Excel 工作表中单元格中的附加值
- facebook - Vue 参数在 Instagram、Facebook 等应用内浏览器中丢失
- java - 如何在java中将时间格式转换为日期格式的今天时间?
- javascript - 检查对象数组是否存在
- google-apps-script - 每当脚本运行时,如何更改 onEdit 函数?- 谷歌表格