README

这是PHP中一个高效的整数优先队列实现。PHP提供了一个SplPriorityQueue类来实现优先队列，但这个组件有“奇怪”的行为，参见PHP请求#60926和PHP错误#53710。基本上，具有相同优先级的元素以任意顺序提取，这可能在许多情况下造成问题。即使如此，优先队列的定义中也提到

在优先队列中，优先级高的元素先于优先级低的元素服务。如果两个元素具有相同的优先级，它们将根据它们在队列中的顺序来服务。

阅读由Matthew Weier O'Phinney撰写的关于此SplPriorityQueue问题的文章Taming SplPriorityQueue以获取更多信息。

实现细节

我没有使用通常的方法使用堆来实现优先队列。我使用了按优先级分组的有序数组。对于数组迭代，我使用了PHP的next()和current()函数。

为了按顺序获取优先级，我使用了PHP的max()函数。要获取下一个优先级，我使用unset()从数组中删除上一个元素，然后对剩余值重新应用max()函数。

这个解决方案非常简单，并且提供了非常好的性能（见下文基准测试）。

基准测试

我提供了一个简单的脚本来测试实现性能。你可以通过运行以下命令来执行此测试

php benchmark/test.php

此脚本执行了50,000次插入和提取操作，使用不同的优先队列实现

• SplPriorityQueue
• Zend\Stdlib\SplPriorityQueue
• Zend\Stdlib\PriorityQueue

我还包括了PHP的SplPriorityQueue，以便在比较中有一个起点，尽管如上所述，此组件的结果是不正确的。

我使用Intel Core i5-2500、3.30GHz频率、8GB RAM的Ubuntu Linux 14.04和PHP 5.5.9执行了基准测试。以下是结果

--- Benchmark 50,000 insert and extract with a fixed priority
SplPriorityQueue                : 0.05173206 (sec)
FastPriorityQueue\PriorityQueue : 0.07072687 (sec)
Zend\Stdlib\SplPriorityQueue    : 0.23528290 (sec)
Zend\Stdlib\PriorityQueue       : 0.39357114 (sec)

--- Benchmark 50,000 insert and extract with random priority (1,100)
SplPriorityQueue                : 0.06713820 (sec)
FastPriorityQueue\PriorityQueue : 0.10090804 (sec)
Zend\Stdlib\SplPriorityQueue    : 0.44940901 (sec)
Zend\Stdlib\PriorityQueue       : 0.65850401 (sec)

如您所见，FastPriorityQueue的执行时间非常好，比其他实现（除了SplPriorityQueue）快约3倍到6倍。

单元测试

安装后，您可以使用composer执行以下命令来运行单元测试。

vendor/bin/phpunit

版权

本作品受Creative Commons Attribution 4.0 International License许可。

(C) 版权所有 2015 by Enrico Zimuel.