Efektywna pamięć podręczna Ruby LRU

Question

Jaki jest najbardziej wydajny sposób budowania pamięci podręcznej z dowolnymi obiektami Ruby jako kluczami, które wygasły w oparciu o ostatnio używany algorytm. Powinien używać zwykłej semantyki ruby ​​(nie równej?)

Answer 1

To przesuwa granice mojego rozumienia tego, jak Ruby wykorzystuje pamięć, ale podejrzewam, że najbardziej wydajną implementacją byłaby podwójnie związana lista, w której każdy dostęp przesuwa klucz do przodu listy, a każda wstawka upuszcza element, jeśli został osiągnięty maksymalny rozmiar.

Jednak przy założeniu, że klasa Ruby o nazwie Hash jest już bardzo wydajna, założę się, że nieco naiwne rozwiązanie polegające na dodaniu danych o wieku do Hash byłoby całkiem dobre. Oto krótki przykład zabawki, które wykonuje to:

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 

Jest prawdopodobnie szybszy sposób na znalezienie najstarszy element, a to nie jest dokładnie testowane, ale byłbym ciekaw, jak ktoś myśli, że to porównać do bardziej wyrafinowany projekt, połączona lista lub w inny sposób.

Answer 2

Blog o Ruby Best Practices ma na ten temat numer post.

Answer 3

Remaze ma dość dobrze przetestowane LRU Cache: Zobacz http://github.com/manveru/ramaze/blob/master/lib/ramaze/snippets/ramaze/lru_hash.rb

I istnieje również hashery gem przez rubyworks które powinny być bardziej skuteczne niż remaze jednym dla dużych skrytek.

Answer 4

gem install ruby-cache

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

Answer 5

rufus-LRU gem ma innej opcji.

Zamiast liczyć tylko tam posortowaną tablicę kluczy od najstarszego do najnowszego

Answer 6

rzucałem razem nowy klejnot lrucache, które mogą okazać się przydatne. Może być szybszy niż podejście Alexa do kolekcji ze znaczną liczbą elementów.

Answer 7

Bardzo prosty i szybki LRU cache używam w naszym http backend https://github.com/grosser/i18n-backend-http/blob/master/lib/i18n/backend/http/lru_cache.rb

Answer 8

Wiem, że kilka lat spóźnione, ale ja po prostu realizowane w co wierzę jest najszybszym LRU cache tam dla Ruby.

Jest również testowany i opcjonalnie bezpieczny w środowiskach wielowątkowych.

https://github.com/SamSaffron/lru_redux

---

Uwaga: w Ruby 1.9 Hash jest uporządkowane, dzięki czemu można oszukać i zbudować najszybszą LRU cache w kilku liniach kodu

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