简单实现LRU - Python

LRU (Least Recently Used) 最近最久未使用

In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions—or algorithms—that a computer program or a hardware-maintained structure can follow in order to manage a cache of information stored on the computer. When the cache is full, the algorithm must choose which items to discard to make room for the new ones. --Wikipedia

更新：

最近刚好看到 Leetcode 上一道关于LRUCache的题

Design and implement a data structure for Least Recently Used (LRU) cache.

It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

以下是实现：(代码可以在 Github 上找到)

class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.__values = {}
        self.__access = []

    def get(self, key):
        """
        :rtype: int
        """
        if key in self.__values:
            self.__access.remove(key)
            self.__access.append(key)
            return self.__values[key]
        else:
            return -1

    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if not self.capacity:
            return
        if key in self.__values:
            self.__access.remove(key)
        else:
            while len(self.__values) >= self.capacity:
                self.cleanup()
        self.__access.append(key)
        self.__values[key] = value

    def cleanup(self):
        del self.__values[self.__access.pop(0)]

使用Python来实现LRUCacheDict

dict容量固定
记录每个key的最后一次访问时间与过期时间
在每次增加/查询操作时，对dict进行清理，先清除过期的key，然后清除最早访问的key

具体实现：

以下代码可以在 Github 上找到

import time
from collections import OrderedDict


class LRUCacheDict(object):
    def __init__(self, expiration=15*60, maxsize=128):
        self.expiration = expiration
        self.maxsize = maxsize
        self.__expire_times = OrderedDict()
        self.__access_times = OrderedDict()
        self.__values = {}

    def __setitem__(self, key, value):
        t = int(time.time())
        self.__delitem__(key)
        self.__values[key] = value
        self.__access_times[key] = t
        self.__expire_times[key] = t + self.expiration
        self.cleanup()

    def __getitem__(self, key):
        t = int(time.time())
        del self.__access_times[key]
        self.__access_times[key] = t
        self.cleanup()
        return self.__values[key]

    def __delitem__(self, key):
        if key in self.__values:
            del self.__values[key]
            del self.__access_times[key]
            del self.__expire_times[key]

    def size(self):
        return len(self.__values)

    def clear(self):
        self.__values.clear()
        self.__access_times.clear()
        self.__expire_times.clear()

    def cleanup(self):
        t = int(time.time())
        for key, expire in self.__expire_times.iteritems():
            if expire < t:
                self.__delitem__(key)

        while self.size() > self.maxsize:
            for key in self.__access_times:
                self.__delitem__(key)
                break

已上实现参考：

pypi.python.org/pypi/py_lru…