优先队列的性能测试

实验环境

这篇文章描述了优先队列的一些性能测试以及测试结果。下文中,g++、msvc++ 和 local(下文实验中使用这个生成器)代表三种不同的生成器:

g++

  • CPU 频率——cpu 主频:2660.644 MHz
  • 内存——内存总量:484412 kB
  • 平台——Linux-2.6.12-9-386-i686-with-debian-testing-unstable
  • 编译器——g++(GCC)4.0.2 20050808(prerelease)(Ubuntu 4.0.1-4ubuntu9) Copyright (C) 2005 Free Software Foundation, Inc. 这是一个免费软件,可以查看源代码进行复制,未经授权不得用于商业或者其他特殊目的。

msvc++

  • CPU 频率——cpu 主频:2660.554 MHz
  • 内存——内存总量:484412 kB
  • 平台—— Windows XP Pro
  • 编译器—— Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80×86 Copyright (C) Microsoft Corporation 1984-2002. All rights reserved

local

  • CPU 频率——cpu 主频:2660.554 MHz
  • 内存——内存总量:484412 kB
  • 平台—— Windows XP Pro
  • 编译器—— g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1) Copyright (C) 2006 Free Software Foundation, Inc. 这是一个免费软件,可以查看源代码进行复制,未经授权不得用于商业或者其他特殊目的。

实验项目

  1. 优先级队列文本的push操作时间测试
  2. 优先级队列文本的push和pop操作时间测试
  3. 优先级队列随机整数的push操作时间测试
  4. 优先级队列随机整数的push和pop时间测试
  5. 优先级队列文本的pop操作内存使用测试
  6. 优先级队列文本的join操作时间测试
  7. 优先级队列文本的修改操作时间测试一
  8. 优先级队列文本的修改操作时间测试二

观察实验

底层数据结构的复杂度

下表按照递增的顺序,展示了不同底层数据复杂度。有一点非常有趣:这个表也反映了关于操作的常量的事情(详见摊销push和pop操作)。

push pop modify erase join
std::priority_queue Θ(n) worstΘ(log(n)) amortized Θ(log(n)) Worst Theta;(n log(n)) Worst[std note 1] Θ(n log(n))[std note 2] Θ(n log(n))[std note 1]
priority_queuewith Tag =pairing_heap_tag O(1) Θ(n) worstΘ(log(n)) amortized Θ(n) worstΘ(log(n)) amortized Θ(n) worstΘ(log(n)) amortized O(1)
priority_queuewith Tag =binary_heap_tag Θ(n) worstΘ(log(n)) amortized Θ(n) worstΘ(log(n)) amortized Θ(n) Θ(n) Θ(n)
priority_queuewith Tag =binomial_heap_tag Θ(log(n)) worstO(1) amortized Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n))
priority_queuewith Tag =rc_binomial_heap_tag O(1) Θ(log(n)) Θ(log(n)) Θ(log(n)) Θ(log(n))
priority_queuewith Tag =thin_heap_tag O(1) Θ(n) worstΘ(log(n)) amortized Θ(log(n)) worstO(1) amortized,orΘ(log(n)) amortized[thin_heap_note] Θ(n) worstΘ(log(n)) amortized Θ(n)

[std note 1]这不是算法的属性,而是归咎于STL的优先队列不支持迭代器(也就不支持访问队列中指定值的能力)。如果优先级队列底层采用std::vector,那么利用STL适配器以及top函数将会返回队列中第一个元素的引用这一事实,仍然可以将复杂度降低到Θ(n)。然而,如果采用std::deque实现,则无法降低复杂度。

[std note 2]与[std note 1]一样,也不是算法的属性,而是与STL实现相关。同样,如果优先级队列采用std::vector实现,也可以将复杂度降低到Θ(n),但是,是一个非常大的常数(必须调用std::make_heap,这个操作是一个开销很大的线性操作);如果优先级队列用std::deque实现,则不可能降低复杂度。

[thin_heap_note] 一个稀疏堆,最坏情况的修改时间总是为&Theta(log(n)),但是摊销时间依赖于操作的特性:I)如果是插入较大的key值(从优先队列的比较函数角度来看),摊销时间是O(1)但是如果II)插入一个较小的key值,那么摊销时间和最坏的情况下是一样的。注意:在大多数算法中,I)很重要,II)并不重要。

摊销push和pop操作

很多情况下,优先级队列主要是为了进行频繁的push和pop操作。所有底层数据结构都有相同的摊销对数复杂度,但是它们的常数不同。

上表显示,不同数据结构在某些方面是受限制的。总而言之,如果某个数据结构在最坏情况下的复杂度比另一个数据结构更低,那么从摊销复杂度的角度来讲,它会更慢。因此,举个例子,一个冗余计数二项式堆(优先级队列带有这样的tag, Tag = rc_binomial_heap_tag)在最坏情况下的push操作比二项堆(优先级队列带有这样的tag,Tag = binomial_heap_tag)更低,因此冗余二项堆的摊销push操作从常数角度看比二项堆更慢。

如上表所示,受限制最小的底层数据结构是二叉堆和配对堆。因此,也就不奇怪他们在摊销常数上表现最好。

  1. 配对堆对于非原始类型(例如:std::strings)表现最好,正如Priority Queue Text push Timing Test 和Priority Queue Text push and pop Timing Test所展示的一样。
  2. 正如Priority Queue Random Integer push Timing TestPriority Queue Random Integer push and pop Timing Test两个实验所示,二叉堆对于非原始类型(例如int)表现得最好。

图形算法

在一些图形算法中,需要进行key递减操作[clrs2001];如果一个值是增长的(从优先级队列比较函数的角度讲),这个操作与修改操作的复杂度是相同的。上表和Priority Queue Text modify Timing Test – I显示:改良堆(优先级队列带有tag: Tag = thin_heap_tag)比配对堆(优先级队列带有tag:Tag = pairing_heap_tag)的性能要好,然而余下的测试却得到了相反的结果。

这使得在这种情况下应该使用哪种实现变得很难决定。例如,Dijkstra的最短路径算法,需要进行Θ(n)次push和pop操作 (n是结点的数量)、O(n2) 次修改操作,实际情况中也可以是Θ(n)次修改操作 。在难以找到先验特征的图中,实际modify操作的数量会让push和pop操作的数量变得微不足道。

2 收藏 评论

关于作者:zaishaoyi

程序员,主要开发语言 C++,Objective-C。外语:英语。日语学习中工作:搜索后台程序开发,机器学习 个人主页 · 我的文章 · 21 ·   

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部