Efficient Ruby LRU cache

Question

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

Answer 1

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

Однако, предполагая, что класс Ruby's 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 2

Блог Ruby Best Practices содержит post об этом.

Answer 3

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

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

Answer 4

gem install ruby-cache

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

Answer 5

Руфус-LRU камень является еще одним вариантом.

Вместо подсчета она просто держит отсортированный массив ключей от старого к новому

Answer 6

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

Answer 7

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

Answer 8

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

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

https://github.com/SamSaffron/lru_redux

---

Примечание: в Рубине 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