Bộ nhớ cache hiệu quả của Ruby LRU

Question

Cách hiệu quả nhất để xây dựng bộ nhớ cache với các đối tượng Ruby tùy ý là các khóa hết hạn dựa trên một thuật toán ít được sử dụng gần đây nhất. Nó nên sử dụng ngữ nghĩa băm bình thường của Ruby (không bằng nhau?)

Answer 1

Điều này đẩy ranh giới hiểu biết về cách Ruby sử dụng bộ nhớ, nhưng tôi nghi ngờ rằng việc triển khai hiệu quả nhất sẽ là danh sách được liên kết gấp đôi, mỗi lần truy cập sẽ chuyển khóa vào trước danh sách. mục nếu đạt đến kích thước tối đa.

Tuy nhiên, giả sử lớp Hash của Ruby đã rất hiệu quả, tôi muốn đặt cược rằng giải pháp hơi ngây thơ về việc thêm dữ liệu tuổi vào Hash sẽ khá tốt. Dưới đây là một ví dụ đồ chơi nhanh chóng mà thực hiện điều này:

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ó lẽ một cách nhanh hơn của việc tìm kiếm mục lâu đời nhất, và điều này không được kiểm tra kỹ lưỡng, nhưng tôi tò mò muốn được biết làm thế nào có ai nghĩ này so với một nhiều thiết kế tinh vi, danh sách liên kết hoặc cách khác.

Answer 2

Blog thực tiễn tốt nhất của Ruby có số post về nó.

Answer 3

Remaze có LRU cache một cách hợp lý cũng được thử nghiệm: Xem http://github.com/manveru/ramaze/blob/master/lib/ramaze/snippets/ramaze/lru_hash.rb

Và đó cũng là hashery đá quý bởi rubyworks mà nên hiệu quả hơn so với remaze một cho lưu trữ lớn.

Answer 4

gem install ruby-cache

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

Answer 5

Các đá quý rufus-LRU là một tùy chọn.

Thay vì đếm nó chỉ giữ một mảng được sắp xếp các phím từ cũ nhất đến mới nhất

Answer 6

Tôi ném cùng một viên ngọc mới lrucache mà bạn có thể thấy hữu ích. Nó có thể nhanh hơn cách tiếp cận của Alex đối với các bộ sưu tập với một số lượng đáng kể các phần tử.

Answer 7

Rất đơn giản và nhanh chóng bộ nhớ cache LRU tôi sử dụng trong http backend của chúng tôi https://github.com/grosser/i18n-backend-http/blob/master/lib/i18n/backend/http/lru_cache.rb

Answer 8

Tôi biết một vài năm cuối, nhưng tôi chỉ thực hiện những gì tôi tin là LRU cache nhanh nhất hiện có cho Ruby.

Nó cũng được kiểm tra và tùy chọn an toàn để sử dụng trong môi trường nhiều luồng.

https://github.com/SamSaffron/lru_redux

---

Lưu ý: trong Ruby 1,9 Hash được ra lệnh, vì vậy bạn có thể lừa gạt và xây dựng bộ nhớ cache LRU nhanh nhất trong một vài dòng mã

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