数据结构-缓存算法

Posted on | Post modified: | In
Words count in article: 997

LRU缓存

LRU（Least recently used，最近最少使用）首先淘汰最长时间未被使用的页面。

leetcode 146. LRU缓存机制
链接
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思路：
get()相当于读，put()即是写。一次读或写意味着对缓存块使用了一次，该缓存的优先级就提高。

思路比较简单，基于哈希表和双向链表。先通过哈希表查找缓存块的位置，也就是缓存块在链表中的位置。然后在表中删除该缓存块，重新把该缓存块置于链表表尾。如果插入后缓存已经满了，那就把表头的缓存块丢掉，同时删除哈希表对应的记录。

代码：

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Node(object):
    def __init__(self, k, v):
        self.key = k
        self.val = v
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.dic = dict()
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dic:
            node = self.dic[key]
            self.remove(node)
            self.add(node)
            return node.val
        return -1


    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.dic:
            self.remove(self.dic[key])
        node = Node(key, value)
        self.add(node)
        self.dic[key] = node
        if len(self.dic) > self.capacity:
            node = self.head.next
            self.remove(node)
            del self.dic[node.key]

    def remove(self, node):
        pNode = node.prev
        nNode = node.next
        pNode.next = nNode
        nNode.prev = pNode

    def add(self, node):
        pNode = self.tail.prev
        pNode.next = node
        self.tail.prev = node
        node.prev = pNode
        node.next = self.tail

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

if __name__ == '__main__':

    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.get(1))      #// 返回  1
    cache.put(3, 3)          #// 该操作会使得密钥 2 作废
    print(cache.get(2))      # // 返回 -1 (未找到)
    cache.put(4, 4)          # // 该操作会使得密钥 1 作废
    print(cache.get(1))      #// 返回 -1 (未找到)
    print(cache.get(3))      #  // 返回  3
    print(cache.get(4))      #// 返回  4

LFU缓存

LRU（Least recently used，最近最少使用）首先淘汰最近一定时期内被访问次数最少的页面。

leetcode 460. LFU缓存
链接

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

待续…

Donate comment here
------------The End------------
0%