c++ - 最近最少使用 (LRU) 缓存

Question

我知道我可以在 STL 中使用各种容器类，但这样做有点矫枉过正，而且代价高昂。

我们有超过 100 万的在线用户，每个用户我们需要维护 8 个不相关的 32 位数据项。目标是

1. 查找列表中是否存在一个项目，
2. 如果没有，插入。如果已满，则删除最旧的条目。

蛮力方法是维护最后一个写入指针并迭代(因为只有 8 个项目)，但我正在寻找输入以更好地分析和实现。

期待在设计模式和算法方面的一些有趣的建议。

Answer 1

Don Knuth 在The Art of Computer Proramming 中给出了几个有趣且非常有效的近似值。

1. 自组织列表I:当你找到一个条目时，将它移到列表的头部；从末尾删除。

2. 自组织列表 II:当您找到一个条目时，将其向上移动一个位置；从末尾删除。

   [以上都在卷。 3 §6.1(A).]

3. 另一种方案涉及循环维护列表，每个条目有 1 个额外位，当您找到该条目时设置该位，并在您跳过它以查找其他内容时清除该位。您总是从上次停止的地方开始搜索，如果您没有找到该条目，则将其替换为下一个清晰的位，即它自从列表的整个行程以来就没有被使用过。

   [卷。 1 §2.5(G).]