Download the PHP package johnroyer/fastpriorityqueue without Composer
On this page you can find all versions of the php package johnroyer/fastpriorityqueue. It is possible to download/install these versions without Composer. Possible dependencies are resolved automatically.
Download johnroyer/fastpriorityqueue
More information about johnroyer/fastpriorityqueue
Files in johnroyer/fastpriorityqueue
Package fastpriorityqueue
Short Description Efficient integer priority queue implementation in PHP
License BSD-3-Clause
Homepage https://github.com/ezimuel/fastpriorityqueue
FAQ
Example:
In general, it is recommended to use always a project to download your libraries. In an application normally there is more than one library needed.
- Some hosting areas are not accessible by a terminal or SSH. Then it is not possible to use Composer.
- To use Composer is sometimes complicated. Especially for beginners.
- Composer needs much resources. Sometimes they are not available on a simple webspace.
- If you are using private repositories you don't need to share your credentials. You can set up everything on our site and then you provide a simple download link to your team member.
- Simplify your Composer build process. Use our own command line tool to download the vendor folder as binary. This makes your build process faster and you don't need to expose your credentials for private repositories.
Informations about the package fastpriorityqueue
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:
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:
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.
Copyright
This work is licensed under a Creative Commons Attribution 4.0 International License.
(C) Copyright 2015 by Enrico Zimuel.
