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

Question

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

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

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

我的解决方案：

1. 使用地图< item，visitTime >
2. 索引:使用f(visitTime)对地图进行降序排序。O(nlg n)
3. 如果访问了一个项目，请使用O(lg n)在地图中搜索它。
4. 如果它已经在地图中，更新时间O(1)。对地图O(lg n)进行排序。
5. 如果没有，请将其插入地图，然后排序。O(lg n)
6. 如果映射大小>固定大小，则删除最后一个元素O(1)。

另一个解决方案：

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

有没有更好的解决办法？不(N)？

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)插入、删除和搜索。它的设计使用了一个双链接的条目列表(从最老到最新)和一个哈希表来定位特定的链接。

下面是一个简化(但快速)的版本，在下面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))

Answer 3

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

编辑:std：：列表迭代器在元素的添加和删除过程中都是有效的，前提是元素迭代器所引用的元素没有被删除。请参阅维基百科中容量和分配一节中的最后一行。