java - LRU 缓存如何为 trie 数据结构工作？

Question

假设我有一个总限制为 10 个节点的 trie/前缀 trie。我限制为 10 个节点来模拟超出的内存。（如果我不能将整个树加载到内存中，我总共有 10 个节点存储在磁盘上。

我现在将一个新字符串插入到树中，这将导致树超过 10 个节点的限制，所以现在是 LRU 缓存从树中驱逐最近最少访问的节点的时候了。

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

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

标签： javatreeprefixtrielru

Answer 1

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

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

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

PS：在您的帖子中，您谈到了模拟内存被执行。程序没有这样的东西。当缓存已满时，我们会填满主存。当主存已满时，操作系统通常会保留一部分硬盘驱动器来扮演主存的角色（我们称之为交换，当它发生时，计算机就像死机一样）。当交换已满时，程序崩溃。他们全部。
在程序的“头脑”中，操作系统为它提供了绝对巨大的内存（这是虚拟的，但对于程序来说它和真实的一样好），永远不会被填满。程序本身并不“意识到”内存的管理方式以及剩余的内存量，原因有很多（安全性，保证所有程序都将拥有公平的资源份额......）