Python LRUを使用したサイズベースのキャッシュにOrderedDictを使用する

Question

OrderedDictを使用してサイズベースのLRUを実装する方法を知りたいと思います。私が苦労している部分は、私が__contains__に電話しているときに、リンクされたリストの頭を動かすことです。次の実装は、__contains__メソッドを除いて動作しています。それは無限再帰を導く。どのように私はそれを行うことができます任意のアイデア？

from collections import OrderedDict 

class Cache(OrderedDict): 
    def __init__(self, *args, **kwds): 
    self.size_limit = kwds.pop("size_limit", None) 
    OrderedDict.__init__(self, *args, **kwds) 
    self.val_sum = 0 
    self.hit = 0 
    self.num_evicted = 0 
    self.total_req = 0 
    self._check_size_limit() 

    def __contains__(self, key): 
    self.total_req += 1 
    if OrderedDict.__contains__(self, key): 
     self.hit += 1 
     value = OrderedDict.__getitem__ (self,key) 
     self.move_item_to_the_top(key, value) 
     return True 
    else: 
     return False 

    def move_item_to_the_top(self, key, value): 
    OrderedDict.__setitem__(self, key, value) 

    def __setitem__(self, key, value): 
    OrderedDict.__setitem__(self, key, value) 
    self.val_sum += value 
    self._check_size_limit() 

    def _check_size_limit(self): 
    if self.size_limit is not None: 
     while self.val_sum > self.size_limit: 
     key, value = self.popitem(last=False) 
     self.val_sum -= value 
     self.num_evicted += 1 

    def get_cache_size(self): 
    return self.val_sum 

    def get_number_evicted(self): 
    return self.num_evicted 

    def get_hit_ratio(self): 
    return 1.00 * self.hit/self.total_req 

    def get_total_req(self): 
    return self.total_req 

    def get_hits(self): 
    return self.hit 

これは私がこれを使用しています方法です：

あなたのコードを実行

if __name__ == "__main__": 


    cache_size_B = 10 
    cache = Cache(size_limit=cache_size_B) 

    items = [(1,3), (2,3), (1,3), (3,4), (1,3), (5,5)] 


    for item in items: 

    cache_key = str(item[0]) 
    obj_size = item[1] 
    print item 

    if cache_key not in cache: 
     cache[cache_key] = int(obj_size) 

    print cache 

Answer 1

私は次のエラーを取得する：

collections.pyのライン75を見ると

python cache.py 
(1, 3) 
(2, 3) 
(1, 3) 
Traceback (most recent call last): 
    File "cache.py", line 68, in <module> 
    if cache_key not in cache: 
    File "cache.py", line 20, in __contains__ 
    self.move_item_to_the_top(key, value) 
    File "cache.py", line 26, in move_item_to_the_top 
    OrderedDict.__setitem__(self, key, value) 
    File "/usr/lib/python2.7/collections.py", line 75, in __setitem__ 
    if key not in self: 
    File "cache.py", line 20, in __contains__ 
    self.move_item_to_the_top(key, value) 
    File "cache.py", line 26, in move_item_to_the_top 
    OrderedDict.__setitem__(self, key, value) 
    File "/usr/lib/python2.7/collections.py", line 75, in __setitem__ 
    if key not in self: 

[...] 

    File "cache.py", line 26, in move_item_to_the_top 
    OrderedDict.__setitem__(self, key, value) 
    File "/usr/lib/python2.7/collections.py", line 75, in __setitem__ 
    if key not in self: 
    File "cache.py", line 20, in __contains__ 
    self.move_item_to_the_top(key, value) 
    File "cache.py", line 26, in move_item_to_the_top 
    OrderedDict.__setitem__(self, key, value) 
RuntimeError: maximum recursion depth exceeded in __instancecheck__ 

それはあなたが戻って呼び出すことが明らかになりましたCache.__contains__であり、無限ループとなる。

あなたは__contains__をoveridingずにCacheクラスを書き換えて、代わりにキャッシュへのアクセスを追跡するためにCache.__getitem__を使用することができます。

from collections import OrderedDict 


class Cache(OrderedDict): 

    def __init__(self, *args, **kwds): 
     self.size_limit = kwds.pop("size_limit", None) 
     OrderedDict.__init__(self, *args, **kwds) 
     self.val_sum = 0 
     self.hit = 0 
     self.num_evicted = 0 
     self.total_req = 0 
     self._check_size_limit() 

    def move_item_to_the_top(self, key, value): 
     del self[key] 
     OrderedDict.__setitem__(self, key, value) 

    def __getitem__(self, key): 
     self.total_req += 1 
     try: 
      value = OrderedDict.__getitem__(self, key) 
     except KeyError: 
      raise 
     else: 
      self.hit += 1 
      self.move_item_to_the_top(key, value) 
      return value 

    def __setitem__(self, key, value): 
     OrderedDict.__setitem__(self, key, value) 
     self.val_sum += value 
     self._check_size_limit() 

    def _check_size_limit(self): 
     if self.size_limit is not None: 
      while self.val_sum > self.size_limit: 
       key, value = self.popitem(last=False) 
       self.val_sum -= value 
       self.num_evicted += 1 

    def get_cache_size(self): 
     return self.val_sum 

    def get_number_evicted(self): 
     return self.num_evicted 

    def get_hit_ratio(self): 
     return 1.00 * self.hit/self.total_req 

    def get_total_req(self): 
     return self.total_req 

    def get_hits(self): 
     return self.hit 


if __name__ == "__main__": 
    cache_size_B = 10 
    cache = Cache(size_limit=cache_size_B) 

    items = [(1,3), (2,3), (1,3), (3,4), (1,3), (5,5)] 

    for item in items: 

     cache_key = str(item[0]) 
     obj_size = item[1] 
     print item 

     try: 
      cache[cache_key] 
     except KeyError: 
      cache[cache_key] = int(obj_size) 

    print cache 

あなたはまだfoo not in cacheを使用することができますが、これはミスやヒットとしてカウントされません。あなたがをカウントしたい場合はどのアクセスがれる好ましい構文try/exceptは例えば、[1]を使用します。

if __name__ == "__main__": 
    cache_size_B = 10 
    cache = Cache(size_limit=cache_size_B) 

    items = [(1,3), (2,3), (1,3), (3,4), (1,3), (5,5)] 

    for item in items: 

     cache_key = str(item[0]) 
     obj_size = item[1] 
     print item 

     try: 
      cache[cache_key] 
     except KeyError: 
      cache[cache_key] = int(obj_size) 

    print cache 

[1]これはconditionaly内のアイテムのexistanceかに基づいて何かをするれる好ましい構文でありますコンテナへの1回のアクセスだけが必要なため、リストまたはディクテーションを使用できます。