本履歴

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

Rubyだとダイクストラ最短路アルゴリズムはバイナリヒープよりスキューヒープ実装の方が速い?!

Skew Heap might be way faster than Binary Heap in Dijkstra Algorithm in Ruby

気になっていたデータ構造Skew heap - Wikipedia, the free encyclopediaを筆のすさびにRubyで書いてみたら、結構速い。もしやとchange_keyも作ってダイクストラの最短経路アルゴリズムに使うと、以前紹介したバイナリヒープ版より2,3割速いようだ。頂点・辺数が小さければ差はほぼないけれど。Rubyは配列アクセス遅いからね、、narrayが標準ライブラリに入ってくれると嬉しいんだが・・・。いずれにせよ、速いことは良いことだ。ただし注意しなくちゃいけないのは、この構造はバランストで無いので、ハックできるようなコンテストだと、スキューヒープが線形な木構造になるような入力を意図的に作られてしまい、簡単に落とされると思う。 SkewHeapNodeクラスのelementに比較可能なオブジェクトを入れるようになっている。ではよろしくお願いします。

#!ruby
#Last Updated at 04/29/2016

#Skew Heap
#ストアするデータは<=>で比較可能でなければならない

class SkewHeapNode
    attr_accessor :element, :left, :right, :parent
    def initialize(element, left = nil, right = nil)
        @element = element
        @left = left
        @right = right   
        @parent = nil
    end
end

class SkewHeap
    attr_reader :size, :root
    def initialize
        @root = nil
        @size = 0
        @position = {}
        @id = 0
    end

    def add(element)
        @id += 1
        @size += 1
        node = SkewHeapNode.new(element)
        @position[@id] = node
        @root = merge(@root, node)
        @id
    end

    def pop
        return nil if @size==0
        @size -= 1
        element = @root.element
        @root = merge(@root.left, @root.right)
        @root.parent = nil if @root
        element
    end

  def change_key(target_id, new_element)
    node = @position[target_id]
    return nil unless node
    if heap_order_property_satisfied?(node, new_element)
        node.element = new_element
    else
        temp = merge(node.left, node.right)
        temp.parent = node.parent if temp
            if node.parent
            if node.parent.left == node
                node.parent.left = temp
            else
                node.parent.right = temp
            end
        else
            @root = temp
        end
        node.element = new_element
        node.left = nil
        node.right = nil
        node.parent = nil

        @root = merge(@root, node)
        @root.parent = nil if @root
    end
    self
  end

  def empty?
    @size == 0
  end

  alias :push :add
  alias :<< :add
  alias :length :size

private
    #p's parent is never changed
    #O(log n)-expected time
    def merge(p, q)
        return p if q.nil?
        return q if p.nil?
        p, q = q, p if p.element > q.element
        q.parent = p
        p.right = merge(p.right, q)
        p.right, p.left = p.left, p.right
        p
    end

    def heap_order_property_satisfied?(node, new_element)
        if node.parent
            return false if node.parent.element > new_element
        end
        if node.left
            return false if node.left.element < new_element
        end
        if node.right
            return false if node.right.element < new_element
        end
        true
    end
end