LRU Hash

Ruby では、 オブジェクトをキャッシュする用途に添付ライブラリ WeakRef が使えるようになっています。 ただし、 WeakRef を使うとオブジェクトをゴミ集め時に廃棄するため、 短命のキャッシュにしか使えません。 そこで、 ゴミ集めの頻度よりも長い時間に渡ってキャッシュさせる目的に、 LRU (Least Recently Used) を使った揮発性のハッシュ表 LRU Hash を使ってみます。 このタイプのデータ構造は、 これまで参照カウンタでゴミ集めする言語用に書いて使いまわしてきましたが、 Ruby はゴミ集めがトレース方式なので、 ほんの少し勝手が違います。

LRU Hash に収納できるキー値の組の個数には上限があります。 個数の上限は LRU Hash オブジェクトの生成時に指定します。 上限値を使っている途中で変更することはできません。 さらに、 格納しているキー値に順番があります。 新しいキー値は、 先頭に追加します。 先頭以外のキー値を読み書きすると、 先頭へ移動します。 追加時に、 収納済みの個数が上限に達しているときは、 末尾のキー値を捨てます。

並びに順番があって、 途中から抜き取ることがあるため、 使用中のキー値は双方向リストの要素にするのが適切です。 さらに、 個数に上限があることから、 使用中のキー値の個数と、 未使用のキー値の個数の和は、 常に上限値に一致しています。 そこで未使用のキー値も双方向リストの要素とし、 2 本のリストの両端をつないでリングにすると、 このリングの要素数は常に上限値になって個数が不変になります。 ただし、 リストの端をそのままつないでしまうと、 境界チェックに余計な条件式が必要になるので、 ダミーの犠牲要素を 2 個つくって、 リストを犠牲要素を挟んでリングにしておきます。 犠牲要素の一つは top で、 これの順方向に使用中の要素を並べます。 末尾の使用中の要素の順方向の次を、 もう一つの犠牲要素で bot (bottom) とします。 top から順方向にリングの要素を辿っていくと、 使用中リスト、 bot、 未使用リストへと進んでから、 top に戻ってきます。

使用中リストからキーを探すために、 top から bot の手前までを順に見ていくと、 リストが長いときに不利になります。 そのため、 リングの要素への索引を Hash オブジェクトにしておきます。 リングの都合の良い点は、 要素の順番を変えても、 要素オブジェクトの双方向リンクの参照が変化するだけで、 要素オブジェクト自体は同じオブジェクトのままなことです。 そのため、 索引の Hash オブジェクトの値を要素オブジェクトへの参照にしてもかまいません。

要素が空の LruHash オブジェクトを上限値を指定して生成します。 犠牲要素を生成し、 top と bot で参照します。 bot と top の間に上限値の個数分の空要素を生成してリストにつなぎます。 さらに空 Hash オブジェクトを生成し、 idx で参照します。

class LruHash
  include Enumerable

  # item: ...<-> [TOP] <-> used <-> [BOT] <-> free <-> [TOP] <-> used <->...
  Item = Struct.new(:forw, :back, :key, :value)

  attr_reader :limit

  def initialize(limit=8)
    @limit = limit
    @top = Item.new(nil, nil, nil, nil)
    @bot = Item.new(nil, nil, nil, nil)
    @top.forw = @top.back = @bot
    @bot.forw = @bot.back = @top
    @limit.times {
      item = Item.new(@top, @top.back, nil, nil)
      item.back.forw = item
      item.forw.back = item
    }
    @idx = {}
  end

#@<idx への委譲メソッド@>
#@<読み書き@>
#@<each@>
#@<assoc@>
#@<要素移動@>
#@<キーの要素を削除@>
#@<全部削除@>
end

idx インスタンス変数にとって、 使用中要素は、 Item オブジェクトを挟んだ間接参照にすぎません。

#@<idx への委譲メソッド@>=
  def size() @idx.size end
  def key?(key) @idx.key?(key) end
  alias member? key?
  alias include? key?
  def keys() @idx.keys end
  def values() @idx.values.map {|item| item.value } end

each メソッドも idx への委譲でも良いかもしれませんけど、 順番を目の当たりにしたいという用途を考慮して top と bot の間の使用中リストの要素を順に訪れることにします。 each は要素の順番を変更しません。 yield する前に次へ進めて、 進める前の要素のキーと値を yield しているのは、 ブロック中で key を削除可能にするための工夫です。

#@<each@>=
  def each()
    block_given? or return enum(:each)
    item = @top.forw
    while ! @bot.equal?(item)
      item = item.forw
      yield item.back.key, item.back.value
    end
    self
  end

他のメソッドは、 idx のハッシュ表と、 top・bot のリングの両方を使った操作をします。 その手のハイブリッドの操作を、 キーに対する Item オブジェクトを返す assoc メソッドに閉じ込めることにします。

#@<読み書き@>=
  def [](key) @idx.key?(key) ? assoc(key).value : nil end
  def []=(key, value) assoc(key).value = value end

このメソッドは、 キーが一致する Item オブジェクトを探して、 使用リストの先頭へ移動します。 見つからなかったときは、 先頭に新しい要素を移動します。 新しい要素を求めるには、 未使用リストに要素があるとき (@bot.forw) はそれを使います。 ないときは、 使用中リストの末尾要素 (@bot.back) を使います。

#@<assoc@>=
  def assoc(key)
    if @idx.key?(key)
      item = @idx[key]
    else
      item = @bot.forw
      if @top.equal?(item)
        item = @bot.back
        @idx.delete(item.key)
      end
      @idx[key] = item
      item.key = key
      item.value = nil
    end
    move_after(@top, item)
    item
  end

双方向リンクの要素のつなぎかえは move_after(e1, e2) メソッドでおこないます。 このメソッドは e1 の順方向の次の要素が e2 になるように e2 を移動します。

#@<要素移動@>=
  def move_after(dst, src)
    src_back = src.back
    src_forw = src.forw
    src_forw.back = src_back
    src_back.forw = src_forw
    dst_forw = dst.forw
    dst.forw = src
    src.back = dst
    src.forw = dst_forw
    dst_forw.back = src
  end

キーを指定して、 要素を一個削除すると、 未使用リストの末尾 (@top.back) へ要素を移動し、 idx からキーを削除します。

#@<キーの要素を削除@>=
  def delete(key)
    if ! @idx.key?(key)
      (block_given?) ? (yield key) : nil
    else
      item = @idx[key]
      r = item.value
      item.key = item.value = nil
      move_after(@top.back, item)
      @idx.delete(key)
      r
    end
  end

全部を削除して空にするには、 使用中リスト内のすべての要素のキーと値を nil で潰してから、 top のすぐ次を bot にします。

#@<全部削除@>=
  def clear()
    item = @top.forw
    while ! @bot.equal?(item)
      item.key = item.value = nil
      item = item.forw
    end
    @bot = @top.forw
    @bot.key = @bot.value = nil
    @idx.clear
    self
  end