手撸LFU算法

LFU 淘汰策略: Least Recently Used，也就是最久没有被使用的数据，每次淘汰使用次数最少的数据。

from collections import OrderedDict, defaultdict

"""
    LRU是淘汰那些早使用的，LFU是淘汰那些使用次数最少的
"""


class LFU:
    def __init__(self, capacity):
        """
               Initialize the LFUCache with the given capacity.
        """
        self.capacity = capacity
        self.cache = {}  # stores the key-value pairs
        self.freq = OrderedDict()  # stores the frequency of access for each key

    def get(self, key):
        if key not in self.cache.keys():
            return -1
        cur_feq = self.freq[key]
        self.freq[key] = cur_feq + 1
        return self.cache[key]

    def put(self, key, value):
        if self.capacity == 0:
            return
        if key in self.cache:
            self.cache[key] = value
            self.freq[key] += 1

        if len(self.cache) >= self.capacity:
            del self.cache[key]
            del self.freq[key]

        self.cache[key] = value
        self.freq[key] = 1

__END__