johnroyer/fastpriorityqueue

Efficient integer priority queue implementation in PHP

v1.14.0 2019-10-27 09:29 UTC

Requires

• php: >=7.2

Requires (Dev)

• phpunit/phpunit: ^8.0
• zendframework/zend-stdlib: ^2.6

BSD-3-Clause

• spl
• priority queue
• SplPriorityQueue

README

This is an efficient implementation of an integer priority queue in PHP. PHP offers the SplPriorityQueue class that implements a priority queue, but this component has a "strange" behaviour, see PHP request #60926 and PHP bug #53710. Basically, elements with the same priority are extracted in arbitrary order and this can be a problem in many situations. Even, though, the definition of Priority Queue says:

In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Read the post Taming SplPriorityQueue by Matthew Weier O'Phinney for more information about this SplPriorityQueue issue.

Implementation details

I did not use the usual approach to implement the priority queue with a heap. I've used ordered arrays grouped by priorities. For the array iteration I used the next(), and current() functions of PHP.

To get the priorities in order, I use the max() function of PHP. To retrieve the next priority, I remove the previous one from the array, using unset(), and I re-apply the max() function to the remaining values.

This solution is very simple and offers very good performance (see the benchmark below).

Benchmark

I provided a simple script to test the performance of the implementation. You can execute this test running the following command:

php benchmark/test.php

This script executes 50'000 insert and extract operations using different priority queue implementations:

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

I have also included the SplPriorityQueue of PHP to have a starter point for the comparison, even though the results of this component are not correct, as mentioned above.

I executed the benchmark using an Intel Core i5-2500 at 3.30GHz with 8 Gb of RAM running Ubuntu Linux 14.04 and PHP 5.5.9. Here the results:

--- 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)

As you can see the execution time of FastPriorityQueue is very good, about 3x to 6x faster than the other implementations (except the SplPriorityQueue that is out of the comparison).

Unit Tests

You can run the unit tests by executing the following commmand after the installation using composer.

vendor/bin/phpunit

Copyright

This work is licensed under a Creative Commons Attribution 4.0 International License.

(C) Copyright 2015 by Enrico Zimuel.