•¯•¯¯•¯¯软件X 16（2021）100869原始软件出版物JHeaps：一个开源的优先级队列库迪米特里奥斯·米歇尔希腊雅典Harokopio大学电信信息学系ar t i cl e i nf o文章历史记录：收到2020年收到修订版2021年8月25日接受2021年保留字：堆数据结构a b st ra ct在过去的二十年中，已经引入了几个新的堆变体主要的研究动机是匹配配对堆的实际性能，同时提供原始斐波那契堆的强有力的理论保证。我们提出的接口和设计的JHeaps库，一个生产就绪的开源堆库的目标Java虚拟机。该库包含大量最先进的堆变体实现和适当设计的接口，允许用户在应用程序中轻松交换和试验不同堆的性能。此外，使用GraalVM的提前编译与众所周知的方法，如基于跟踪的模拟，我们进行了第一次大规模的实验研究堆在托管环境中。©2021由Elsevier B.V.发布这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v0.14用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX_2020_271法律代码许可证Apache-2.0使用git的代码版本控制系统使用的软件代码语言、工具和服务Java编译要求、操作环境依赖性Java 8及以上版本如果可用，链接到开发人员文档/手册https://www.jheaps.org/apidocs/问题支持电子邮件michail@hua.gr1. 介绍堆是由一组项组成的数据结构，每个项与来自全有序宇宙的键以及可能的值相关联。数据结构的设计是为了能够有效地查找和可能删除的项目与最小的关键字。一般来说，它支持以下操作：make-heap：返回一个空堆。findMin（H）：返回H中键最小的项，或者在堆为空的情况下。insert（H，x，k）：将具有键k的项x插入堆H中，返回句柄x.deleteMin（H）：从H中删除一个键最小的项。decreaseKeY（H， x， k）：给定句柄x，将H中相关项的键减少到k。delete（H， x）：给定一个句柄x，从H中删除关联item.电子邮件地址：michail@hua.gr。https://doi.org/10.1016/j.softx.2021.100869meld（H1，H2）：将堆H2中的所有项添加到堆H1中，使堆H2不可用。在本文中，我们介绍了JHeaps库，一个开源的软件库，针对Java虚拟机（JVM）包含一组丰富的堆变量采样从可能的设计空间。传统上，与堆相关的实验研究[1虽然这样做有一定的好处，解释型语言如Python、JavaScript和面向JVM的语言集合的日益普及，催生了一种新的算法库。GraalVM [6]最近的普遍可用性允许在不使用Java VM的情况下进行本机执行。GraalVM包含一个名为SubstrateVM的子系统，其中包括所有必要的运行时组件，如内存管理，线程调度和垃圾收集器。利用提前（AOT）编译，我们进行了堆的实验研究。我们的方法遵循以前的方法[3，4]，在完善的工作负载上使用基于跟踪的模拟。2352-7110/©2021由Elsevier B. V.出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx····迪米特里奥斯·米歇尔软件X 16（2021）1008692O据作者所知，这是第一次在托管环境中使用AOT对如此大量的堆进行实验性比较。本文的其余部分组织如下。我们将在第2节中简要讨论接口问题。第三部分介绍了该库的设计和可用的数据结构.第4节包含我们的实验，使用基于跟踪的模拟和第5节总结的文件。2. 界面设计Java从一开始就在其集合包中包含了基本的数据结构。关于优先级 队 列 ， Java 包 括 一 个 基 本 类 ， 它 提 供 （ logn ） insert 和deleteMin，但不提供任何DECREASEKEY、delete（线性搜索除外）或meld功能。因此，对于大多数程序员来说，根据所需的功能设计自己的接口和实现是非常常见的。JHeaps库的主要关注点之一是在几个定义良好的接口下合并不同的堆实现。有三个主要的功能级别：(1) 基本堆操作，即findMin、deleteMin、insert、size和空，(2) 可寻址堆操作，即decrease和delete，以及(3) 可融合堆操作，即融合每一个层次都带来了必须解决的额外困难和问题。2.1. 堆和可寻址堆堆之间的主要区别在于它们是否是可寻址的。因此，我们的接口分为两个主要层次。 这两个层次结构的基接口分别被称为和。在下文中，我们使用更一般的可寻址的一个作为示例。图1提供了一个带有库的主要接口的类图。的主要区别 的and 的接口是，和返回手柄。使用句柄，用户可以读取键，读写元素的值，并调用其他方法和。2.2. 双端堆双端优先级队列可以同时查找和维护最小和最大元素。因此，这 种 堆 的 接 口 还 包 含 对 称 操 作 findMax 、 deleteMax 和INCREASEMAX。从双端堆返回的句柄支持INCREASEKEY2.3. 可熔堆可合并堆支持额外的合并操作。堆的合并只允许在具有相同基础类型的两个堆此外，这两个堆需要使用相同的比较器进行初始化。在运行时，实现需要执行这些检查，并在必要时抛出适当的异常。请注意，融合是一种需要特殊算法支持的操作，以便在小于线性时间内实现3. 图书馆JHeaps库包含大量堆数据结构，它们代表了几乎所有的设计技术。表1包含所有可用实现的列表。为了保持一致性，我们使用与[4]中相同的命名方案该库使用Java语言的特性，对结果代码的性能有影响，但如果有人在生产中使用代码，这是必要的。最重要的是，我们使用Java泛型，以便允许用户更改键的类型和存储在堆中的值的类型。此外，我们允许用户更改使用比较器对象执行键比较的方式。作为一种优化，我们试图在操作的一开始就区分使用自然比较器或用户提供的比较器，从而避免for循环中不必要的比较。一个聪明的编译器当然会检测到这一点，但我们仍然试图在代码中避免它。关于内存消耗，库试图保持尽可能小的内存需求，但不牺牲性能。作为一个例子，考虑配对堆的此外，每个节点还需要一个引用，以便维护负责支持meld操作的所有者引用。作为一般规则，我们使用存储效率最高的表示，只要它不显着复杂的代码。遵循所有Java数据结构的设计，基于数组的堆包含适当的机制，以确保底层数组的容量足以存储所有请求的元素。这种机制将这些重新分配的成本平均分配给堆中的所有元素，迪米特里奥斯·米歇尔软件X 16（2021）1008693图1.一、库 中 主 要 接 口 的 类关系图。层次结构是具有键和关联值的可寻址堆 层次结构是只 包 含 键 的 不可寻址堆。添加了对关联值的支持图二. 在经典工作负载中的运行时间，而不会减少操作。成本从最坏情况到摊销的界限。用户当然能够在构造基于数组的堆时显式地请求一定的容量，以避免这样的重新分配，从而在它们适用的地方和时间保持最坏情况的界限。每当我们为基于数组的堆上的操作声明最坏情况的界限时，我们假设用户已经显式地初始化了堆，其容量大于或等于将要插入堆中的元素库中的各种堆都支持合并操作。JHeaps库通过为每个堆和每个句柄维护所有者引用来支持此操作。 在句柄的情况下，所有者引用被调用，并且最初指向创建句柄的堆，但是在堆与另一个堆合并之后可能会改变值。类似地，堆的所有者引用被调用，并且最初指向其自身，并且在融合的情况下可能指向另一个堆。此所有者引用允许堆的所有句柄在堆之间迁移，迪米特里奥斯·米歇尔软件X 16（2021）1008694图三. 随机的ins-dcr-dmn工作负载。有必要对他们进行报复。当用户合并两个堆并使用时，实现将首先合并结构，然后执行。任何没有被meld操作触及的句柄都可以在以后使用所有者引用来确定所有权的变化。为了避免维护完整的union-find数据结构，我们不允许在右手边的一个融合操作不止一次。所有者引用提供了一种机制，以便检测这种在运行时，并抛出适当的错误。作为一个标准的优化，我们在级联合并的情况下使用路径压缩启发式算法，也就是说，句柄从一个堆移动这种简单的技术意味着，在用户执行级联合并操作的情况下，声明的特定堆的摊销或最坏情况的边界是无效的[24]。4. 实验在本节中，我们将在各种众所周知的工作负载上实验性地比较不同的堆实现。我们使用第5次DIMACS挑战[25]期间描述的基于跟踪的模拟，有关跟踪文件的确切格式，请参见[26更具体地说，首先使用引用堆实现执行工作负载，并记录包含操作序列的文件。然后，使用不同的驱动程序执行跟踪文件，比较中的每个堆对应一个驱动程序，一个所谓的虚拟驱动程序，它只是分析跟踪文件，但不执行任何堆操作。使用伪驱动程序是为了规范化结果，这意味着从每个堆驱动程序的统计信息中减去伪驱动程序的统计信息。最终统计量表示为最小值的倍数，因此对于每个统计量，已获得最小值的驱动程序显示为1.0。我们还提供了表2，其中包含每个实验的运行时间（以毫秒为单位）以及最佳和最差的驱动程序。迪米特里奥斯·米歇尔软件X 16（2021）1008695图四、Di j k s t r a 算 法 在 真 实 世 界 地 图 和 非 循 环 图 上 的 执行。表1JHeaps库中的可用实现类（堆名称）类型可寻址可熔的双头的单调出版物BinaryArrayHeap（implicit-simple-2）阵列✗✗✗✗[七]《中国日报》BinaryArrayIntegerValueHeap（implicit-simple-2）阵列✗✗✗✗[8、9]BinaryArrayAddressableHeap（隐式-2）阵列✓✗✗✗[七]《中国日报》BinaryArrayWeakHeap（implicit-weak-2）阵列✗✗✗✗[10个国家]BinaryArrayBulkInsertWeakHeap（implicit-bulkins-weak-2）阵列✗✗✗✗[10个国家]MinMaxBinaryArrayDoubleEndedHeap（minmax-implicit-2）阵列✗✗✓✗[第十一届]DaryArrayHeap（implicit-simple-d）阵列✗✗✗✗[12个]DaryArrayAddressableHeap（implicit-d）阵列✓✗✗✗[12个]Fibonacci堆（Fibonacci）树✓✓✗✗[13个国家]简单斐波那契堆（简单斐波那契）树✓✓✗✗[14个]第一章PairingHeap（配对）树✓✓✗✗[第十五条]RankPairingHeap（rank-pairing-t1）树✓✓✗✗[16个]无代价MeldPairingHeap（cm-配对）树✓✓✗✗[17个]BinaryTreeAddressableHeap（explicit-2）树✓✗✗✗[七]《中国日报》DaryTreeAddressableHeap（explicit-d）树✓✗✗✗[12个]LeftistHeap（左）树✓✓✗✗[18个国家]SkewHeap（skew）树✓✓✗✗[19个]BinaryTreeSoftHeap（explicit-soft-simple-2）树✗✓✗✗[20个]BinaryTreeSoftAddressableHeap（explicit-soft-2）树✓✓✗✗[20个]ReflectedPairingHeap（反射配对）树✓✓✓✗[21日]ReflectedFibonacci堆（reflected-fibonacci）树✓✓✓✗[21日]Hollow Heap（空心）向无环✓✓✗✗[22日]图IntegerRadixHeap（radix-simple）桶✗✗✗✓[23日]LongRadixHeap（radix-simple）桶✗✗✗✓[23日]DoubleRadixHeap（radix-simple）桶✗✗✗✓[23日]BigIntegerRadixHeap（radix-simple）桶✗✗✗✓[23日]IntegerAddressableRadixHeap（radix）桶✓✗✗✓[23日]LongAddressableRadixHeap（radix）桶✓✗✗✓[23日]DoubleAddressableRadixHeap（radix）桶✓✗✗✓[23日]BigIntegerAddressableRadixHeap（radix）桶✓✗✗✓[23日]迪米特里奥斯·米歇尔软件X 16（2021）1008696该库是使用GraalVM CE v20.0.0编译的，它使用OpenJDK11.0.6。使用本机映像工具，为每个堆驱动程序构建可执行文件。实验在Intel（R）CoreTMi5- 8250@1.6GHz CPU（turbo迪米特里奥斯·米歇尔软件X 16（2021）1008697==图五. Dijkstra最大3.4 GHz），具有4个物理内核。这台机器有16 GB的RAM，运行的是Ubuntu/Linux，内核版本为5.4。运行时间由司机直接记录4.1. 工作负载以下工作负载是使用来自DIMACS挑战[25，27]的（修改后）代码和来自Larkin等人的（修改后）代码生成的。[4]。作为一个一般性的评论，我们看到最快和最慢的司机之间的运行时间比平时更小的差距。这可能与用于提前编译的相对新的技术和/或运行时组件的额外开销有关。请注意，虚拟驱动程序不创建堆节点，因此在执行后不必执行大量的垃圾收集。在接下来的每一张图中，除了运行时间，我们以以下格式报告执行期间发生的最大堆大小和操作比率：insert：deleteMin：DECREASEKEY。我们对许多不同规模的问题执行了每个实验，但观察到结果很快稳定下来。因此，每个图都显示了单个大型实例的结果。4.1.1. 分选最经典的工作负载（图2（a））是具有均匀分布的随机密钥的n个插入操作，然后是n个deleteMin操作。在此工作负载中，正如预期的那样，情况有利于不可寻址的隐式d-ary堆。4.1.2. 随机化ins-dmn第二个工作负载从n个随机插入操作开始，然后执行以下内容的cn次 图2（b）显示了c的结果1.一、此工作负载包含在原始DIMACS测试集中，这意味着它是最常见的测试之一。Larkin等人[4]称这种工作负载退化，因为他们表明堆内的结果密钥分布远非均匀。正如前面的实验所预期的那样，不可寻址的隐式d元堆（在我们的例子中是d4）是赢家。在基于指针的堆中，配对堆是最快的，但几乎差4倍迪米特里奥斯·米歇尔软件X 16（2021）1008698==-表2每个实验的最佳、最差和虚拟驱动程序运行时间（毫秒）最小值，c=1，k= 1最小值，c=1，k=1024比简单隐式4更简单。斐波那契堆在这里是有竞争力的，只比配对堆稍微差一点。最后，新引入的空心堆与配对堆具有非常相似的性能。4.1.3. 随机化ins-dcr-dmn[4]引入了下一个工作负载，以避免随机化ins-dmn工作负载引入的关键偏倚。同样，堆是用n个随机插入操作初始化的。然后cn次重复以下操作：一次随机插入，k在随机节点上decreaseKeY，然后是一次deleteMin。对于递减操作，有两种变化是可能的在第一种称为中间的变化中，密钥被减少到其当前值和最小值之间的某个随机数。在第二种变化中，称为min，键成为新的最小值。图图3（a）和3（b）分别包含当c k在中间的变化中，隐式d元堆的性能更好，其次是显式-4堆和配对堆，其性能大约差1.6倍。请注意，空心堆在这个特定的工作负载中表现不佳。当我们使用min变量时，情况就不同了，因为键减少的元素也是被随后的deleteMin操作删除的元素。在这种情况下，配对堆和它的无成本meld变体是明显的赢家。同样，空心堆在这个工作负载中无法与配对堆竞争隐式d-ary堆在三个操作（ins-dcr-dmn）期间执行两个自下而上和一个自上而下的调整，而对于配对堆，插入操作只是与根的链接，DECREASEKEY操作相对便宜（一个从父节点取消链接，一个与根的链接）。此外，配对堆的deleteMin操作的性能取决于我们随机选择的节点的子节点的数量，在decreaseKeY操作之后，该节点成为新的根节点。我们的配对堆实现通过从root和他们使用两个通道组合它们。当我们将k增加到1024时，情况就不同了，这意味着我们在删除最小值之前执行了很多DECREASEKEY操作 图图3（c）示出了中间变化的结果。隐式d元和配对的性能几乎相同。此外，在这种情况下，所有堆的性能似乎一致。唯一的例外是空心堆，它在这个工作负载中受到影响。图3（d）给出了min变量的k1024的情况。 因此，在该变型中，我们首先执行1024次随机递减操作，其中每次元素变为最小值然后执行最后一个deleteMin操作。在这个工作负载中，隐式堆更快，但差异有限。看起来这种工作量更一般，并没有给任何特定的技术带来任何优势同样，空心堆在这里表现不4.1.4. Dijkstra其余的工作量是基于执行的Di- jkstra的算法的单源最短路径问题。图图4（a）示出了来自加利福尼亚州和内华达州的道路地图的真实世界图的结果。隐式d-ary堆在这样的工作负载中表现得非常好，这一点已经得到了很好的证实好消息是，对堆非常接近隐式d元堆.我们再次观察到基于指针的堆和隐式d进制堆之间的微小差异最后，空心堆的性能比斐波那契堆好，但比配对堆差。在这个特定的用例中，显式8和显式16d进制堆似乎受到影响，可能是由于更大的指令计数。其余的图在结构良好的图表上有结果。图图4（b）使用具有非负边权重的非循环图。无环图似乎稍微倾向于配对和隐式d-元堆。空心堆在这种工作负载中完全没有竞争力。图5（a）具有长网 格 （ grid_slong ） 上 的 结 果 ， 而 图 5 （ b ） 具 有 长 网 格（ grid_slong ） 上 的 结 果 。 5 （ b ） 包 含 具 有 非 负 边 权 重（grid_phard）的更困难的最短路径实例。在这两种情况下，配对堆和隐式d-ary堆的性能是相似的。另一方面，显式版本可能由于增加的指令计数而受到影响。令人惊讶的是，在长网格的情况下，空心堆的性能非常好。图5（c）使用grid_ssquare，图5（c）使用grid_ssquare。5（d）使用grid_ssquare_s。最后两个实例之间的区别是将具有零长度边的人造源顶点引入到图的所有顶点。在这种情况下，配对堆是最具竞争力的。即使在grid_ssquare_s的情况下，在操作比率不同的情况下，它们也保持其性能。有关这些生成器的详细描述，请参见SPLIB [28]。5. 结论我们详细介绍了JHeaps库的接口和设计选择。该库经过了良好的测试，并已在JGraphT库中用于生产[29]。它包含大量堆数据结构的最新实现，代表了大量的设计选择。最后我们实验虚设最好最糟糕分选分选1003318462（implicit-simple-4）54341（左派）随机插入-删除最小值简并923913311（implicit-simple-4）39477（歪斜）随机降低中间，c=1，k= 1中间，c=1，k= 102467096496145302287512529102031574925702（隐式-8）（cm-配对）（隐式-2）（隐式-4）21419184111739528550（skew）（explicit-16）（hollow）（hollow）Dijkstra美国路线图（CAL）1287615478（隐式-2）20511（explicit-16）美国青年联合会29843464（配对）3925（空心）格线41694570（隐式-2）5033（explicit-16）迪米特里奥斯·米歇尔软件X 16（2021）1008699首次在托管环境中使用提前编译对堆数据结构进行了广泛的运行时比较。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作引用[1] Stasko JT，Vitter JS.配对堆：实验与分析。Commun ACM1987;30（3）：234-49.[2] Moret BM，Shapiro HD.构造最小生成树算法的实证分析。在：算法和数据结构研讨会。Springer; 1991，p. 400比11[3] 拉马尔卡A，拉德纳R。缓存对堆性能的影响。J. Exp P.（JEA）1996;1：4.[4] Larkin DH，Sen S，Tarjan RE.优先级队列的回归基础实证研究。在：2014年第十六届算法工程和实验研讨会论文集。SIAM; 2014，p.61比72[5] 王晓刚，王晓刚，等.弱堆优先级排队系统的理论与实践.北京：机械工程出版社，2001.第十八届计算会议论文集：澳大拉西亚理论研讨会，第128卷。澳大利亚计算机协会; 2012年，第103比12[6] Würthinger T，Wimmer C，Wönig A，Stadler L，Duboscq G，Humer C，Richards G，Simon D，Wolczko M.一个VM来统治它们。在：2013年ACM国际研讨会上的新思想，新范式，以及对编程&软件的反思。ACM; 2013，p.187-204.[7] 威廉姆斯JWJ。 第232章：你是我的女人 Commun ACM1964;7：347-8.[8] 韦格纳岛自底向上堆排序，一种新的堆排序的变体，平均而言，QUICKSORT（如果n不是很小）。Theoret Comput Sci1993;118（1）：81-98.[9] Sanders P.高速缓存内存的快速优先级队列。《实验医学杂志》（JEA）2000;5：7.[10]Edelkamp S ， Elmasry A ， Katajainen J. 弱 堆 数 据 结 构 ： 变 体 和 应 用 。 JDiscrete Algorithms2012;16：187-205.[11]杨文龙，李晓梅.最小-最大堆和广义优先级队列。Commun ACM1986;29（10）：996-1000.[12]约翰逊湾优先级队列更新和寻找最小生成树。Inform Process Lett1975;4（3）：53-7.[13]Fredman ML，Tarjan RE.斐波那契堆及其在改进网络优化算法中的应用。JACM1987;34（3）：596-615.[14]王晓刚，王晓刚，王晓刚.斐波那契堆重访。2014年，arXiv预印本arXiv：1407.5750。[15]Fredman ML，Sedgewick R，Sleator DD，Tarjan RE.配对堆：一种新形式的自调整堆。Micromica1986;1（1-4）：111-29.[16]Haeupler B，Sen S，Tarjan RE.等级配对堆。SIAM J Comput2011;40（6）：1463-85.[17]埃尔马斯利将堆与无成本的合并配对。在：欧洲算法研讨会。Springer;2010，p. 183比93[18]CraneCA.线性列表和优先级队列作为平衡二叉树。一九七三年[19]Sleator DD，Tarjan RE.自我调整堆。SIAM J Comput 1986;15（1）：52 - 69.[20]作者：J. chazelle软堆的一个简单实现与分析。在：第二十届年度ACM-SIAM离散算法研讨会论文集。工业与应用数学学会;2009，p. 477-85.[21]Makris C ， Tsakalanya A ， Tsichlas K. 反 射 的 最 小 - 最 大 堆 。 InformProcessLett2003;86（4）：209-14.[22]杨 文 辉 ， 陈 文 辉 ， 陈 文 辉 . 空 堆 。 ACM TransAlgorithms （ TALG ） 2017;13（3）：42.[23]Denardo EV ， Fox BL. 最 短 路 径 方 法 ： 1. 伸 手 ， 修 剪 ， 和 水 桶 。 OperRes1979;27（1）：161-86.[24]杨文辉，王文辉，王文辉.可熔堆和布尔联合查找。在：第三十四届年度ACM计算理论研讨会论文集。ACM; 2002，p. 573-82.[25]迪 马 斯 。 第 五 个 DIMACS 挑 战 ： 优 先 级 队 列 。 1996 ， https://www.cs 。amherst.edu/%7Eccmcgeoch/challenge5/p_queue/index.html 网 站 。 [ 在 线 ;2019年8月访问[26]McGeoch CC.第五届DIMACS实现挑战：数据类型定义和规范。一九九六年。[27]迪 马 斯 。 第 九 届 DIMACS 实 施 挑 战 ： 最 短 路 径 。 2006 ，http://www.dis.uniroma1.it/%7Echallenge9/download.shtml。[在线; 2019年8月访问[28]Cherkassky BV，Goldberg AV，Radzik T.最短路径算法：理论与实验评估。Math Program1996;73（2）：129-74.[29]Michael D，Kinable J，Naveh B，Sichi JV. JGraphT- 图 形 数 据 结 构 和 算法 的 J a v a 库 。ACM Trans Math Software 2020;46（2）.
我的内容管理
展开
