35

什么更快：插入优先级队列，或追溯排序？

我正在生成一些我需要在最后进行排序的项目。我想知道，就复杂性而言，什么更快：将它们直接插入到 priority_queue 或类似的数据结构中，还是在最后使用排序算法？

4

10 回答 10

97

就您的问题而言，这可能会在您的游戏后期出现，但让我们完整。

针对您的特定计算机体系结构、编译器和实现，测试是回答此问题的最佳方式。除此之外，还有概括。

首先，优先级队列不一定是 O(n log n)。

如果您有整数数据，则有优先级队列在 O(1) 时间内工作。Beucher 和 Meyer 的 1992 年出版物“分割的形态学方法：分水岭变换”描述了分层队列，它对有限范围的整数值工作得非常快。Brown 1988 年的出版物“日历队列：模拟事件集问题的快速 0 (1) 优先级队列实现”提供了另一种很好地处理更大范围的整数的解决方案 - 在 Brown 的出版物之后的 20 年的工作已经产生了一些很好的整数结果优先级队列快. 但是这些队列的机制可能会变得复杂：桶排序和基数排序可能仍然提供 O(1) 操作。在某些情况下，您甚至可以量化浮点数据以利用 O(1) 优先级队列。

即使在浮点数据的一般情况下，O(n log n) 也有点误导。Edelkamp 的《启发式搜索：理论和应用》一书中有一个方便的表格，显示了各种优先级队列算法的时间复杂度（请记住，优先级队列相当于排序和堆管理）：

优先队列时间复杂度

如您所见，许多优先级队列的成本为 O(log n)，不仅插入成本高，提取成本高，甚至队列管理成本也高！虽然通常会删除系数来衡量算法的时间复杂度，但这些成本仍然值得了解。

但是所有这些队列仍然具有可比较的时间复杂度。哪个最好？Cris L. Luengo Hendriks 在 2010 年发表的一篇题​​为“Revisiting priority queues for image analysis”的论文解决了这个问题。

优先队列的保持时间

在 Hendriks 的保持测试中，优先级队列以[0,50]范围内的N个随机数为种子。然后将队列的最顶部元素出列，按[0,2]范围内的随机值递增，然后排队。此操作重复10^7次。从测量的时间中减去生成随机数的开销。梯形队列和分层堆在这个测试中表现得很好。

还测量了每个元素初始化和清空队列的时间——这些测试与您的问题非常相关。

每个元素的入队和出队时间

如您所见，不同的队列通常对入队和出队有非常不同的响应。这些数字表明，虽然可能存在优于连续操作的优先级队列算法，但没有最佳选择算法来简单地填充然后清空优先级队列（您正在执行的操作）。

让我们回顾一下您的问题：

什么更快：插入优先级队列，或追溯排序？

如上所示，优先级队列可以变得高效，但插入、移除和管理仍然存在成本。插入向量很快。摊销时间为 O(1)，没有管理成本，加上要读取的向量是 O(n)。

假设您有浮点数据，对向量进行排序将花费您 O(n log n)，但是这种时间复杂度并没有像优先级队列那样隐藏东西。（不过，您必须小心一点。快速排序在某些数据上运行得非常好，但它的最坏情况时间复杂度为 O(n^2)。对于某些实现，这是一个严重的安全风险。）

恐怕我没有排序成本的数据，但我想说追溯排序抓住了你想要做得更好的本质，因此是更好的选择。基于优先队列管理与后排序的相对复杂性，我会说后排序应该更快。但同样，您应该对此进行测试。

我正在生成一些我需要在最后进行排序的项目。我想知道，就复杂性而言，什么更快：将它们直接插入优先级队列或类似的数据结构中，还是最后使用排序算法？

我们可能已经在上面介绍过了。

不过，还有一个问题你没有问。也许你已经知道答案了。这是稳定性的问题。C++ STL 说优先级队列必须保持“严格的弱”顺序。这意味着具有相同优先级的元素是不可比较的，并且可以按任何顺序放置，而不是每个元素都可比较的“总顺序”。（这里对排序有很好的描述。）在排序中，“严格弱”类似于不稳定排序，“全序”类似于稳定排序。

结果是，如果相同优先级的元素应该保持与您将它们推送到数据结构中的相同顺序，那么您需要一个稳定的排序或总顺序。如果您打算使用 C++ STL，那么您只有一种选择。优先级队列使用严格的弱排序，所以在这里它们没用，但是 STL 算法库中的“stable_sort”算法可以完成工作。

我希望这有帮助。如果您想要上述任何文件的副本或想要澄清，请告诉我。:-)

于 2012-05-25T20:59:21.423 回答
32

将n项插入优先级队列将具有渐近复杂度 O( n log n )，因此就复杂度而言，它并不比sort最后使用一次更有效。

它在实践中是否更有效真的取决于。你需要测试。事实上，在实践中，即使继续插入线性数组（如在插入排序中，不构建堆）可能是最有效的，即使它渐近地运行时间更差。

于 2010-09-21T09:57:34.817 回答
7

取决于数据，但我通常发现 InsertSort 更快。

我有一个相关的问题，最后我发现瓶颈只是我正在做一个延迟排序（只有当我最终需要它时）并且在大量项目上，我通常有最坏的情况我的快速排序（已经按顺序），所以我使用了插入排序

对具有许多缓存未命中的 1000-2000 个元素进行排序

所以分析你的数据！

于 2010-09-21T10:14:41.400 回答
5

对于您的第一个问题（更快）：这取决于。只是测试它。假设您想要向量中的最终结果，替代方案可能如下所示：

#include <iostream>
#include <vector>
#include <queue>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <iterator>

#ifndef NUM
    #define NUM 10
#endif

int main() {
    std::srand(1038749);
    std::vector<int> res;

    #ifdef USE_VECTOR
        for (int i = 0; i < NUM; ++i) {
            res.push_back(std::rand());
        }
        std::sort(res.begin(), res.end(), std::greater<int>());
    #else
        std::priority_queue<int> q;
        for (int i = 0; i < NUM; ++i) {
            q.push(std::rand());
        }
        res.resize(q.size());
        for (int i = 0; i < NUM; ++i) {
            res[i] = q.top();
            q.pop();
        }
    #endif
    #if NUM <= 10
        std::copy(res.begin(), res.end(), std::ostream_iterator<int>(std::cout,"\n"));
    #endif
}

$ g++     sortspeed.cpp   -o sortspeed -DNUM=10000000 && time ./sortspeed

real    0m20.719s
user    0m20.561s
sys     0m0.077s

$ g++     sortspeed.cpp   -o sortspeed -DUSE_VECTOR -DNUM=10000000 && time ./sortspeed

real    0m5.828s
user    0m5.733s
sys     0m0.108s

所以，std::sortbeats std::priority_queue，在这种情况下。但也许你有一个更好或更差std:sort的 ，也许你有一个更好或更差的堆实现。或者，如果不是更好或更糟，只是或多或少适合您的确切用法，这与我发明的用法不同：“创建一个包含值的排序向量”。

我可以很有信心地说，随机数据不会达到最坏的情况std::sort，所以从某种意义上说，这个测试可能会让它更受宠若惊。但是对于一个好的实现std::sort来说，它的最坏情况将很难构建，而且实际上可能并没有那么糟糕。

编辑：我添加了一个多重集的使用，因为有些人建议一棵树：

    #elif defined(USE_SET)
        std::multiset<int,std::greater<int> > s;
        for (int i = 0; i < NUM; ++i) {
            s.insert(std::rand());
        }
        res.resize(s.size());
        int j = 0;
        for (std::multiset<int>::iterator i = s.begin(); i != s.end(); ++i, ++j) {
            res[j] = *i;
        }
    #else

$ g++     sortspeed.cpp   -o sortspeed -DUSE_SET -DNUM=10000000 && time ./sortspeed

real    0m26.656s
user    0m26.530s
sys     0m0.062s

对于您的第二个问题（复杂性）：它们都是 O(n log n)，忽略了诸如内存分配是否为 O(1) 之类的繁琐的实现细节（vector::push_back最后其他形式的插入是摊销的 O(1)）并假设“排序”是指比较排序。其他种类的排序可以具有较低的复杂性。

于 2010-09-21T10:52:47.940 回答
2

据我了解，您的问题不需要优先队列，因为您的任务听起来像“进行多次插入，然后对所有内容进行排序”。这就像用激光射鸟，而不是合适的工具。为此使用标准排序技术。

如果您的任务是模仿一系列操作，您将需要一个优先队列，其中每个操作可以是“将元素添加到集合”或“从集合中删除最小/最大元素”。例如，这可以用于在图上找到最短路径的问题。在这里，您不能只使用标准排序技术。

于 2010-09-21T11:58:34.603 回答
1

优先级队列通常实现为堆。使用堆排序平均比快速排序慢，除了快速排序在最坏情况下的性能更差。此外，堆是相对较重的数据结构，因此开销更大。

我建议最后排序。

于 2010-09-21T10:02:13.903 回答
1

我认为在您生成数据的几乎所有情况下（即尚未将其包含在列表中），插入效率更高。

优先队列不是您进行时插入的唯一选择。正如其他答案中提到的，二叉树（或相关的 RB 树）同样有效。

我还将检查优先级队列是如何实现的——许多已经基于 b-trees，但是一些实现并不擅长提取元素（它们基本上遍历整个队列并寻找最高优先级）。

于 2010-09-21T09:54:36.100 回答
1

为什么不使用二叉搜索树？然后元素总是被排序并且插入成本等于优先队列。在此处阅读有关 RedBlack 平衡树的信息

于 2010-09-21T10:29:52.780 回答
0

在最大插入优先级队列上，操作是 O(lg n)

于 2011-11-27T04:02:32.560 回答
0

这个问题有很多很好的答案。一个合理的“经验法则”是

  • 如果您“预先”拥有所有元素，则选择排序。
  • 如果您要“即时”添加元素/删除最小元素，请使用优先级队列（例如，堆）。

对于第一种情况，最好的“最坏情况”排序无论如何都是堆排序，而且您通常会通过只关注排序（即，而不是与其他操作交错）来获得更好的缓存性能。

于 2020-07-21T17:38:35.103 回答