问题标签 [lru]

（首先，我的英语不是很好，拜托）

众所周知，memcached 提供延迟过期，并“替换”其平板中的 LRU 数据，但我不太清楚它是如何做到的。比如一个slab已经满了，但是这个slab里面的一些数据已经过期了，那么在slab中添加数据会发生什么？

1. memcached 是否找到一些过期数据并用添加的数据替换它们，或者
2. 它是否替换了 LRU 数据，或者
3. 它还有其他作用吗？

据我所知，延迟过期是这样的，memcached 不会主动从每个slab 中删除过期数据，而是仅在引用过期条目的键时删除过期条目。这很浪费资源，不是吗？

我需要实现一个非常简单的 LRU 缓存来存储内存地址。

• 这些地址的数量是固定的（在运行时）。
• 我只对最近使用的地址感兴趣（我不关心其他元素的顺序）。
• 每个地址都有一个对应的索引号（简单整数），它不是唯一的并且可以更改。

实现需要以尽可能少的开销运行。除了每个地址之外，还有一个相关的信息结构（包含索引）。

我目前的方法是使用 astd::list来存储地址/信息对，而 aboost::unordered_multimap是索引和列表的相关迭代器之间的映射。

以下示例与我的生产代码无关。请注意，这只是为了更好地理解。

我的数据由以下三个部分组成：

• a_path
• a_key
• a_value =f(a_path, a_key)

a_value计算起来很昂贵，所以我想不经常计算它。在一个理想的世界里，只有当它会发生变化时才会这样。所以，我对这个缓存的要求如下：

• 具有可配置最大大小的 LRU 缓存
• 键控(a_path, a_key)
• 能够根据年龄使条目过期（例如，每隔一小时左右重新计算一次）
• 能够根据以下条件使条目过期expiry_func(a_path, a_key)

我的谷歌搜索在这里失败了；即使在搜索“elisp LRU 缓存”时，我也会发现很多 Java 站点。

当出现页面错误或缓存未命中时，我们可以使用最近最少使用 (LRU)、先进先出 (FIFO) 或随机替换算法。我想知道，哪一个提供了最好的性能，也就是未来可能出现的缓存未命中/页面错误最少？

架构：Coldfire 处理器

新的 Android 类LruCache线程安全吗？java文档说：

这个类是线程安全的。通过在缓存上同步来原子地执行多个缓存操作：

他们的意思是说不是线程安全的吗？如果类是线程安全的，为什么还要同步呢？

谢谢！

Perl 中是否有一些数据结构，例如 java 中的 LinkedHashMap？

或者 Perl 中的 LRU 数据结构

更新：@TLP 基本上我想要 Hashtable 数据结构，但我也可以保持键的顺序，在处理列表中的键后删除键。

更新：@ccheneson Tie::IxHash 似乎不是我想要的，我想弹出一个最旧的键，但是 tie::ixHash 弹出最新的键，我如何在 Tie::IxHash 中获得最旧的键值对？我想要一个队列结构（以及哈希结构，我想以最简单的方式找到键），新的键、值对不断出现，我保留处理最旧的键并删除最旧的键。

更新：@ FMc Tie::IxHash 是我需要的，Tie::IxHash->Shift() 执行队列弹出 Tie::IxHash->Push() 执行队列推送，它是哈希结构，易于查找键。

谢谢大家。

如何设计一个最近使用的缓存？

假设您访问了一些项目。您需要设计一个数据结构来保存这些项目。每个项目都与最近访问时间相关联。

每次访问一个项目时，都要在数据结构中检查它。如果该项目已在缓存中，则更新其访问时间。否则，将其插入缓存。缓存大小是固定的，如果已满，则删除最旧的项。

我的解决方案：

1. 使用地图<item, visitTime>

2. 初始化：使用 f(visitTime) 以降序对地图进行排序。O(nlg)

3. 如果访问了一个项目，则使用 O(lg n) 在地图中搜索它。

4. 如果它已经在地图中，则更新时间 O(1)。对地图 O(lg n) 进行排序。

5. 如果没有，将其插入地图然后排序。O(lg n)

6. 如果地图大小 > 固定大小，则删除最后一个元素 O(1)。

另一种解决方案：

1. 使用 hashtable < item , visitTime >

2. 对它进行排序 O(n lgn)。

3. 如果访问了一个项目，则使用 O(1) 在表中搜索它。

4. 如果它已经在 table 中，则更新时间 O(1)。对表 O(n lg n) 进行排序。

5. 如果没有，将其插入表中，然后排序。O(n lg n)

6. 如果表大小 > 固定大小，则删除最后一个元素 O(1)。

有更好的解决方案吗？在） ？

有人知道基于 Redis LRU 的驱逐/删除的内部结构吗？

Redis 如何确保首先删除旧的（较少使用的）密钥（如果我们没有易失性密钥并且我们没有设置 TTL 过期）？

我确定 Redis 有一个配置参数“maxmemory-samples”，它控制用于删除键的样本大小 - 因此，如果您将样本大小设置为 10，那么它会采样 10 个键并从中删除最旧的键。

我不知道它是否完全随机地对这些密钥进行采样，或者它是否有某种机制允许它自动从相当于“较旧/较少使用的一代”中进行采样？

我正在使用对内存使用大小有限制的 lru 缓存。lru 缓存包括两种数据结构：hashmap 和链表。哈希映射保存缓存对象，链表保存缓存对象访问顺序的记录。为了确定 java 对象的内存使用情况，我使用了一个开源工具——Classmexer 代理，它是一个简单的 Java 检测代理，位于http://www.javamex.com/classmexer/。

我在http://sizeof.sourceforge.net/尝试了另一个名为 SizeOf 的工具。

问题是性能非常昂贵。测量对象大小的一项操作的时间成本约为 1.3 秒，非常缓慢。这可以使缓存的好处为零。

是否有任何其他解决方案来测量 Java 对象的内存大小？

谢谢。

我正在考虑在 Android 应用程序中实现第一层缓存。我正在考虑使用 SoftReferences 来确保避免 OOM 异常，但由于有很多关于 Android 如何“过早”释放这些异常的文章，我决定研究 android.util.LruCache 缓存。

问题：如何为实际设备正确调整尺寸？LRU 缓存是真正的解决方案而不是软引用，这听起来非常好，但如果你真的很想避免 OOM 异常，那么使用任意数量的兆字节硬引用会感觉非常不安全。如果你问我，那是不安全的。无论如何，这似乎是唯一的选择。我正在研究 getMemoryClass 以找出实际设备上应用程序的堆大小（+在调整缓存大小之前检查可用堆大小）。基线是 16 Megs，这听起来不错，但我见过设备（例如过去的 G1）抛出 OOM 异常，堆大小约为 5 MB（根据 Eclipse MAT）。我知道 G1 已经很老了，但关键是我的经验与文档中提到的 16 Megs 基线并不相符。因此我' 我完全不确定如果我需要我能合理获得的最大容量，我应该如何扩展 LRU 缓存。（对 8 Megs 会很满意，在低规格设备上会使用小至 1 Megs）

感谢您的任何提示。

编辑：我指的Android LRU缓存类：http: //developer.android.com/reference/android/util/LruCache.html