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: