Эффективный кэш Ruby LRU

Question

Какой самый эффективный способ построить кэш с произвольными объектами Ruby в качестве ключей, срок действия которых истек, на основе наименее недавно использованного алгоритма. Он должен использовать нормальную семантику хеширования в Ruby (не равно?)

Answer 1

Я знаю, что это несколько лет назад, но я только что реализовал, как мне кажется, самый быстрый LRU Cache для Ruby.

Он также протестирован и при необходимости безопасен для использования в многопоточных средах.

https://github.com/SamSaffron/lru_redux

---

Примечание: в Ruby 1.9 хэш упорядочен, так что вы можете обмануть и построить самый быстрый 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 использует память, но я подозреваю, что наиболее эффективной реализацией будет список с двойной связью, где каждый доступ перемещает ключ в начало списка, а каждая вставка отбрасывает элемент если достигнут максимальный размер.

Однако, предполагая, что класс Hash Руби уже очень эффективен, я бы поспорил, что довольно наивное решение простого добавления данных о возрасте в 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

Вероятно, существует более быстрый способ найти самый старый элемент, и он не проходит тщательной проверки, но мне было бы любопытно узнать, как кто-то считает, что это сравнивается с более сложным дизайном, связанным списком или чем-то другим.

Answer 3

Remaze имеет достаточно хорошо протестированный кэш LRU: см. http://github.com/manveru/ramaze/blob/master/lib/ramaze/snippets/ramaze/lru_hash.rb

И есть также камень hashery от rubyworks , который должен быть более эффективным, чем оставшийся для больших кэшей.

Answer 4

Я собрал новый драгоценный камень lrucache , который вы можете найти полезным. Это может быть быстрее, чем подход Алекса для коллекций со значительным количеством элементов.

Answer 5

Драгоценный камень Руфус-Лру - еще один вариант.

Вместо подсчета он просто сохраняет отсортированный массив ключей от самых старых до самых новых

Answer 6

Очень простой и быстрый кэш lru, который я использую в нашем http-интерфейсе https://github.com/grosser/i18n-backend-http/blob/master/lib/i18n/backend/http/lru_cache.rb

Answer 7

Блог Ruby Best Practices содержит сообщение .

Answer 8

gem install ruby-cache

-> http://www.nongnu.org/pupa/ruby-cache-README.html