起因：我的同事需要一個固定大小的cache，如果記錄在cache中，直接從cache中讀取，否則從數據庫中讀取。python的dict 是一個非常簡單的cache,但是由于數據量很大，內存很可能增長的過大，因此需要限定記錄數，并用LRU算法丟棄舊記錄。key 是整型，value是10KB左右的python對象
分析：
1）可以想到，在對于cache，我們需要維護 key -> value 的關系
2）而為了實現LRU，我們又需要一個基于時間的優先級隊列，來維護?? timestamp? -> (key, value) 的關系
3）當cache 中的記錄數達到一個上界maxsize時，需要將timestamp 最小的(key,value) 出隊列
4) 當一個（key, value) 被命中時，實際上我們需要將它從隊列中，移除并插入到隊列的尾部。
從分析可以看出我們的cache 要達到性能最優需要滿足上面的四項功能，對于隊表的快速移除和插入，鏈表顯然是最優的選擇，為了快速移除，最好使用雙向鏈表，為了插入尾部，需要有指向尾部的指針。
下面用python 來實現：
#encoding=utf-8
class LRUCache(object):
??? def __init__(self, maxsize):
??????? # cache 的最大記錄數
??????? self.maxsize = maxsize
??????? # 用于真實的存儲數據
??????? self.inner_dd = {}
??????? # 鏈表-頭指針
??????? self.head = None
??????? # 鏈表-尾指針
??????? self.tail = None
??? def set(self, key, value):
??????? # 達到指定大小?????
??????? if len(self.inner_dd) >= self.maxsize:
??????????? self.remove_head_node()
??????? node = Node()
??????? node.data = (key, value)
??????? self.insert_to_tail(node)
??????? self.inner_dd[key] = node
??? def insert_to_tail(self, node):
??????? if self.tail is None:
??????????? self.tail = node
??????????? self.head = node
??????? else:
??????????? self.tail.next = node
??????????? node.pre = self.tail
??????????? self.tail = node
??? def remove_head_node(self):
??????? node = self.head
??????? del self.inner_dd[node.data[0]]
??????? node = None
??????? self.head = self.head.next
??????? self.head.pre = None
??? def get(self, key):
??????? if key in self.inner_dd:
??????????? # 如果命中, 需要將對應的節點移動到隊列的尾部
??????????? node = self.inner_dd.get(key)
??????????? self.move_to_tail(node)
??????????? return node.data[1]
??????? return None
??? def move_to_tail(self, node):
??????? # 只需處理在隊列頭部和中間的情況
??????? if not (node == self.tail):
??????????? if node == self.head:
??????????????? self.head = node.next
??????????????? self.head.pre = None
??????????????? self.tail.next = node
??????????????? node.pre = self.tail
??????????????? node.next = None
??????????????? self.tail = node
??????????? else:
??????????????? pre_node = node.pre
??????????????? next_node = node.next
??????????????? pre_node.next = next_node
??????????????? next_node.pre = pre_node
??????????????? self.tail.next = node
??????????????? node.pre = self.tail
??????????????? node.next = None
??????????????? self.tail = node
class Node(object):
??? def __init__(self):
??????? self.pre = None
??????? self.next = None
??????? # (key, value)
??????? self.data = None
??? def __eq__(self, other):
??????? if self.data[0] == other.data[0]:
??????????? return True
??????? return False
??? def __str__(self):
?????? return str(self.data)
if __name__ == '__main__':
??? cache = LRUCache(10)
??? for i in xrange(1000):
??????? cache.set(i, i+1)
??????? cache.get(2)
??? for key in cache.inner_dd:
??????? print key, cache.inner_dd[key]
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
