用C最近最少使用缓存++ [英] Least Recently Used cache using C++

问题描述

我想用C ++实现LRU缓存。我想知道什么是实现它们的最佳设计。我知道LRU应提供find（）方法，添加元素和删除元素。删除应该删除LRU元素。什么是实现这一目标的最佳的ADT 对于例如：如果我使用的地图与元素作为价值和时间计数器的关键我可以在O查询（LOGN）时，插入是O（n），删除是O（LOGN）

I am trying to implement LRU Cache using C++ . I would like to know what is the best design for implementing them. I know LRU should provide find(), add an element and remove an element. The remove should remove the LRU element. what is the best ADTs to implement this For ex: If I use a map with element as value and time counter as key I can search in O(logn) time, Inserting is O(n), deleting is O(logn).

推荐答案

与LRU缓存的一个主要问题是，很少有常量的操作，多数会改变底层重新presentation（如果仅仅是因为他们碰到的元素访问）。

One major issue with LRU caches is that there is little "const" operations, most will change the underlying representation (if only because they bump the element accessed).

这当然是非常不方便的，因为这意味着它不是一个传统的STL容器，并因此表现出的迭代器的任何想法是相当复杂：当迭代器被提领，这是一个访问，这应该修改我们的迭代就行了......噢，我的。

This is of course very inconvenient, because it means it's not a traditional STL container, and therefore any idea of exhibiting iterators is quite complicated: when the iterator is dereferenced this is an access, which should modify the list we are iterating on... oh my.

和有表演的考虑，无论是在速度和内存占用期限。

And there are the performances consideration, both in term of speed and memory consumption.

这是不幸的，但你需要一些方法来组织你的数据在队列（LRU）（并有可能以除去中间的元素），这意味着你的元素必须是相互独立的。 A 的std ::列表适合，当然，但它比你更需要。一个单向链表就足够了这里，因为你并不需要遍历列表向后（你只想要一个队列，毕竟）。

It is unfortunate, but you'll need some way to organize your data in a queue (LRU) (with the possibility to remove elements from the middle) and this means your elements will have to be independant from one another. A std::list fits, of course, but it's more than you need. A singly-linked list is sufficient here, since you don't need to iterate the list backward (you just want a queue, after all).

不过其中的一个主要缺点是参考他们可怜的地方，如果你需要更多的速度，你需要提供自己的自定义（池？）分配的节点，使他们尽可能地接近越好。这也将缓解堆碎片一些。

However one major drawback of those is their poor locality of reference, if you need more speed you'll need to provide your own custom (pool ?) allocator for the nodes, so that they are kept as close together as possible. This will also alleviate heap fragmentation somewhat.

接下来，你显然需要一个索引结构（用于缓存位）。最自然的是把对哈希映射。 的std :: tr1 :: unordered_map ，的std :: unordered_map 或的boost :: unordered_map 通常是质量好的执行，有的要提供给你。他们还分配额外的节点的哈希冲突的处理，你可能preFER其他类型的哈希地图，请维基百科的文章关于这个问题，并阅读有关的各种执行工艺的特点。

Next, you obviously need an index structure (for the cache bit). The most natural is to turn toward a hash map. std::tr1::unordered_map, std::unordered_map or boost::unordered_map are normally good quality implementation, some should be available to you. They also allocate extra nodes for hash collision handling, you might prefer other kinds of hash maps, check out Wikipedia's article on the subject and read about the characteristics of the various implementation technics.

继续，有（明显）线程支持。如果你不需要线程支持，那么它的罚款，如果你这样做然而，这是一个比较复杂：

Continuing, there is the (obvious) threading support. If you don't need thread support, then it's fine, if you do however, it's a bit more complicated:

• 正如我所说的，上有这样的结构有点常量运行，所以你并不需要区分读/写访问
• 在内部锁是好的，但你可能会发现，它并没有发挥好与您的用途。内部锁定的问题是，它不支持交易的概念，因为它放弃每一个呼叫的锁。如果您遇到这种情况，改变你的对象变成一个互斥体，并提供了一​​个的std ::的unique_ptr＆LT;锁定＆GT;锁定（）方法（在调试中，可以断言不是锁在采取各种方法的入口点）
• 有（锁定策略）再进入的问题，即在同一个线程内重新锁定的互斥体的能力，检查Boost.Thread有关各种锁和互斥可用
了解更多信息

• As I said, there is little const operation on such a structure, thus you don't really need to differentiate Read/Write accesses
• Internal locking is fine, but you might find that it doesn't play nice with your uses. The issue with internal locking is that it doesn't support the concept of "transaction" since it relinquish the lock between each call. If this is your case, transform your object into a mutex and provide a std::unique_ptr<Lock> lock() method (in debug, you can assert than the lock is taken at the entry point of each method)
• There is (in locking strategies) the issue of reentrance, ie the ability to "relock" the mutex from within the same thread, check Boost.Thread for more information about the various locks and mutexes available

最后，还有一个错误报告的问题。由于预计缓存可能无法取回你把数据，我会考虑使用一个例外，低级趣味。考虑要么指针（值* ）或 Boost.Optional （的boost ::可选＆LT;价值＆安培;＆GT; ）。我想preFER Boost.Optional，因为它的语义是明确的。

Finally, there is the issue of error reporting. Since it is expected that a cache may not be able to retrieve the data you put in, I would consider using an exception "poor taste". Consider either pointers (Value*) or Boost.Optional (boost::optional<Value&>). I would prefer Boost.Optional because its semantic is clear.

这篇关于用C最近最少使用缓存++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！