BPStudy #29 のテスト駆動開発の話でペアプログラミングで、Last Recently Used キャッシュ (LRU)を自動テストやりながら、実装しようという部分がありました。
最初に僕は二つのリストで１０分くらいで実装したんですけど、やっぱりパフォーマンスが出ないと思ったから、時間が終わったまでに、pythonの辞書で書き直した。
最終版はこれでした。
lru.py
#:coding=utf8:
class LRU(object):
def __init__(self, size=2):
self.size = size
self.name_list = []
self.value_dict = {}
def put(self, name, value):
if name not in self:
self.name_list.append(name)
self.value_dict[name] = value
if len(self.name_list) > self.size:
old_name = self.name_list[0]
del self.name_list[0]
self.value_dict.pop(old_name)
def get(self, name):
if name in self.name_list:
self.name_list.remove(name)
self.name_list.append(name)
return self.value_dict[name]
else:
return None
def __contains__(self, key):
try:
self.value_dict[key]
return True
except KeyError:
return False
def __setitem__(self, key, value):
self.put(key, value)
def __getitem__(self, key):
return self.get(key)
def __len__(self):
return len(self.name_list)
lru_test.py
from unittest import TestCase
from lru import LRU
class LRUTestCase(TestCase):
def test_put(self):
lru = LRU()
lru.put("monjudoh", "monju")
self.assertEquals(lru.get("monjudoh"), "monju")
def test_multi_put(self):
lru = LRU()
lru.put("monjudoh", "monju")
self.assertEquals(lru.get("monjudoh"), "monju")
lru.put("monjudoh", "monju2")
self.assertEquals(lru.get("monjudoh"), "monju2")
self.assertEquals(len(lru), 1)
def test_loss(self):
lru = LRU()
lru.put("monjudoh", "monju1")
lru.put("ian", "monju2")
lru.put("test", "monju3")
self.assertEquals(lru.get("monjudoh"), None)
def test_use(self):
lru = LRU()
lru.put("monjudoh", "monju1")
lru.put("ian", "monju2")
self.assertEquals(lru.get("monjudoh"), "monju1")
lru.put("test", "monju3")
self.assertEquals(lru.get("ian"), None)
self.assertEquals(lru.get("monjudoh"), "monju1")
def test_size(self):
lru = LRU(size=4)
lru.put("monjudoh", "monju1")
self.assertEquals(len(lru), 1)
lru.put("ian", "monju2")
self.assertEquals(len(lru), 2)
lru.put("test", "monju3")
self.assertEquals(len(lru), 3)
lru.put("test2", "monju4")
self.assertEquals(len(lru), 4)
lru.put("test3", "monju5")
self.assertEquals(len(lru), 4)
lru.put("test5", "monju6")
def test_bigger(self):
lru = LRU(size=4)
lru.put("monjudoh", "monju1")
lru.put("ian", "monju2")
lru.put("test", "monju3")
self.assertEquals(lru.get("monjudoh"), "monju1")
lru.put("test2", "monju4")
lru.put("test3", "monju5")
self.assertEquals(lru.get("ian"), None)
self.assertEquals(lru.get("test"), "monju3")
self.assertEquals(lru.get("test2"),"monju4")
self.assertEquals(lru.get("test3"),"monju5")