Cache

Design
hash table, linked list, topic
Catalogue
  1. 1. OrderedDict
  2. 2. 146. LRU Cache
    1. 2.1. Solution1. Built-In
    2. 2.2. Solution2. Doublely Linked List + Hash map
  3. 3. 460. LFU Cache

Design + Operatin System + Data Structure

OrderedDict

An OrderedDict is a dict that remembers the order that keys were first inserted.

1
2
3
4
cache = collections.OrderedDict()
cache.popitem(last=True)
# The popitem() method for ordered dictionaries returns and removes a (key, value) pair.
# The pairs are returned in LIFO order if last is true or FIFO order if false.

146. LRU Cache

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

  1. we need to be able to add an entry to the cache and delete the oldest entry from the cache.(including when the cache is full)
  2. we need to find out quickly whether an entry is in the cache or not.
  • hash map :
  1. we need to adjust the priority efficiently of each entry in the cache.
  • double linked list or singly linked list node

Solution1. Built-In

  • python built-in datastructure OrderedDict!!! record the order when they put in the dictionary
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class LRUCache(object):

    def __init__(self, capacity):
        self.cap = capacity
        self.cache = collections.OrderedDict()

    def get(self, key):
        if key not in self.cache:
            return -1
        val = self.cache.pop(key)
        self.cache[key] = val
        return val


    def put(self, key, value):
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
        else:
            if len(self.cache) >= self.cap:
                self.cache.popitem(last=False)
            self.cache[key] = value

Solution2. Doublely Linked List + Hash map

  • Key Point
  1. DummyNode, head and tail
  2. helper function, remove and addHead
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
class Node(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cap = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def _addHead(self, node):
        nxt = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = nxt
        nxt.prev = node

    def _remove(self, node):
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

    def get(self, key):
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._addHead(node)
        self.cache[key] = node
        return node.val

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._remove(node)
            self._addHead(node)
        else:
            if len(self.cache) >= self.cap:
                lastKey = self.tail.prev.key
                self._remove(self.tail.prev)
                del self.cache[lastKey]
            node = Node(key, value)
            self.cache[key] = node
            self._addHead(node)

460. LFU Cache

TODO!!!

Share