如何使用STL实现LFU缓存？

 

我试图使用纯STL实现LFU（Least Frequently Used）缓存（我不想使用Boost！）。

要求是：

  • 使用Key与std::map关联访问任何元素。
  • 能够释放最低优先级的项目（使用它的UsesCount属性）。
  • 能够更新任何项目的优先级（ UsesCount ）。

    • 问题是：

  • 如果我使用std::vector作为容器的项目（ Key ， Value ， UsesCount ）， std::map作为容器的迭代器，用于关联访问的vector和std::make_heap ， std::push_heap和std::pop_heap作为优先队列实现在向量中，映射中的迭代器在堆操作后无效。
  • 如果我在前面的配置中使用std::list （或std::map ）而不是std::vector ， std::make_heap等无法编译，因为它们的迭代器不支持aritmetic。
  • 如果我想使用std::priority_queue ，那么我无法更新项目优先级。

    • 问题是：

  • 我是否明白这个问题可以如何解决？
  • 你能指点我一些符合以前需求的LFU缓存的纯C ++ / STL实现吗？

    • 感谢您的见解。

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

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

    直接回答你的问题：你不会错过某些明显的东西。 std::priority_queue并不像应该那样有用。 最好的方法是编写自己的支持更新的堆实现。 为了完全兼容STL（尤其是分配器感知）是相当棘手的，而不是一个简单的任务。 最重要的是，实现LFU缓存。

    第一步，查看Boost实现来了解这个工作。 我不知道第二个参考实现。

    为了解决迭代器失效问题，你总是可以选择间接到另一个容器中，尽管你应该尽量避免它，因为它会产生额外的成本并且会变得非常混乱。

    比保留两种数据结构更简单一些：

  • 只需保留一张地图，它将你的钥匙映射到它们的值/使用计数对。
  • 当缓存已满时：
  • 为地图元素创建一个迭代器向量（ 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为什么适合您的缓存策略，我对它的改变可能是错误的策略，或者它可能还是很好的。

    链接地址: http://www.djcxy.com/p/10951.html

    上一篇: How to implement LFU cache using STL?

    下一篇: How to handle if query parameter is null or empty in hibernate?