Efficient Ruby LRU cache

Question

Qual è il modo più efficiente per creare una cache con oggetti Ruby arbitrari come chiavi scadute in base a un algoritmo meno recente utilizzato. Dovrebbe utilizzare la normale semantica dell'hash di Ruby (non uguale?)

Answer 1

Questo spinge i limiti della mia comprensione di come Ruby utilizza la memoria, ma sospetto che l'implementazione più efficiente sarebbe una lista doppiamente collegata in cui ogni accesso sposta la chiave in primo piano nell'elenco e ogni inserto rilascia un articolo se è stata raggiunta la dimensione massima.

Tuttavia, supponendo che la classe Hash di Ruby sia già molto efficiente, scommetterei che la soluzione un po 'ingenua di aggiungere semplicemente dati di età a un Hash sarebbe abbastanza buona. Ecco un esempio di giocattoli rapida che fa questo:

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 

C'è probabilmente un modo più veloce di trovare l'oggetto più antico, e questo non è testato, ma sarei curioso di sapere come qualcuno pensa questo a fronte di un maggiore design sofisticato, elenco collegato o altro.

Answer 2

Il blog di Ruby Best Practices ha uno post.

Answer 3

Remaze ha un ragionevolmente ben collaudato LRU cache: Vedere http://github.com/manveru/ramaze/blob/master/lib/ramaze/snippets/ramaze/lru_hash.rb

E c'è anche il hashery gemma da rubyworks che dovrebbe essere più efficiente rispetto alla remaze uno per i grandi cache.

Answer 4

gem install ruby-cache

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

Answer 5

La gemma rufus-LRU è un'altra opzione.

Invece di un conteggio solo mantiene un array ordinato di chiavi dal più vecchio al più recente

Answer 6

ho buttato insieme un nuovo gioiello lrucache che si possono trovare utili. Potrebbe essere più veloce dell'approccio di Alex per le collezioni con un numero significativo di elementi.

Answer 7

molto semplice e veloce di cache LRU che uso nel nostro backend http https://github.com/grosser/i18n-backend-http/blob/master/lib/i18n/backend/http/lru_cache.rb

Answer 8

So che è un paio di anni di ritardo, ma ho appena realizzato quello che credo sia il più veloce LRU cache là fuori per Ruby.

È inoltre testato e opzionalmente sicuro da utilizzare in ambienti con più thread.

https://github.com/SamSaffron/lru_redux

---

Nota: in Ruby 1.9 Hash è ordinato, in modo da poter imbrogliare e costruire la cache LRU più veloce in poche righe di codice

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