PriorityQueueCxx

PriorityQueueCxx provides a fast implementation of priority queues for ruby. Speed is achieved by exposing the c++ standard implementation through a light ruby wrapper. As a bigger project, the library may grow to provide a number of containers that are not in the standard ruby library and are presently only available as pure ruby libraries. Presently, however, the library includes a single class named PriorityQueue. More containers will be added as necessity arises. Contributors and feature requests are most welcome.

The library exposes a module named FastContainers (to be required using require 'fc') which provides the PriorityQueue class.

gem install 'priority_queue_cxx'

require 'fc'
q = FastContainers::PriorityQueue.new(:max)
q.push("largest", 10)
q.push("smallest", 5)
q.top      # =>  "largest"
q.top_key  # => 10
q.pop

As far as I know, only one other library (the PriorityQueue gem) provides priority queues implemented as a C extension. This implies that the fc::PriorityQueue is a lot faster than most current alternatives and, as shown below, it compares favorably with the mentioned C extension as well.

To get an idea about how fast it is, below I provide a comparison of the time needed to push and pop a large number of elements into a priority queue. Each experiment compares FastContainers with other priority queues implementations. Since timings varies greatly among different implementations, the number of push/pop performed is chosen so to make the experiments to run for (at most) few minutes.

The following table summarizes the outputs, detailed results can be found in the next few sections. All libraries have been installed through the 'gem' command and executed using ruby v. 2.1.0.

where: results are sorted according to "avg μs per op" (higher in the list is better); μs stands for micro seconds; op stands for any operation (push or pop); the figures for priority_queue_cxx has been calculated with the results of experiments with PriorityQueue (the experiment with the highest number of operations).

require 'fc'
require 'algorithms'
require 'benchmark'

N = 50_000
algo_pq = Containers::PriorityQueue.new
fc_pq = FastContainers::PriorityQueue.new(:min)

Benchmark.bm do |bm|
  bm.report('algo:push') { N.times { |n| algo_pq.push(n.to_s, rand) } }
  bm.report('fc:push')   { N.times { |n| fc_pq.push(n.to_s, rand) } }
  bm.report('algo:pop')  { N.times { algo_pq.pop } }
  bm.report('fc:pop')    { N.times { fc_pq.pop } }
end

Output (reformatted):

Summary: FastContainers::PriorityQueues (fc) are 6461.5 times faster on pushes and 49.3 times faster on pops.

require 'fc'
require 'priority_queue'
require 'benchmark'

N = 50_000
pq_pq = PriorityQueue.new
fc_pq = FastContainers::PriorityQueue.new(:min)

Benchmark.bm do |bm|
  bm.report('pq:push') { N.times { |n| pq_pq[rand] << n.to_s } }
  bm.report('fc:push')   { N.times { |n| fc_pq.push(n.to_s, rand) } }
  bm.report('pq:pop')  { N.times { pq_pq.shift } }
  bm.report('fc:pop')    { N.times { fc_pq.pop } }
end

Output (reformatted):

Summary: FastContainers::PriorityQueues (fc) are 3.5 times faster on pushes and 23918.25 times faster on pops.

require 'fc'
require 'em-priority-queue'
require 'benchmark'

N = 500_000
em_pq = EM::PriorityQueue.new
fc_pq = FastContainers::PriorityQueue.new(:min)

Benchmark.bm do |bm|
  bm.report('em:push') { N.times { |n| em_pq.push(n.to_s, rand) } }
  bm.report('fc:push') { N.times { |n| fc_pq.push(n.to_s, rand) } }
  bm.report('em:pop')  { N.times { em_pq.pop {} } }
  bm.report('fc:pop')  { N.times { fc_pq.pop } }
end

Output (reformatted):

Summary: FastContainers::PriorityQueue (fc) are 8.5 times faster on pushes and 10.9 times faster on pops.

require 'fc'
require 'pqueue'
require 'benchmark'

N = 100_000
pq_pq = PQueue.new { |x,y| x[1] <=> y[1] }
fc_pq = FastContainers::PriorityQueue.new(:min)

Benchmark.bm do |bm|
  bm.report('pq:push') { N.times { |n| pq_pq.push([n,rand]) } }
  bm.report('fc:push')   { N.times { |n| fc_pq.push(n.to_s, rand) } }
  bm.report('pq:pop')  { N.times { pq_pq.pop } }
  bm.report('fc:pop')    { N.times { fc_pq.pop } }
end

Output (reformatted):

Summary: FastContainers::PriorityQueue (fc) are 1672.5 times faster on pushes and 7 times slower on pops.

require 'fc'
require 'priority_queue'
require 'benchmark'

N = 5_000_000
pq_pq = CPriorityQueue.new
fc_pq = FastContainers::PriorityQueue.new(:min)

Benchmark.bm do |bm|
  bm.report('pq:push') { N.times { |n| pq_pq.push(n.to_s,rand) } }
  bm.report('fc:push') { N.times { |n| fc_pq.push(n.to_s, rand) } }
  bm.report('pq:pop')  { N.times { pq_pq.delete_min } }
  bm.report('fc:pop')  { N.times { fc_pq.pop } }
end

Output (reformatted):

Summary: FastContainers::PriorityQueue (fc) are 4.58 times faster on pushes and 4.54 times faster on pops.

As it usually happens, the answer is: it depends. The evidence reported above shows that if you are only interested in the speed of push and pop methods, then priority_queue_cxx is a very good candidate. Few other important factors may make other libraries be better suited for your needs. The most glaring one is that priority_queue_cxx implementation (i.e., FastContainers::PriorityQueue) does not support changes of priorities¹. If your problem requires this feature, the best candidate appears to be PriorityQueue (0.1.2) library. Also, in making your choice, you may want to consider the fact that not all the presented libraries appear to be actively maintained (although, no one gave any problem at the time of the writing).

Here it follows a transcription of the RDoc documentation for the library. I'm adding it here because I'm having difficulties in instructing the 'gem' executable to generate the correct files on installation (everything works fine using rdoc from the command line though). Any suggestion about how to solve this problem is very welcome.

Create a new priority queue and returns it. queue_kind specifies whether to build a :min or a :max queue.

Example:

  pq = FastContainers::PriorityQueue.new(:min)

Iterates through the priority queue yielding each element to the given block. The order of the yielded elements is not defined. Returns self.

Example:

pq.each do |obj,priority|
  puts "Obj #{obj} has priority #{priority}"
end

Alias for: top

Alias for: top_key

Returns the priority of the second best element in the priority queue.

Returns true if the queue is empty

Pops the top most element from the priority queue. Returns self.

Iterates through the priority queue popping the top element and yielding it to the block. The order of yielded elements is guaranteed to be the priority order. Returns self.

Example:

ary = [100, 1, 90, 55, 6]
ary.each { |x| pq.push(x.to_s, x)}
ary.pop_each {|obj, priority| print(priority, ',') } # => 1,6,55,90,100,

Push the obj/priority pair into the queue and returns self.

Returns the size of the priority queue

Returns the object at the top of the priority queue.

Returns the priority of the object at the top of the priority queue.

The class Includes Enumerable, so that standard enumeration based methods (e.g., map, all?, any?, ...) can all be used with this container. Notice that Enumerable methods are based on #each, implying that the order used to iterate through the container is undefined.

¹ It is worth mentioning that, due to how priority queue are implemented by the C++ standard library, this implementation can't efficiently support priority changes. In any case, to support this feature would require important changes in the current API.↩