java - LRU 缓存如何用于 trie 数据结构？

Question

假设我有一个特里树/前缀特里树，节点总数限制为 10 个。我将节点限制为 10 个以模拟超出内存的情况。 (如果我无法将整个树加载到内存中，则磁盘上总共存储了 10 个节点。

我现在向 trie 中插入一个新字符串，这将导致树超过 10 个节点的限制，因此现在 LRU 缓存需要从 trie 中逐出最近最少访问的节点。

假设树包含单词 hello、help、hi，LRU 节点是“h”。这意味着我需要从特里树中删除“h”，在这种情况下这将删除整个树。我的困惑还在于更新缓存本身以删除所有子项。在这种情况下它是如何工作的？

我假设缓存有“h”、“he”、“hel”、“help”等节点。如果我删除“h”节点，我假设我需要删除缓存中前缀为“的所有内容” H”？我的整个假设看起来效率很低。

Answer 1

在谈论缓存时要记住的一件事是，它是一种冗余数据结构，其唯一目标是加速数据获取。
因此，当从缓存中逐出一条数据时，它对使用该数据的程序没有任何影响(除了执行速度)，因为随后将从主内存中获取该数据。因此，无论如何，您的 trie 将具有完全相同的行为，无论它的哪一部分位于缓存中或不在缓存中。

这非常重要，因为它允许我们用高级语言(例如java)进行编码，而无需关心处理器实现的缓存的替换策略。如果情况并非如此，那将是一场噩梦，因为我们必须考虑处理器中实现的所有现有(和 future ？)更换策略。更不用说这些策略并不像 LRU 那么简单(有缓存集，它将缓存划分为“行”，它们的行为也与它们的物理结构密切相关)，并且一条数据将在哪里存储？其在高速缓存中的位置取决于其在主存中的地址，每次执行代码时该地址不一定相同。

简而言之，你提到的两件事(java中的trie节点和LRU缓存策略)相距太远(一个是非常非常低级的编程，另一个是高级)。这就是为什么我们很少(如果有的话)考虑他们的相互作用。
如果你用java实现Trie，你的工作就是确保它在所有情况下都能正常工作，它设计得很好，因此维护会更容易(可能)，它是可读的，以便其他程序员有一天可以使用它。最终，如果它仍然运行太慢，您可以尝试优化它(在确定瓶颈在哪里之后，以前从未如此)。
但是如果你想将你的 trie 链接到缓存命中/未命中和替换策略，你将必须阅读字节码实现的翻译(由 JVM 完成)。

PS:在您的帖子中，您谈到模拟内存被执行。对于程序来说，不存在这样的事情。当缓存满了，我们就填满主存。当主存已满时，操作系统通常会保留一部分硬盘来发挥主存的作用(我们称之为交换，当这种情况发生时，计算机就像卡住一样)。当交换空间已满时，程序就会崩溃。全部。
在程序的“大脑”中，操作系统为它提供了绝对巨大的内存(这是虚拟的，但对于程序来说它与真实的内存一样好)，并且永远不会被填满。出于很多充分的原因(安全性、保证所有程序都拥有公平的资源份额......)，程序本身并不“意识到”内存的管理方式以及剩余的内存量。 p>