c - 避免 LRU 缓存中的 "mass evictions"

Question

我已经实现了 LRU 缓存。插入新项目的过程如下所示:

1. 检查 haystack 中是否有足够的空间。如果是，请跳至 4。
2. 删除最近最少使用的项目。
3. 检查是否有足够的空间。如果没有，重复 2。
4. 在可用空间中插入项目。

元素在大海捞针中有效地随机排序。

当需要插入的项目比之前的项目大时，就会出现问题。它会导致“大规模驱逐”，在这种情况下，它会不断驱逐，直到驱逐了足够多的项目，以至于碰巧驱逐了几个连续的项目。

这种“大规模驱逐”通常涉及驱逐数以万计的元素。

可以做些什么来避免或减轻这种“大规模驱逐”？

Answer 1

我会考虑为每个缓存条目赋予与其大小和年龄成正比的权重。

(例如，真正古老的大件元素重量很大。尺寸非常小的非常古老的元素几乎没有那么重)

然后根据“权重”驱逐事物。这将有利于驱逐大型和中等陈旧的项目，而不是驱逐一万个较旧的小型项目。