Lib.rs

› 算法
#优先队列 #图算法 #堆 #配对 #优先级 #队列 #图

pheap

为优先队列和一些图算法实现的一种（快速）配对堆数据结构

由 1crcbl

3 个版本 (破坏性更新)

0.3.0 2021 年 6 月 28 日
0.2.0 2021 年 6 月 27 日
0.1.0 2021 年 6 月 22 日

#1212 在 算法

MIT/Apache

44KB
828 行

配对堆

Crates.io Documentation

来自 维基百科

配对堆是一种具有相对简单实现和优秀实际摊销性能的堆数据结构类型。配对堆是堆序多路树结构，可以被认为是简化后的斐波那契堆。它们被认为是实现如普里姆的最小生成树算法的“稳健选择”。

最小配对堆支持以下操作

  • find_min：查找堆中的最小元素，即根节点。
  • merge：合并两个堆。
  • insert：将新元素添加到堆中。
  • delete_min：删除根节点并重新排序其子节点。
  • decrease_key：降低元素的优先级。标准堆数据结构的实现不支持高效地搜索键（在此crate中就是这样）。因此，此操作可能非常耗时，上界为 O(2^(sqrt(log log n)))。

该crate还包含一个高效的Dijkstra算法实现，用于解决单源最短路径问题，以及Prim算法用于找到最小生成树。

基准测试

为了衡量此实现的性能，我选择了以下在 crates.io 上可用的库进行实验

如果遗漏了任何库，请告诉我。

实验在我的以下配置的PC上进行

操作系统：Fedora 34 64位
处理器：AMD® Ryzen 7 3800x 8核心处理器
内存：32 GB

实验 1

每个实现被分配执行1000次插入/0次删除，然后999次插入/1次删除（移除顶部元素），直到删除次数达到1000。这意味着每个实现必须执行500_500次插入和500_500次删除。

对于这个实验，我使用了criterion来测量每个实现的性能。

配对堆
(这个库)		 可寻址配对堆 配对堆
(Apasel422)		 优先队列 键优先队列
平均时间
(毫秒)		 20.37 56.6 24.18 116.84 111.30

实验2

每个实现被分配执行1000次插入/1000次优先级更新/0次删除，然后999次插入/999次优先级更新 | 1次删除（移除顶部元素），直到删除次数达到1000。

配对堆
(这个库)		 可寻址配对堆 配对堆
(Apasel422)		 优先队列 键优先队列
平均时间
(秒)		 1.399 无实现 无实现 0.171 0.142

对于这个实验，配对堆的性能比其他两个库差。这是因为配对堆数据结构必须搜索键，在最坏情况下需要O(n)的时间，而其他实现利用了哈希表的快速查找能力。

实验3

每个实现被分配插入100万元素，并将测量内存消耗。

对于这个实验，我编写了一个简单的main（在examples/stress.rs中）并使用valgrind与massif进行评估。

编译

cargo build --examples --release

运行valgrind

valgrind --tool=massif ./target/release/examples/stress <implementation> <number of nodes to be inserted>

命令行参数<implementation>接受以下选项

  • pairing_heap
  • priority_queue
  • keyed_priority_queue
  • addressable_pairing_heap
  • ap422_pairing_heap
配对堆
(这个库)		 可寻址配对堆 配对堆
(Apasel422)		 优先队列 键优先队列
峰值堆
内存消耗
(MB)		 30.5 72.0 段错误 62 76

massif-visualiser的图像输出存储在文件夹img中。

迪杰斯特拉算法

为了测试配对堆实现的迪杰斯特拉算法的性能，我使用了DIMACS数据集。你可以使用以下命令通过Python脚本来下载所有数据集

python3 scripts/download.py -d dimacs-all --dest data/

在crates.io上，有几个库实现了迪杰斯特拉算法，但我只找到了性能良好的pathfinding（请告诉我如果遗漏了任何库）。

对于这个实验，所有实现都被分配解决所有DIMACS数据集上的最短路径问题，并在十次运行后取平均运行时间。

注意：pathfinding的函数dijkstra_all只返回查询节点的直接父节点，而不是整个路径，我使用的函数是sssp_dijkstra_lazy。这个函数返回的结果（某种程度上）等同于pathfinding提供的结果。通过这样做，我们可以比较两种实现的求解时间，同时忽略路径构建时间。

时间以毫秒计

节点数 边数 pheap pathfinding
DIMACS-NY 264_346 733_846 88 110
DIMACS-BAY 321_270 800_172 94 127
DIMACS-COL 435_666 1_057_066 126 172
DIMACS-FLA 1_070_376 2_712_798 377 626
DIMACS-NW 1_207_945 2_840_208 456 665
DIMACS-NE 1_524_453 3_897_636 619 852
DIMACS-CAL 1_890_815 4_657_742 740 1_246
DIMACS-LKS 2_758_119 6_885_658 1_141 1_695
DIMACS-E 3_598_623 8_778_114 1_548 2_151
DIMACS-W 6_262_104 15_248_146 3_098 4_460
DIMACS-CTR 14_081_816 34_292_496 10_183 11_256
DIMACS-USA 23_947_347 58_333_344 16_678 20_896

最小生成树

在这个实验中，我测量了两个库在寻找最小生成树（MST）方面的性能。然而，两个crate之间存在一些值得注意的差异：首先，虽然 pathfinding 使用克鲁斯卡尔算法，但我只使用了配对堆实现普里姆算法。其次，pathfinding 的实现仅返回边的迭代器，而收集这些迭代器并（重新）构建MST是用户的任务。另一方面，我的实现返回完整的图以及MST的总权重。因此，我为 pheap 运行两个实验，一个是在不构建MST的情况下解决，另一个是在解决和构建MST的情况下。

十次运行后的平均时间，以毫秒为单位

节点数 边数 pheap
（解决）		 pheap
（解决 + 构建）		 pathfinding
DIMACS-NY 264_346 733_846 78 140 132
DIMACS-BAY 321_270 800_172 93 170 140
DIMACS-COL 435_666 1_057_066 132 243 191
DIMACS-FLA 1_070_376 2_712_798 358 727 598
DIMACS-NW 1_207_945 2_840_208 409 863 622
DIMACS-NE 1_524_453 3_897_636 565 1_144 845
DIMACS-CAL 1_890_815 4_657_742 715 1_553 1_148
DIMACS-LKS 2_758_119 6_885_658 1_093 2_307 1_641
DIMACS-E 3_598_623 8_778_114 1_452 3_100 2_125
DIMACS-W 6_262_104 15_248_146 2_618 5_732 4_042
DIMACS-CTR 14_081_816 34_292_496 7_371 16_470 9_712
DIMACS-USA 23_947_347 58_333_344 11_785 25_450 17_943

许可

根据以下之一许可：

由您选择。

贡献

除非您明确声明，否则根据Apache-2.0许可定义，您有意提交的任何旨在包含在作品中的贡献，将根据上述许可双许可，不附加任何额外条款或条件。

依赖

~155KB