我想知道 c++11
中 std::sort
的实现。我有一个 MPI 管理的并行代码,其中每个等级将文件中的数据读取到需要排序的 vector A 中。每个排名都会调用 std::sort 来执行此操作。
当我以大约 100 个等级运行此程序时,有时会有一个等级在对 std::sort
的调用中挂起。最终,我意识到,这不是挂起,而是需要很长时间。也就是说,一个排名的排序时间比所有其他排名的时间长约 200 倍。
起初我怀疑这是一个负载平衡问题。不,我已经彻底检查了每个等级的 A
大小是否尽可能平衡。
我得出的结论是,可能只是一个等级的初始条件为 A
,例如 worst-case performance of quicksort已实现(或至少是非理想情况)。
我为什么这么想?
- 如果我更改
MPI
配置(从而扰乱每个等级A
的内容,因为它来自读取的文件),问题就会消失,或者可以移动到其他级别。 - 如果我将
std::sort
更改为std::stable_sort
(不再使用快速排序算法),那么一切都很好。
但是,通过在每次迭代中选择随机枢轴点来实现快速排序似乎是最明智的。如果 std::sort
就是这种情况,那么在多次迭代中从 A
中随机选择最坏情况的值是绝对不可能的(这需要导致性能下降 200 倍)。
因此,我的观察表明 std::sort
实现了固定快速排序枢轴值(例如,始终选择数组中的第一个值,或类似的值)。这是我所看到的行为可能发生的唯一方法,并且在相同的 MPI 配置上重新运行时也能给出一致的结果(确实如此)。
我的结论正确吗?我确实设法找到了 std 源,但是 sort 函数完全不可读,并且对各种辅助函数进行了大量调用,我宁愿避免兔子洞。除此之外,我正在 HPC 系统上运行,我什至不清楚如何确定 mpicxx
到底链接到什么。我找不到任何描述算法实现的文档
最佳答案
std::sort
是特定于实现的。
自 C++11 起,常规快速排序不再是有效的实现,因为所需的复杂度从平均的 O(N log N)
变为 O (N log N)
。
关于C++ std::sort 实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54371903/