10

我正在尝试使用纯 STL 实现 LFU（最不常用）缓存（我不想使用 Boost！）。

要求是：

  • Key使用like with对任何元素进行关联访问std::map。
  • 能够释放最低优先级的项目（使用其UsesCount属性）。
  • 能够更新UsesCount任何项目的优先级 ( )。

问题是：

  • 如果我std::vector用作项目的容器 ( Key, Value, UsesCount)，std::map用作向量的迭代器容器以进行关联访问std::make_heap，std::push_heap并且std::pop_heap用作向量内的优先级队列实现，则映射中的迭代器在堆操作后无效。
  • 如果我在以前的配置中使用std::list(or std::map) 而不是等，则无法编译，因为它们的迭代器不支持算法。std::vectorstd::make_heap
  • 如果我想使用std::priority_queue，我无法更新项目优先级。

问题是：

  • 我是否遗漏了一些明显的问题如何解决？
  • 您能否以一些满足先前要求的 LFU 缓存的纯 C++/STL 实现为例？

感谢您的见解。

4

2 回答 2

3

您使用函数和向量的 make 实现*_heap似乎很合适。虽然它会导致更新缓慢。对于使用向量作为底层数据结构的每个容器，您遇到的有关迭代器失效的问题是正常的。这也是boost::heap::priority_queue采用的方法，但由于上述原因，它不提供可变接口。其他boost::heap 数据结构提供了更新堆的能力。

看起来有点奇怪：即使您能够使用std::priority_queue，您仍然会面临迭代器失效问题。

直接回答您的问题：您并没有遗漏一些明显的东西。std::priority_queue没有应有的用处。最好的方法是编写您自己的支持更新的堆实现。使其完全兼容 STL（尤其是分配器感知）相当棘手，而且不是一项简单的任务。最重要的是，实现 LFU 缓存。

第一步，查看 Boost 实现以了解工作量。我不知道第二个的任何参考实现。

要解决迭代器失效问题，您始终可以选择间接进入另一个容器，尽管您应该尽量避免它，因为它会产生额外的成本并且会变得非常混乱。

于 2012-07-10T08:51:59.323 回答
1

比保留两个数据结构更简单的方法：

  • 只需保留一张地图，它将您的密钥映射到它们的值/使用计数对。
  • 当缓存已满时：
    • 创建映射元素的迭代器向量 ( O(n))
    • 用于std::nth_element找出最差的 10% ( O(n))
    • 将它们全部从地图中删除 ( O(n log n))

因此，向缓存中添加新元素是常见情况O(log n)、最坏情况O(n log n)和已摊销的情况O(log n)。

在 LFU 缓存中删除最差的 10% 可能有点过激，因为新条目必须进入前 90%，否则它们会被删除。再说一次，如果您只删除一个元素，那么新条目仍然需要在下一个新条目之前从底部下降，否则它们会被剪切，并且他们这样做的时间更少。因此，取决于为什么 LFU 是适合您的缓存策略，我对它的更改可能是错误的策略，或者它可能仍然没问题。

于 2012-07-10T09:33:55.607 回答