learn simple LRU

learn_simple_lru.md

LRU Cache 學習

LRU是在一個有限大小的快取空間，保持最近使用過的資料的一種快取機制，可以透過getter、setter方法搭配一個有序字典物件來實現

import collections


class LRUCache(object):
    """ Simple LRU Cache
    """
    
    def __init__(self, size=10):
        """ 實例化時可透過size參數設定cache大小
        """
        self.size = size
        self._dict = collections.OrderedDict()

    def __contains__(self, key):
        """ 讓cache可以使用 in 來確認key值是否存在
        """
        return key in self._dict

    def __getitem__(self, key):
        """ 讓cache可以使用value = cache[key]的方式取值
        """
        return self.get(key)

    def __setitem__(self, key, value):
        """ 讓cache可以使用cache[key] = value的方式設值
        """
        return self.set(key, value)
        
    def get(self, key):
        """ 取值。
            如果要取得的key已經在字典中，則將該值移動到最新的位置，如果沒有就回傳None
        """
        if key in self._dict:
            value = self._dict.pop(key)
            self._dict[key] = value
            return value
        return None
    
    def set(self, key, value):
        """ 設值。
            如果該key已經存在cache中，則更新值，並調整位置至最新。
            如果該key尚未在cache中，則先確定cache長度是否已經到達長度限制，
            若已經達到長度限制的話則將最舊一筆資料剔除，再新增新值，
            否則直接新增值
        """
        try:
            self._dict.pop(key)
        except KeyError:
            if len(self._dict) >= self.size:
                self._dict.popitem(last=False)
        self._dict[key] = value
        
    def keys(self):
        return self._dict.keys()

測試:

import random

# 設置size為10的LRU cache
cache = LRUCache(10)

# 先預設給他10個範圍是1~20的亂數值
for i in range(10):
    cache[i] = random.randint(1, 20)

print(cache)

# 隨機抽取10筆
for i in range(10):
    i = random.randint(1, 10)
    print('cache keys: ', list(cache.keys()))
    if cache[i]:
        print('key: {} 存在'.format(i))
    else:
        print('key: {} 不存在'.format(i))