10

我正在尝试使用 C++ 实现 LRU 缓存。我想知道实现它们的最佳设计是什么。我知道 LRU 应该提供 find()、添加元素和删除元素。删除应该删除 LRU 元素。什么是最好的 ADT 来实现这个例如：如果我使用一个元素作为值和时间计数器作为键的映射，我可以在 O(logn) 时间内搜索，插入是 O(n)，删除是 O(logn)。

4

7 回答 7

15

LRU 缓存的一个主要问题是几乎没有“const”操作，大多数会更改底层表示（如果只是因为它们会影响访问的元素）。

这当然很不方便，因为这意味着它不是传统的 STL 容器，因此任何展示迭代器的想法都非常复杂：当迭代器被取消引用时，这是一个访问，它应该修改我们正在迭代的列表......天啊。

并且在速度和内存消耗方面都有性能考虑。

不幸的是，您需要某种方式将数据组织到队列 (LRU) 中（可以从中间删除元素），这意味着您的元素必须彼此独立。Astd::list适合，当然，但它比你需要的更多。单链表在这里就足够了，因为您不需要向后迭代列表（毕竟您只需要一个队列）。

然而，其中一个主要缺点是它们的参考局部性差，如果您需要更快的速度，则需要为节点提供自己的自定义（池？）分配器，以便它们尽可能靠近。这也将在一定程度上缓解堆碎片。

接下来，您显然需要一个索引结构（用于缓存位）。最自然的是转向哈希图。std::tr1::unordered_map，std::unordered_map或者boost::unordered_map通常是高质量的实现，你应该可以使用一些。他们还为哈希冲突处理分配了额外的节点，您可能更喜欢其他类型的哈希映射，请查看Wikipedia关于该主题的文章并阅读各种实现技术的特征。

继续，有（明显的）线程支持。如果您不需要线程支持，那很好，但是如果您这样做，那就有点复杂了：

  • 正如我所说，const这种结构几乎没有操作，因此您实际上不需要区分读/写访问
  • 内部锁定很好，但您可能会发现它不适合您的使用。内部锁定的问题在于它不支持“事务”的概念，因为它在每次调用之间放弃了锁定。如果是这种情况，请将您的对象转换为互斥体并提供一个std::unique_ptr<Lock> lock()方法（在调试中，您可以断言比在每个方法的入口点获取锁）
  • 存在（在锁定策略中）重入问题，即从同一线程中“重新锁定”互斥锁的能力，检查 Boost.Thread 以获取有关可用的各种锁和互斥锁的更多信息

最后，还有错误报告的问题。由于预计缓存可能无法检索您放入的数据，因此我会考虑使用“不良品味”异常。考虑指针 ( Value*) 或Boost.Optional ( boost::optional<Value&>)。我更喜欢 Boost.Optional 因为它的语义很清楚。

于 2010-09-04T16:02:24.760 回答
7

实现 LRU 的最佳方式是使用 std::list 和 stdext::hash_map 的组合（只想使用 std，然后使用 std::map）。

  • 将数据存储在列表中，以便最后使用最近最少的数据，并使用映射指向列表项。
  • 对于“get”，使用地图获取列表地址并检索数据并将当前节点移动到第一个节点
    （因为现在使用它）并更新地图。
  • 对于“插入”，从列表中删除最后一个元素并将新数据添加到前面并更新地图。

这是您可以获得的最快速度，如果您使用的是 hash_map，您几乎应该在 O(1) 中完成所有操作。如果使用 std::map 它应该在所有情况下都需要 O(logn) 。

这里有一个很好的实现

于 2010-09-04T00:22:47.190 回答
5

本文描述了几个 C++ LRU 缓存实现（一个使用 STL，一个使用boost::bimap.

于 2010-12-15T13:22:45.113 回答
2

当您说优先级时，我认为“堆”自然会导致increase-key和delete-min。

于 2010-09-03T21:47:57.883 回答
2

如果可以避免的话，我根本不会让外部世界看到缓存。我只是有一个集合（无论什么）并以不可见的方式处理缓存，根据需要添加和删除项目，但外部接口将完全是底层集合的接口。

就实现而言，堆可能是最明显的。它的复杂性与地图大致相似，但不是从链接节点构建树，而是将项目排列在数组中，并且“链接”是基于数组索引的隐式。这增加了缓存的存储密度并改善了“真实”（物理）处理器缓存中的局部性。

于 2010-09-03T21:52:12.137 回答
0

我建议堆，也许是斐波那契堆

于 2010-09-03T21:47:51.427 回答
0

我会使用 C++ 中的普通堆。

使用#include 中的std::make_heap（标准保证为O(n)）、std::pop_heap 和std::push_heap，实现它绝对是小菜一碟。你只需要担心增加键。

于 2010-09-03T22:06:19.793 回答