FastPriorityQueue
FastPriorityQueue copied to clipboard
ezimuel
Efficient implementation of an integer proprity queue in PHP
Fast Priority Queue implementation
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:
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.
ezimuel