146. LRU Cache

https://leetcode.com/problems/lru-cache/

solution

复合数据结构通常采用 unordered_map 或 map 辅助记录，加速寻址；配上 vector 或 list数据储存，加速连续选址或删除值

• 1.新数据放到链表的开头

• 2.数据被访问后，也需要放到链表开头

• 3.当超过LRU的容量之后，将链表尾部的数据删除

• 双向链表+哈希

# 一个类似字典item的node, 同时记录其前后的位置

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key到Node的索引, 对于linked list, tree, graph等通过局部逐渐访问, 建立一个全局的快速访问
        self.head = Node()  # dummy head and tail
        self.tail = Node()

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.remove_node(node)
        self.add_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value  # 记得更新value
            self.remove_node(node)
            self.add_to_head(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            if len(self.cache) > self.capacity:
                self.remove_tail()

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

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

    def remove_tail(self):
        del self.cache[self.tail.prev.key]
        node = self.tail.prev
        self.remove_node(node)

时间复杂度：O(1) 空间复杂度：O(1)

# ordered dict: 记录并保持了加入字典的顺序 (可能会不允许使用ordered dict)
import collections

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.ordered_dict = collections.OrderedDict()

    def get(self, key: int) -> int:
        # 1.找到目标数据 2.将目标对象移至list前端
        if key in self.ordered_dict:
            value = self.ordered_dict[key]
            self.ordered_dict.pop(key)
            self.ordered_dict[key] = value
            return value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        # 1.向list的前端加入对象 2.如果超过capacity，将list尾部的对象删除
        if key in self.ordered_dict:
            self.ordered_dict.pop(key)
        self.ordered_dict[key] = value
        if len(self.ordered_dict) > self.capacity:
            self.ordered_dict.popitem(last=False)

# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

时间复杂度：O() 空间复杂度：O()

follow up

• 多线程版本LRU

  • multiprocessing库: cpu-intensive 任务用 processPool, 如果是 io-intensive 任务用 threadPool

  • 多进程: 多核CPU上并行执行，资源和变量不共享，需要通过管道队列通信，更适合计算密集型

  • 多线程: CPU单核上互斥锁串行执行，资源共享。由于python GIL，一个进程当中如果存在多个线程，也只能在单核CPU上顺序执行，不能利用多个CPU，更适合IO密集型

• MultiCache调用

  • https://www.1point3acres.com/bbs/thread-1104232-1-1.html

460. LFU Cache

# https://zhuanlan.zhihu.com/p/126313561
# https://leetcode.com/problems/lfu-cache/solutions/3111521/o-1-time-full-explanation-hashtable-c-java-python3/

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.freq = 1
        self.prev = None
        self.next = None

class DLinkedList:
    def __init__(self):
        self.dummy = Node(None, None)
        self.dummy.next = self.dummy
        self.dummy.prev = self.dummy
        self.size = 0

    def append(self, node: Node):
        # 尾插入, 加到双向链表尾部
        node.prev = self.dummy.prev
        node.next = self.dummy
        node.prev.next = node
        self.dummy.prev = node
        self.size += 1

    def pop(self, node: Node = None):
        if self.size == 0:
            return
        # 删除头部
        if node is None:
            node = self.dummy.next
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
        return node

class LFUCache:
    def __init__(self, capacity: int):
        from collections import defaultdict
        self.key_to_node = {}
        self.freq = defaultdict(DLinkedList)
        self.min_freq = 0
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.key_to_node:
            return -1
        node = self.key_to_node[key]
        node_freq = node.freq
        self.freq[node_freq].pop(node)
        if self.min_freq == node_freq and self.freq[node_freq].size == 0:
            self.min_freq += 1
        node.freq += 1
        self.freq[node.freq].append(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0: return
        if key in self.key_to_node:
            node = self.key_to_node[key]
            node_freq = node.freq
            self.freq[node_freq].pop(node)
            if self.min_freq == node_freq and self.freq[node_freq].size == 0:
                self.min_freq += 1
            node.freq += 1
            node.val = value
            self.freq[node.freq].append(node)
        else:
            if len(self.key_to_node) == self.capacity:
                node = self.freq[self.min_freq].pop()
                self.key_to_node.pop(node.key)
            node = Node(key, value)
            self.key_to_node[key] = node
            self.freq[1].append(node)
            self.min_freq = 1

• ordered_dict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self._items = collections.defaultdict(int)  # key: frequency.
        self._freqs = collections.defaultdict(OrderedDict)  # frequency: {key: val}
        self._minFreq = 0  # Minimum used frequency for the keys in the cache.

    def _update_freq(self, key: int, value: int = None) -> int:
        """
        Update the _items and the _freqs with the input key, then return the latest value.
        """
        f = self._items[key]
        v = self._freqs[f].pop(key)  # Remove the current key.
        if value is not None:  # Update with new value if any.
            v = value

        self._freqs[f + 1][key] = v  # Add the key to the new frequency.
        self._items[key] += 1  # Update the frequency in the items.
        if self._minFreq == f and not self._freqs[f]:  # Update minimum freq.
            self._minFreq += 1

        return v

    def get(self, key: int) -> int:
        if key not in self._items:
            return -1

        return self._update_freq(key)

    def put(self, key: int, value: int) -> None:
        if not self.capacity:  # Not able to put anything.
            return

        if key in self._items:
            self._update_freq(key, value)
        else:
            if len(self._items) == self.capacity:  # Cache is full.
                # 1. Pop the least frequently used key in _freqs[minimum freq].
                # 2. Pop the same key from _items as it does not exist.
                self._items.pop(
                    self._freqs[self._minFreq].popitem(last=False)[0])

            # Add the new key.
            self._minFreq = 1
            self._items[key] = 1
            self._freqs[1][key] = value

时间复杂度：O() 空间复杂度：O()