本履歴

購入した古本の履歴と時々プログラミング

各種Heap処理速度の比較1

The Heap implementation can make significant difference

Google Code Jamも2016 R1BがそろそろということでWEBをさまよっていたらいろいろな人の優先順位付きキューがgemとして公開されていたので、自分の実装と比較してみた。

GitHub - matiasbattocchia/lazy_priority_queue: A priority queue implemented using a lazy binomial heap. It allows change priority operation. を大いに参考にしている、というか比較方法パクっている。本レース競技者はリンク先の方の実装lazy_priority_queueと自作したbinary heap, skew heap, 最後にC言語拡張のPriorityQueue (supertinou)(フィボナッチヒープ)の4実装だ。後者は実行環境がサーバ側では動かない問題点があるので参考招待選手として走ってもらう。PQueue等他との比較はリンク先のlazyとの結果から類推できる。 結果は、C-extentionが速いのは当然として、やはり前回お知らせしたとおりSkew Heapが結構速かった(知ってた)。

API Design : Whether PQ.push(key, value) or PQ.push(value)

今回やってみて感じた気付きは、当初の目的であった速度とは全く別の所、つまりAPIをどう設計するか、だった。自作以外はpush(add, <<)する時に必ず利用者がユニークなキーを割り当てなければならない。つまり、push(key, value)だ。これは今回紹介した以外の他の優先順位付きキューどれでもそうだった。しかし自分的には後で値を更新しないかもしれないのに、単にヒープソートで使いたいだけかもしれないのに(push & pop)ユニークなキーを利用者に求めるのはなにかおかしい気がして、自作の物は内部的にキー管理をし、pushされた時にpushされたオブジェクトに紐づくid(キー)を付与する形にし、それを使うかどうかは利用者任せにしたんだけれど、世界の趨勢とは真逆だったようだ。下のベンチマークの処理で言うと、自作以外はなんか知らないnを追加で引数にとっている。どっちがいいんだろうか、なかなか難しいのお。 面白いのでもうちょっと続く。

#!ruby
require 'benchmark'
require 'lazy_priority_queue'
require 'priority_queue'

def iterator n, push, pop
  n.times do |i|
    (n - i).times do |j|
      push.call i.to_s + ':' + j.to_s
    end

    i.times do
      pop.call
    end
  end
end

N = 1_000

Benchmark.bm do |bm|
  bm.report('Lazy priority queue') do
    q = MinPriorityQueue.new
    iterator N, ->(n){ q.enqueue n, rand }, ->{ q.dequeue }
  end

  bm.report('My Binary Heap') do
    q = MyHeaps::PriorityQueue.new
    iterator N, ->(n){ q.push rand }, ->{ q.pop }
  end

  bm.report('My Skew Heap') do
    q = MyHeaps::SkewHeap.new
    iterator N, ->(n){ q.push rand }, ->{ q.pop }
  end

  bm.report('PriorityQueue (supertinou)') do
    q = CPriorityQueue.new
    iterator N, ->(n){ q.push n, rand }, ->{ q.delete_min }
  end
end
       user     system      total        real
Lazy priority queue       : 15.820000   0.250000  16.070000 ( 16.286343)
My Binary Heap            : 11.440000   0.200000  11.640000 ( 11.942219)
My Skew heap              :  5.970000   0.070000   6.040000 (  6.129232)
PriorityQueue (supertinou):  3.770000   0.050000   3.820000 (  3.848521)