如何设计最近使用的缓存？

Question

如何设计最近使用的缓存？

假设您访问过一些项目。你需要设计一个数据结构来保存 这些物品。每个项目都与最近访问的时间相关联。

每次访问一个项目时，请在数据结构中检查它。如果该项目已在缓存中，则更新其访问时间。否则，将其插入缓存中。缓存大小是固定的，如果已满，则删除最旧的项。

我的解决方案：

1. 使用地图<项目，visitTime >

2. 初始化：用f(visitTime)对地图进行降序排序。 O(nlg n)

3. 如果访问了某个项目，则使用 O(lg n) 在地图中搜索它。

4. 如果已经在地图中，则更新时间 O(1)。对地图进行排序 O(lg n).

5. 如果没有，则插入到map中，然后排序。 O(lg n)

6. 如果地图大小 >固定大小，删除最后一个元素 O(1)。

另一种解决方案：

1. 使用哈希表<项目 , 访问时间 >

2. 排序 O(n lgn)。

3. 如果访问了某个项目，则在表中搜索它的时间复杂度为 O(1)。

4. 如果已经在表中，则更新时间O(1)。对表格进行排序 O(nlgn)。

5. 如果没有，则插入表中，然后排序。 O(n lg n)

6. 如果表大小 >固定大小，删除最后一个元素 O(1)。

有更好的解决方案吗？在） ？

Answer 1

如果您使用双向链表，您将获得 O(1) 插入（搜索后）、O(1) 删除、O(n) 搜索。

假设你在前面插入新项：

如果缓存未满，就添加到前面（O(1)）。

如果需要更新一个项目，找到它（O(n)），将其从链表中删除（O(1)），然后添加到前面（O(1)）。

如果需要删除最旧的元素来插入新元素，请删除末尾元素（O(1)），然后插入到前面（O(1)）[注意：在这种情况下，您需要先搜索列表才能看到如果该项目尚未在缓存中，则 O(n)]。

链接列表也可以为您提供相同的时间，因为搜索会将您留在最后一个元素。

Answer 2

Python 的 LRU 缓存 具有 O(1) 的插入、删除和删除操作搜索。它的设计使用双向链接的条目列表（从最旧到最新排列）和哈希表来定位特定链接。

这是一个简化（但快速）的版本，由非常基本的 Python 代码组成，不到 40 行。将 Python 的解决方案翻译成 C++ 应该不难：

class LRU_Cache(object):

    def __init__(self, original_function, maxsize=1000):
        self.original_function = original_function
        self.maxsize = maxsize
        self.mapping = {}

        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        self.head = [None, None, None, None]        # oldest
        self.tail = [self.head, None, None, None]   # newest
        self.head[NEXT] = self.tail

    def __call__(self, *key):
        PREV, NEXT, KEY, VALUE = 0, 1, 2, 3
        mapping, head, tail = self.mapping, self.head, self.tail
        sentinel = object()

        link = mapping.get(key, sentinel)
        if link is sentinel:
            value = self.original_function(*key)
            if len(mapping) >= self.maxsize:
                oldest = head[NEXT]
                next_oldest = oldest[NEXT]
                head[NEXT] = next_oldest
                next_oldest[PREV] = head
                del mapping[oldest[KEY]]
            last = tail[PREV]
            link = [last, tail, key, value]
            mapping[key] = last[NEXT] = tail[PREV] = link
        else:
            link_prev, link_next, key, value = link
            link_prev[NEXT] = link_next
            link_next[PREV] = link_prev
            last = tail[PREV]
            last[NEXT] = tail[PREV] = link
            link[PREV] = last
            link[NEXT] = tail
        return value

if __name__ == '__main__':
    p = LRU_Cache(ord, maxsize=3)
    for c in 'abcdecaeaa':
        print(c, p(c))

Answer 3

您可以使用 Java 中的 java.util 来完成此操作.LinkedHashSet。它是一个哈希表，加上一个链接列表，保留项目插入的顺序。如果密钥分散效果良好，您应该获得（预期的）恒定时间的查找、插入和删除。

您可能还想查看 WeakHashMap 其中实现了一种可以对元素进行垃圾收集的自动化机制。

Answer 4

使用共享相同数据的两个集合。有一个哈希表和一个列表。使用哈希表来验证项目是否存在，并在列表中查找它（哈希映射的值为列表迭代器）。使用列表来维护项目之间的顺序。同步两个集合（从列表中删除项目时，从哈希表中删除相应的项目）。列表迭代器必须确保当您在列表中重新定位项目时它不会更改。

编辑： std::list 迭代器在元素的添加和删除过程中都有效，前提是不删除迭代器引用的元素。请参阅 Wikipedia 中容量和分配部分的最后几行。

Answer 5

您实际上不必对容器进行分类。只需将项目添加到地图或矢量中，然后线性遍历即可找到所需的项目（或最旧的项目）。

那么它将是O(n)。

Answer 6

看看 boost::multi_index。它显示的示例之一是 MRU 列表。