快捷導(dǎo)航

Python實(shí)現(xiàn)的一個(gè)簡單LRU cache

更新時(shí)間：2014年09月26日 12:03:05 投稿：junjie

這篇文章主要介紹了Python實(shí)現(xiàn)的一個(gè)簡單LRU cache,本文根據(jù)實(shí)際需求總結(jié)而來,需要的朋友可以參考下

起因：我的同事需要一個(gè)固定大小的cache，如果記錄在cache中，直接從cache中讀取，否則從數(shù)據(jù)庫中讀取。python的dict 是一個(gè)非常簡單的cache,但是由于數(shù)據(jù)量很大，內(nèi)存很可能增長的過大，因此需要限定記錄數(shù)，并用LRU算法丟棄舊記錄。key 是整型，value是10KB左右的python對象

分析：

1）可以想到，在對于cache，我們需要維護(hù) key -> value 的關(guān)系

2）而為了實(shí)現(xiàn)LRU，我們又需要一個(gè)基于時(shí)間的優(yōu)先級隊(duì)列，來維護(hù) timestamp -> (key, value) 的關(guān)系

3）當(dāng)cache 中的記錄數(shù)達(dá)到一個(gè)上界maxsize時(shí)，需要將timestamp 最小的(key,value) 出隊(duì)列

4) 當(dāng)一個(gè)（key, value) 被命中時(shí)，實(shí)際上我們需要將它從隊(duì)列中，移除并插入到隊(duì)列的尾部。

從分析可以看出我們的cache 要達(dá)到性能最優(yōu)需要滿足上面的四項(xiàng)功能，對于隊(duì)表的快速移除和插入，鏈表顯然是最優(yōu)的選擇，為了快速移除，最好使用雙向鏈表，為了插入尾部，需要有指向尾部的指針。

下面用python 來實(shí)現(xiàn)：

復(fù)制代碼代碼如下:

#encoding=utf-8

class LRUCache(object):
    def __init__(self, maxsize):
        # cache 的最大記錄數(shù)
        self.maxsize = maxsize
        # 用于真實(shí)的存儲數(shù)據(jù)
        self.inner_dd = {}
        # 鏈表-頭指針
        self.head = None
        # 鏈表-尾指針
        self.tail = None

    def set(self, key, value):
        # 達(dá)到指定大小
        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:
            # 如果命中, 需要將對應(yīng)的節(jié)點(diǎn)移動到隊(duì)列的尾部
            node = self.inner_dd.get(key)
            self.move_to_tail(node)
            return node.data[1]
        return None

    def move_to_tail(self, node):
        # 只需處理在隊(duì)列頭部和中間的情況
        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]

您可能感興趣的文章: