Golang 中的快速优先级队列:分层队列

本文最初发表在我的网站https://coder.today/fast-priority-queues-in-go-hierarchical-queue-86daf6a7553a

编写 O(1) 高性能数据结构是一个多帖子系列:

1.分层队列(本文)

2.分层堆

3.梯队队列(即将)

优先级队列是一种抽象的数据结构,用于存储具有优先级的值(任何数据)。可以随时插入任何优先级的数据,但只能取出优先级最高的值。

Magic

何时使用优先级队列 !?

我承认,我并没有在我的应用程序中使用它们中的很多,但是有一些问题完美:

分类——基于分数/重要性的任何处理
ordering - 当您的数据具有特定的处理/分析顺序时,例如:在 MAU 之前处理 DAU KPI
事件驱动模拟——优先级可以是时间戳
图形搜索
负载均衡——优先级是负载的倒数

婴儿步数

我与 Go](https://coder.today/go-go-go-flash-bang-d66f4c42eb7c)建立了长久的[关系。我不想让我的训练白费,所以我开始寻找高性能数据结构来实现(目前还没有)。经过几次搜索后,我最终得到了这张图片,摘自一本书

两条底线引起了我的兴趣,它们是 O(1) 多结构优先级队列。首先是分层堆,它基于分层队列,所以让我们深入研究。

分层队列

我找不到此结构的任何开源代码或伪代码,如果您发现任何问题,请告诉我。

“当优先级值被限制为小整数时(例如,当数字图像离开成像传感器时,它们通常具有 8 位或 12 位整数作为像素值),可以为每个优先级分配一个 FIFO 队列(桶)可能的优先级值。一个数组包含一个指向这些桶中的每一个的指针,当对一个元素进行排队时,可以使用优先级值直接索引正确的桶。入队和出队都是 O(1) 操作。”

用于算法和片段的论文:

重新审视图像分析的优先级队列,Cris L. Luengo Hendriks
分层队列:MAMBA 图像库中的一般描述和实现,Nicolas Beucher 和 Serge Beucher

它是一个简单的结构,速度非常快,但有一些限制。

它只有有限数量的优先级值(在我的实现中是 uin8(0–255))。每个值都有自己的队列,因此增加数字会导致内存开销。

2.一旦最高优先级队列为空,就将其移除,下一个队列可以开始清空,**并且不能再次创建。**这意味着我们必须在开始出队之前填满队列,否则我们的性能将减少,例如:出队过程只剩下 1 个优先级(255),我们将其他元素加入队列。所有新元素都将被推送到 255 队列中(因为 0-254 为空并被移除)。

转到代码转到

优先级可以是 uint8 和值 interface{} 。

我决定删除第二个限制, 我认为它使结构对于大多数现实世界场景来说过于严格。我设法保持了非常相似的性能(每次操作≤ 50ns)。我缓存了具有值的最高优先级并从那里开始出列。在某些情况下,Dequeue 过程可以是 O(1 + k) ,其中 K 个空队列,但如果优先级平衡良好,总体上是摊销的。

这意味着结构的寿命得到了延长,它可以被重用,并且即使在出队过程开始之后也可以添加更高的优先级值。

在第一次迭代中,我使用链表作为队列(使用 golang list.List),平均操作时间为 150-200ns。我最终使用了更快的结构(感谢 Egon Elbre 的建议)。它将操作时间减少到 50ns 以下_(这是一个非常快的该死的列表)_,请参阅 collection/deque:

Karazabe/Kokiljar

某选手的算法工具箱

CookieJar - 参赛者的工具箱

CookieJar 是一小部分常用算法、数据结构和库扩展,它们一度被认为对计算竞赛很方便。

这个工具箱是一个正在进行中的工作。它可能缺少,并且在提交之间可能会发生巨大变化(尽管尽一切努力不这样做)。欢迎你使用它,但它是你的头就行了:)

安装

要获取包,请执行:

go get gopkg.in/karalabe/cookiejar.v2

要导入此包,请将以下行添加到您的代码中:

import "gopkg.in/karalabe/cookiejar.v2"

有关更多详细信息,请参阅包文档。

内容

算法:

图表

*广度优先搜索

*深度优先搜索

数据结构:

袋子
因此
图表
优先队列
队列
套装
堆栈

扩展:

英尺

ScanFscanintfloat64string

数学

Absint

MinMaxintbig.Intbig.Rat

Signint

在 GitHub 上查看

因为并发在 Go 中很重要,所以结构有一个 mutex。它可以手动或自动使用(每个函数调用都会阻塞互斥锁)。

为了尽可能通用,队列可以存储任何数据类型接口{}。

打包

Hierarchical Queue 结构是“priorityqueue”包的一部分,它具有 100% 的测试覆盖率、示例、基准和文档。

bgadrian/数据结构

抽象数据结构 Go 包,在构建时考虑了性能和并发性以学习 Go。

Go中的数据结构

我正在为 GO 中的不同数据结构编写一组包。

为什么?要学习 Go,请练习基本结构并学习编写快速并发算法。

所有的包都有 100% 以上的测试覆盖率、基准测试和 godocs。用 go 1.9 测试。

!!警告此库尚未在生产中使用。 !!

优先队列

用于优先级队列的高性能、并发安全、复杂的抽象数据结构的集合。

Priority 队列是一种抽象数据类型,类似于常规队列或堆栈数据结构,但其中每个元素都有一个与之关联的“优先级”。在优先级队列中,优先级高的元素先于低优先级的元素提供服务。

分层队列描述

用于小整数的 O(1)/O(1+K) 优先级队列(非常快) 实现,它使用 N 个简单队列的集合。它针对具有小价值优先级的大量数据进行了优化......