c4se記:さっちゃんですよ☆

.。oO(さっちゃんですよヾ(〃l _ l)ノ゙☆)

.。oO(此のblogは、主に音樂考察Programming に分類されますよ。ヾ(〃l _ l)ノ゙♬♪♡)

音樂は SoundCloud に公開中です。

考察は現在は主に Scrapbox で公表中です。

Programming は GitHub で開發中です。

LRU cacheの模型をRubyで

LRU (least rescently used) cacheの模型。Ruby 1.9.3と2.0.0で確認した。
HashListとか云ふ意味不明なdata構造を捻出したが、たぶん他に使い道が無い。
unittest blockは此れ。 -> Rubyで、D言語風にassertionを直書きする簡易unit test http://c4se.hatenablog.com/entry/2013/08/15/022137

List, ListNode: 双方向連結list。おなじみ。164行。
HashList: 挿入順序を保存したhash table。中身は連結listとhash tableの組み合わせ。instance_evalとか使ってるけど見ちゃダメ。69行。
LruCache: LRU cacheの模型。今回の目的のもの。此の本体を美しく書きたいが為の、HashListだった。37行。comment等を除くと27行。

# coding=utf-8
# license: Public Domain

$DEBUG = true

# Rubyで、D言語風にassertionを直書きする簡易unit test
# http://c4se.hatenablog.com/entry/2013/08/15/022137
#
# @param test_name [String]
def unittest test_name, &proc
  if $DEBUG
    include Test::Unit::Assertions
    proc.call
    puts "#{test_name} ok."
  end
end
if $DEBUG
  require 'test/unit/assertions'
end

# {{{ List
class ListNode
  attr_accessor :prev, :next, :value

  def initialize value
    @prev = nil
    @next = nil
    @value = value
  end

  def to_s; @value.to_s end
end

# Only List#first and List#last are public low-level API.
class List
  include Enumerable
  attr_reader :first, :last

  # @param array [Enumerable]
  # @return [List]
  def self.from_a array
    list = List.new
    array.each{|item| list.push item }
    list
  end

  def initialize
    @first = nil
    @last = nil
  end

  # @param value [Object]
  # @return [List]
  def push value
    node = ListNode.new value
    if @first == nil && @last == nil
      @first = @last = node
    else
      @last.next = node
      node.prev = @last
      @last = node
    end
    self
  end

  # @return [Object]
  def pop
    if @first == nil && @last == nil
      nil
    else
      node = @last
      @last = node.prev
      @last.next = nil
      node.prev = nil
      node.value
    end
  end

  # @param value [Object]
  # @return [List]
  def shift value
    node = ListNode.new value
    if @first == nil && @last == nil
      @first = @last = node
    else
      @first.prev = node
      node.next = @first
      @first = node
    end
    self
  end

  # @return [Object]
  def unshift
    if @first == nil && @last == nil
      nil
    else
      node = @first
      @first = node.next
      @first.prev = nil
      node.next = nil
      node.value
    end
  end

  # @param index [Number]
  # @return [Object]
  def [] index
    node = get_index index
    node && node.value
  end

  # @param index [Number]
  # @param value [Object]
  # @return [Object]
  def []= index, value
    raise IndexError, "index #{index} too small for List; minimum: #{-length}" if index < -length
    node = get_index index
    if node
      node.value = value
    else
      (length .. (index - 1)).each{ push nil }
      push value
    end
    value
  end

  # @return [Number]
  def length
    reduce(0){|acc, node| acc + 1 }
  end

  # @param index [Number]
  # @return [Object]
  def delete_at index
    node = get_index index
    node.prev.next = node.next if node.prev
    node.next.prev = node.prev if node.next
    if node.prev
      node.prev.next = node.next
      @last = node.prev unless node.next
    end
    if node.next
      node.next.prev = node.prev
      @first = node.next unless node.prev
    end
    node.prev = node.next = nil
    node.value
  end

  def each &proc
    each_node{|node| proc.call node.value }
  end

  private
  def get_index index
    if index >= 0
      node_with_index = each_node.each_with_index.find{|node, i| i == index }
      node_with_index && node_with_index[0]
    else
      current = @last
      while index < -1 && current
        index += 1
        current = current.prev
      end
      current
    end
  end

  def each_node &proc
    enum = Enumerator.new do |yielder|
      break if @first == nil && @last == nil
      current = @first
      while current.next
        yielder << current
        current = current.next
      end
      yielder << current
    end
    if proc
      enum.each{|node| proc.call node }
    end
    enum
  end
end

unittest 'List' do
  list = List.new
  list.push('i').push('ro').push('ha')
  assert_equal ['i', 'ro', 'ha'], list.map{|node| node.to_s }.to_a
  assert_equal 'ha', list.pop
  assert_equal 'i', list.unshift

  list = List.from_a ['i', 'ro', 'ha']
  assert_equal 'i', list[0]
  assert_equal 'ro', list[1]
  assert_equal 'ha', list[2]
  assert_nil list[3]
  assert_equal 'ha', list[-1]
  assert_equal 'ro', list[-2]
  assert_equal 'i', list[-3]
  assert_nil list[-4]
  list[4] = 'ho'
  assert_equal ['i', 'ro', 'ha', nil, 'ho'], list.to_a
  assert_equal 'ho', list[4]
  assert_equal 5, list.length
  assert_raise(IndexError){ list[-6] = 'n' }
end
# }}}

# {{{ HashList
class HashList
  include Enumerable

  def initialize
    @list = List.new
    @hash = {}
  end

  # @param key [Symbol]
  # @return [Object]
  def get key
    pair = @hash[key]
    pair && pair.value[1]
  end

  # @param key [Symbol]
  # @param value [Object]
  # @return [HashList]
  def push key, value
    if @hash.key? key
      delete key
      push key, value
    else
      @list.push [key, value]
      @hash[key] = @list.last
    end
    self
  end

  # @return [Array] [key, value]
  def unshift
    pair = @list.unshift
    return nil unless pair
    @hash.delete pair[0]
    pair
  end

  # @param key [Symbol]
  # @return [Array] [key, value]
  def delete key
    pair = @hash[key]
    raise IndexError, '' unless pair
    unless pair.prev || pair.next
      @list.instance_eval{ @first = @last = nil }
    else
      if pair.prev
        pair.prev.next = pair.next
        @list.instance_eval{ @last = pair.prev } unless pair.next
      end
      if pair.next
        pair.next.prev = pair.prev
        @list.instance_eval{ @first = pair.next } unless pair.prev
      end
      pair.prev = pair.next = nil
    end
    @hash.delete key
    pair.value
  end

  # @param key [Symbol]
  # @return [HashList]
  def move_last key
    pair = delete key
    push *pair
  end

  # @return [Number]
  def length; @list.length end

  def each &proc
    @list.each &proc
  end
end

unittest 'HashList' do
  list = HashList.new
  list.push :k1, 'v1'
  list.push :k2, 'v2'
  assert_equal 'v1', list.get(:k1)
  assert_equal 'v2', list.get(:k2)
  assert_nil list.get :k3
  assert_equal [:k1, 'v1'], list.unshift
  assert_nil list.get :k1

  list = HashList.new
  assert_nil list.unshift

  list = HashList.new
  list.push :k1, 'v1'
  assert_equal [[:k1, 'v1']], list.to_a
  list.delete :k1
  assert_equal [], list.to_a
  assert_nil list.get(:k1)

  list = HashList.new
  list.push :k1, 'v1'
  list.push :k2, 'v2'
  assert_equal [[:k1, 'v1'], [:k2, 'v2']], list.to_a
  list.move_last :k1
  assert_equal [[:k2, 'v2'], [:k1, 'v1']], list.to_a
end
# }}}

class LruCache
  # @param size [Number]
  # @param expiration [Number] seconds
  def initialize size, expiration = Float::INFINITY
    raise ArgumentError, '' if size <= 0
    @cache = HashList.new
    @size = size
    @expiration = expiration
  end

  # @param key [Symbol]
  # @param value [Object]
  # @return [LruCache]
  def put key, value
    clean
    @cache.unshift if @cache.length >= @size
    @cache.push key, [value, Time.now.to_i + @expiration]
    self
  end

  # @param key [Symbol]
  # @return [Object]
  def get key
    clean
    value = @cache.get key
    if value
      value[1] = Time.now.to_i + @expiration
      @cache.move_last key
      value[0]
    end
  end

  private
  def clean
    @cache.select{|key, value| value[1] < Time.now.to_i }.
      each{|key, value| @cache.delete key }
  end
end

unittest 'LruCache' do
  cache = LruCache.new 2
  cache.put(:k1, 'v1').put(:k2, 'v2')
  assert_equal 'v1', cache.get(:k1)
  assert_equal 'v2', cache.get(:k2)
  cache.put :k3, 'v3'
  assert_equal 'v3', cache.get(:k3)
  assert_nil cache.get :k1

  cache = LruCache.new 1000, 1
  cache.put :k1, 'v1'
  assert_equal 'v1', cache.get(:k1)
  sleep 2
  assert_nil cache.get :k1
end
# vim:set foldmethod=marker: