什么更快:插入优先级队列,还是追溯排序?

不 进入优先级队列的项将具有渐近复杂性( 不 日志 不 )所以就复杂性而言,它并不比使用 sort

在实践中是否更有效取决于。你需要测试一下。实际上,在实践中,甚至继续 插入 在线性数组中(如插入排序中,不构建堆)可能是最有效的,即使它是渐进的 运行时。

就你的问题而言,这可能在游戏中出现得有点晚,但让我们完成吧。

对于特定的计算机体系结构、编译器和实现,测试是回答这个问题的最佳方法。除此之外,还有一些概括。

首先,优先级队列不一定是O(n logn)。

如果您有整数数据,则会有优先级队列在O(1)时间内工作。Beucher和Meyer在1992年出版的《分割的形态学方法:分水岭变换》中描述了分层队列,这种队列对于范围有限的整数值非常快。Brown 1988年的出版物“日历队列:模拟事件集问题的快速0(1)优先级队列实现”提供了另一种解决方案,它很好地处理了更大范围的整数-在Brown的出版物之后的20年的工作为处理整数优先级队列产生了一些很好的结果 快速的

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

在Hendriks的hold测试中,使用 范围内的随机数 [0,50] . 然后,队列中最上面的元素被取消排队,并按范围内的随机值递增 [0,2] 10^7 次。从测量的时间中减去生成随机数的开销。梯形队列和层次堆在这个测试中表现得相当好。

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

让我们回顾一下你的问题:

如上所示,优先级队列可以提高效率,但插入、删除和管理仍有成本。插入向量很快。在摊销时间内是O(1),没有管理成本,加上要读取的向量是O(n)。

恐怕我没有关于分类成本的数据,但我想说追溯分类抓住了你想做得更好的本质,因此是更好的选择。基于优先级队列管理与后期排序的相对复杂性,我认为后期排序应该更快。不过,你还是应该测试一下。

我们可能已经讨论过了。

不过,还有一个问题你没问。也许你已经知道答案了。这是一个稳定的问题。C++ STL表示优先级队列必须保持“严格的弱”顺序。这意味着同等优先权的要素是不可比较的,可以按任何顺序排列,而不是按每个要素都具有可比性的“总顺序”。(有一个很好的订单描述 here )在排序中,“严格弱”类似于不稳定排序,“全序”类似于稳定排序。

我希望这有帮助。如果您需要上述文件的复印件或需要澄清,请告诉我。:-)

对于你的第一个问题(哪个更快):这要看情况。测试一下。假设您希望在向量中得到最终结果,备选方案可能如下所示:

#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::sort std::priority_queue 在这种情况下 std:sort

我可以很有信心地说,随机数据不会出现最坏的情况 标准::排序 标准::排序

编辑:我添加了multiset的用法,因为有些人建议使用树:

    #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

vector::push_back 最后插入的其他形式是摊销的O(1),假设“排序”是指比较排序。其他类型的排序可以具有较低的复杂性。

取决于数据,但我通常认为InsertSort更快。

所以我使用了插入排序

Sorting 1000-2000 elements with many cache misses

所以分析你的数据!

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

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

我建议在最后分类。

为什么不使用二叉搜索树呢?然后在任何时候对元素进行排序,插入成本等于优先级队列。 阅读红黑平衡树 here

我认为,在几乎所有生成数据的情况下(例如,列表中还没有数据),插入都更有效。

优先级队列不是您在运行时插入的唯一选项。如其他答案所述,二叉树(或相关RB树)同样有效。

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

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

• 如果你有你所有的元素“在前面”,然后选择排序。
• 如果要“动态”添加元素/删除最小元素,则使用优先级队列(例如,堆)。

对于第一种情况,最好的“最坏情况”是 不管怎样,只要专注于排序(即,而不是与其他操作交织),通常可以获得更好的缓存性能。