Caché de LRU de Ruby eficiente

Question

¿Cuál es la forma más eficiente de construir un caché con objetos de Ruby arbitrarios como claves caducadas en función de un algoritmo utilizado menos recientemente? Debería usar la semántica de hashing normal de Ruby (¿no es igual?)

Answer 1

Esto traspasa los límites de mi comprensión de cómo Ruby usa memoria, pero sospecho que la implementación más eficiente sería una lista doblemente enlazada donde cada acceso mueve la tecla al frente de la lista, y cada inserción deja caer una artículo si se alcanzó el tamaño máximo.

Sin embargo, suponiendo que la clase Hash de Ruby ya es muy eficiente, apostaría a que la solución ingenua de simplemente agregar datos de edad a un Hash sería bastante buena. He aquí un ejemplo de juguete rápida que hace esto:

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 

Probablemente hay una manera más rápida de encontrar el elemento más antiguo, y esto no ha sido probada, pero tengo curiosidad de saber cómo alguien piensa que esto se compara con una mayor diseño sofisticado, lista vinculada o de lo contrario.

Answer 2

El blog Ruby Best Practices tiene un post al respecto.

Answer 3

Remaze tiene un caché LRU razonablemente bien probado: Ver http://github.com/manveru/ramaze/blob/master/lib/ramaze/snippets/ramaze/lru_hash.rb

Y también existe la hashery joya por rubyworks que debería ser más eficiente que el Remaze uno para grandes cachés.

Answer 4

gem install ruby-cache

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

Answer 5

La gema rufus-LRU es otra opción.

En lugar de un recuento que sólo mantiene un arreglo ordenado de las llaves del más antiguo al más reciente

Answer 6

Tiré juntos una nueva joya lrucache que pueden serle de utilidad. Puede ser más rápido que el enfoque de Alex para las colecciones con un número significativo de elementos.

Answer 7

muy simple y rápida caché LRU utilizo en nuestro back-end http https://github.com/grosser/i18n-backend-http/blob/master/lib/i18n/backend/http/lru_cache.rb

Answer 8

Sé que es un par de años de retraso, pero simplemente implementa lo que creo que es el más rápido caché LRU por ahí para Ruby.

También se ha probado y, opcionalmente, es seguro para su uso en entornos de múltiples hilos.

https://github.com/SamSaffron/lru_redux

---

Nota: en Ruby se ordena 1,9 Hash, por lo que puede engañar y construir el caché LRU más rápido en unas pocas líneas de código

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