Posted By

unnu on 07/17/09


Tagged

ruby cache lru


Versions (?)

Who likes this?

1 person have marked this snippet as a favorite

webstic


Ruby LRU Cache


 / Published in: Ruby
 

  1. class LRUCache
  2.  
  3. def initialize(size = 10)
  4. @size = size
  5. @store = {}
  6. @lru = []
  7. end
  8.  
  9. def set(key, value)
  10. @store[key] = value
  11. set_lru(key)
  12. @store.delete(@lru.pop) if @lru.size > @size
  13. end
  14.  
  15. def get(key)
  16. set_lru(key)
  17. @store[key]
  18. end
  19.  
  20. private
  21. def set_lru(key)
  22. @lru.unshift(@lru.delete(key) || key)
  23. end
  24. end
  25.  
  26.  
  27. if __FILE__ == $0
  28. require 'test/unit'
  29.  
  30. class TestLRUCache < Test::Unit::TestCase
  31.  
  32. def setup
  33. @cache = LRUCache.new(2)
  34. end
  35.  
  36. def test_last_droped
  37. @cache.set(:a, 'a')
  38. @cache.set(:b, 'b')
  39. @cache.set(:c, 'c')
  40.  
  41. assert_nil @cache.get(:a)
  42. assert_equal 'b', @cache.get(:b)
  43. assert_equal 'c', @cache.get(:c)
  44. end
  45.  
  46. def test_get_keeps_key
  47. @cache.set(:a, 'a')
  48. @cache.set(:b, 'b')
  49. @cache.get(:a)
  50. @cache.set(:c, 'c')
  51.  
  52. assert_equal 'a', @cache.get(:a)
  53. assert_nil @cache.get(:b)
  54. assert_equal 'c', @cache.get(:c)
  55. end
  56.  
  57. def test_set_keeps_key
  58. @cache.set(:a, 'a')
  59. @cache.set(:b, 'b')
  60. @cache.set(:a, 'a')
  61. @cache.set(:c, 'c')
  62.  
  63. assert_equal 'a', @cache.get(:a)
  64. assert_nil @cache.get(:b)
  65. assert_equal 'c', @cache.get(:c)
  66. end
  67. end
  68. end

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: boscomonkey on July 28, 2009

"@lru.delete(key)" on line 22 is an O(n) search. Doesn't matter when n is small, but can be very non-performant if n is big.

You need to login to post a comment.