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

Question

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

我正在生成一些我需要在最后排序的项目.我想知道,在复杂性方面更快的是:将它们直接插入priority_queue或类似的数据结构中,还是在结尾处使用排序算法？

Answer 1

就你的问题而言,这可能会在游戏中稍晚一些,但让我们完成.

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

首先,优先级队列不一定是O(n log n).

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

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

正如您所看到的,许多优先级队列的O(log n)成本不仅仅用于插入,还用于提取,甚至是队列管理!虽然通常会丢弃系数来测量算法的时间复杂度,但这些成本仍然值得了解.

但是所有这些队列仍然具有可比较的时间复杂性.哪个最好？Cris L. Luengo Hendriks在2010年发表的题为"重新审视图像分析的优先级队列"的论文解决了这个问题.

在Hendriks的保持测试中,优先级队列用[0,50]范围内的N个随机数播种.然后队列的最顶层元素出列,增加[0,2]范围内的随机值,然后排队.该操作重复10 ^ 7次.从测量的时间中减去产生随机数的开销.通过此测试,梯形队列和分层堆表现得非常好.

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

如您所见,不同的队列通常对入队和出队的响应非常不同.这些数字意味着尽管可能存在优先于连续操作的优先级队列算法,但是没有最佳选择算法来简单地填充然后清空优先级队列(您正在进行的操作).

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

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

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

假设您有浮点数据,对向量进行排序将花费您O(n log n),但这次复杂性并没有隐藏优先级队列之类的东西.(你必须要小心一点.Quicksort在一些数据上运行得非常好,但它的最坏情况时间复杂度为O(n ^ 2).对于某些实现,这是一个严重的安全风险.)

我担心我没有分拣成本的数据,但我会说追溯分拣捕捉到你想要做得更好的本质,因此是更好的选择.基于优先级队列管理与后期排序的相对复杂性,我认为后期排序应该更快.但同样,你应该测试一下.

我正在生成一些我需要在最后排序的项目.我想知道,在复杂性方面更快的是:将它们直接插入优先级队列或类似的数据结构中,还是在结束时使用排序算法？

我们可能已经涵盖了上述内容.

不过,还有一个问题是你没有问过的.也许你已经知道了答案.这是一个稳定的问题.C++ STL表示优先级队列必须保持"严格弱"的顺序.这意味着具有相同优先级的元素是无法比较的,并且可以按任何顺序放置,而不是每个元素具有可比性的"总顺序".(有订货的一个很好的描述在这里.)在排序,"严格弱"是类似于一个不稳定的排序和"总序"类似于一个稳定的排序.

结果是,如果相同优先级的元素应保持相同的顺序,您将它们推入数据结构,那么您需要稳定的排序或总订单.如果您打算使用C++ STL,那么您只有一个选项.优先级队列使用严格的弱排序,因此它们在这里没用,但STL算法库中的"stable_sort"算法将完成工作.

我希望这有帮助.如果您想要提及任何论文的副本或想要澄清,请告诉我.:-)

Answer 2

将n个项插入优先级队列将具有渐近复杂度O(n log n),因此就复杂性而言,它最终不会比使用sort一次更有效.

它在实践中是否更有效取决于它.你需要测试.实际上,在实践中,即使继续插入线性数组(如插入排序,而不构建堆)也可能是最有效的,即使渐近地它具有更差的运行时间.

Answer 3

取决于数据,但我通常发现InsertSort更快.

我有一个相关的问题,我最终发现瓶颈只是我做了一个默认的排序(只有当我最终需要它时)和大量的项目,我通常有最糟糕的情况我的QuickSort(已按顺序),所以我使用了插入排序

使用许多缓存未命中对1000-2000个元素进行排序

所以分析你的数据!

Answer 4

对你的第一个问题(更快):这取决于.试试吧.假设您希望最终结果在向量中,替代方案可能如下所示:

#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,也许你有更好或更差的堆实现.或者如果不是更好或更糟,只是或多或少地适合您的确切用法,这与我发明的用法不同:"创建包含值的排序向量".

我可以非常自信地说随机数据不会达到最坏的情况std::sort,所以从某种意义上来说,这个测试可能会让人感到厌烦.但是对于一个好的实现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

对于你的第二个问题(复杂性):它们都是O(n log n),忽略了虚拟的实现细节,比如内存分配是否为O(1)(最后的vector::push_back其他形式的插入是分摊的O(1))并假设通过"排序"表示比较排序.其他类型的排序可以具有较低的复杂性.