Python с использованием OrderedDict для кеширования с размерами с LRU

Question

Мне интересно, как я могу реализовать LRU на основе размера, используя OrderedDict. Часть, с которой я борюсь, - это переместить голову связанного списка, когда я звоню __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

Запуск кода я получаю следующее сообщение об ошибке:

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__ 

Глядя на линии 75 из collections.py это показывает, что ваш обратный вызов Cache.__contains__, что приводит к бесконечному циклу.

Вы можете переписать Cache класс без overiding __contains__ и вместо того, чтобы использовать 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 сделать что-то на основе существования или не элемента в или dict, потому что для этого требуется только один доступ к контейнеру.