高效的Ruby LRU缓存

Question

使用任意Ruby对象构建缓存的最有效方法是基于最近最少使用的算法过期的密钥.它应该使用Ruby的正常散列语义(不相等？)

Answer 1

我知道它在几年晚,但我只是实现了我认为是最快的LRU缓存在那里的Ruby.

它还经过测试,可选择安全地在多线程环境中使用.

https://github.com/SamSaffron/lru_redux

注意:在Ruby 1.9中,Hash是有序的,因此您可以在几行代码中欺骗并构建最快的LRU缓存

class LruRedux::Cache19

  def initialize(max_size)
    @max_size = max_size
    @data = {}
  end

  def max_size=(size)
    raise ArgumentError.new(:max_size) if @max_size < 1
    @max_size = size
    if @max_size < @data.size
      @data.keys[0..@max_size-@data.size].each do |k|
        @data.delete(k)
      end
    end
  end

  def [](key)
    found = true
    value = @data.delete(key){ found = false }
    if found
      @data[key] = value
    else
      nil
    end
  end

  def []=(key,val)
    @data.delete(key)
    @data[key] = val
    if @data.length > @max_size
      @data.delete(@data.first[0])
    end
    val
  end

  def each
    @data.reverse.each do |pair|
      yield pair
    end
  end

  # used further up the chain, non thread safe each
  alias_method :each_unsafe, :each

  def to_a
    @data.to_a.reverse
  end

  def delete(k)
    @data.delete(k)
  end

  def clear
    @data.clear
  end

  def count
    @data.count
  end

  # for cache validation only, ensures all is sound
  def valid?
    true
  end
end

Answer 2

这推动了我对Ruby如何使用内存的理解的界限,但我怀疑最有效的实现将是一个双向链接列表,其中每个访问都将密钥移动到列表的前面,并且每个插入都会丢弃一个项目,如果最大值尺寸已达到.

然而,假设Ruby的Hash类已经非常有效,我敢打赌,简单地将年龄数据添加到a的有点天真的解决方案Hash会相当不错.这是一个快速的玩具示例:

class Cache
  attr_accessor :max_size

  def initialize(max_size = 4)
    @data = {}
    @max_size = max_size
  end

  def store(key, value)
    @data.store key, [0, value]
    age_keys
    prune
  end

  def read(key)
    if value = @data[key]
      renew(key)
      age_keys
    end
    value
  end

  private # -------------------------------

  def renew(key)
    @data[key][0] = 0
  end

  def delete_oldest
    m = @data.values.map{ |v| v[0] }.max
    @data.reject!{ |k,v| v[0] == m }
  end

  def age_keys
    @data.each{ |k,v| @data[k][0] += 1 }
  end

  def prune
    delete_oldest if @data.size > @max_size
  end
end

可能有一种更快的方法来找到最老的项目,这还没有经过彻底的测试,但我很想知道有人认为这与更复杂的设计,链接列表或其他方式相比.