FastPriorityQueue

A blazzingly fast implementation of priority queue using Rust + Ruru

Installation

Add this line to your application's Gemfile:

gem 'fast_priority_queue'

And then execute:

$ bundle

Or install it yourself as:

$ gem install fast_priority_queue

Usage

fpq = FastPriorityQueue.new
# or use a custom comparator function
fpq = FastPriorityQueue.new { |a,b| a<=>b }
# add elements to the queue
fpq.add 5
fpq.add 4
fpq.add 3
fpq.add 2
fpq.add 1
# see what's in the top of the queue
fpq.top # => 1
# take the top element
fpq.pop # => 1
fpq.pop # => 2
# see how many elements are in the queue
fpq.length # => 3

Benchmarks

FastPriorityQueue is super fast. Here are some benchmarks against PQueue:

(the smallest the number, the better)

Benchmark of add and pop with fixnums:

Rehearsal -----------------------------------------------
Fast#add      0.830000   0.010000   0.840000 (  0.854182)
PQueue#push  22.610000  40.740000  63.350000 ( 67.128790)
Fast#pop      1.280000   0.010000   1.290000 (  1.331896)
PQueue#pop    0.010000   0.000000   0.010000 (  0.012800)
------------------------------------- total: 65.490000sec

                  user     system      total        real
Fast#add      0.860000   0.010000   0.870000 (  0.896107)
PQueue#push  22.570000  41.690000  64.260000 ( 68.815510)
Fast#pop      1.250000   0.010000   1.260000 (  1.275417)
PQueue#pop    0.010000   0.000000   0.010000 (  0.011788)

Benchmark of add and pop with objects:

Rehearsal -----------------------------------------------
Fast#add      0.380000   0.010000   0.390000 (  0.393005)
PQueue#push  36.730000  53.990000  90.720000 ( 96.215730)
Fast#pop      1.850000   0.020000   1.870000 (  1.911544)
PQueue#pop    0.010000   0.000000   0.010000 (  0.012731)
------------------------------------- total: 92.990000sec

                  user     system      total        real
Fast#add      0.410000   0.010000   0.420000 (  0.423021)
PQueue#push  37.190000  55.130000  92.320000 (100.046236)
Fast#pop      1.970000   0.010000   1.980000 (  2.031743)
PQueue#pop    0.020000   0.000000   0.020000 (  0.014687)

I had to use Array#pop from ruby because there's no Array.pop native extension by now. That's why #pop benchmark is a little bit worse than PQueue.

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/[USERNAME]/fast_priority_queue.