Подтвердить что ты не робот

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Однако, если предположить, что класс 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

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

Ответ 2

Я знаю его несколько лет спустя, но я только что реализовал то, что, по моему мнению, самый быстрый LRU Cache для 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[[email protected][email protected]].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

Ответ 4

Жемчуг rufus-lru - это еще один вариант.

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

Ответ 5

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

Ответ 6

В блоге Ruby Best Practices есть post об этом.