c++ - 如何设计一个最近使用的缓存？

Question

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

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

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

我的解决方案：

使用地图<item, visitTime>
初始化：使用 f(visitTime) 以降序对地图进行排序。O(nlg)
如果访问了一个项目，则使用 O(lg n) 在地图中搜索它。
如果它已经在地图中，则更新时间 O(1)。对地图 O(lg n) 进行排序。
如果没有，将其插入地图然后排序。O(lg n)
如果地图大小 > 固定大小，则删除最后一个元素 O(1)。

另一种解决方案：

使用 hashtable < item , visitTime >
对它进行排序 O(n lgn)。
如果访问了一个项目，则使用 O(1) 在表中搜索它。
如果它已经在 table 中，则更新时间 O(1)。对表 O(n lg n) 进行排序。
如果没有，将其插入表中，然后排序。O(n lg n)
如果表大小 > 固定大小，则删除最后一个元素 O(1)。

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

score 4 · Accepted Answer

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

假设您在前面插入新项目：

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

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

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

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

score 3 · Accepted Answer

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

这是 40 行以下非常基本的 Python 的简化（但快速）版本。将 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))

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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

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

score 0 · Accepted Answer

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

然后就会了O(n)。

score 0 · Accepted Answer

0

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

于 2011-11-29T21:10:02.767 回答

c++ - 如何设计一个最近使用的缓存？

6 回答 6

Related

Reference