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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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__