假设你有一个大文件，比如 1GB。该文件的每一行都包含一个单词（总共 n 个单词），并且您要查找文件中最常用的 k 个术语。
现在，假设您有足够的内存来存储这些单词，那么在减少内存使用和 Big-O 复杂性中的持续开销方面，解决这个问题的更好方法是什么？我相信可以使用两种基本算法：
哪种方法更好？
另外：如果您没有足够的内存用于哈希表/trie（即 10MB 左右的有限内存），那么最好的方法是什么？
关于常数哪个更有效是非常依赖的。一方面，trieO(N)为插入所有元素提供了严格的时间复杂度，而哈希表在最坏的情况下可能会衰减到二次时间。
另一方面，在缓存方面尝试效率不是很高——每次查找都需要O(|S|) 随机访问内存请求，这可能会导致性能显着下降。
这两种方法都是有效的，我认为在选择其中一种时应该考虑多种因素，例如最大延迟（如果是实时系统）、吞吐量和开发时间。
如果平均案例性能很重要，我建议生成一堆文件并运行统计分析哪种方法更好。Wilcoxon签名检验是实际使用的最先进的假设检验。
关于嵌入式系统：这两种方法仍然有效，但在这里：trie 中的每个“节点”（或一堆节点）都将在磁盘上而不是在 RAM 上。请注意，这意味着对于 trie O(|S|)随机访问磁盘查找每个条目，这可能会很慢。
对于散列解决方案，您有 10MB，假设他们可以将其中的 5MB 用于磁盘指针的散列表。我们还假设你可以在这 5MB 上存储 500 个不同的磁盘地址（这里悲观分析），这意味着在每次哈希查找后你还有 5MB 可以加载一个桶，如果你有 500 个桶，加载因子为 0.5，这意味着您可以存储 500 * 5MB * 0.5 ~= 1.25GB > 1GB 的数据，因此使用散列表解决方案，因此使用散列 - 每次查找只需要O(1) 随机磁盘查找即可找到包含相关字符串的存储桶。
请注意，如果仍然不够，我们可以重新散列指针表，非常类似于在虚拟内存机制中的分页表中所做的。
由此我们可以得出结论，对于嵌入式系统，散列解决方案在大多数情况下更好（请注意，在最坏的情况下它可能仍会遭受高延迟，这里没有灵丹妙药）。
PS，基数树通常比 trie 更快，更紧凑，但与哈希表相比，它具有 trie 的相同副作用（当然，虽然不那么重要）。
对于有限的内存选项，您可以先快速对列表进行排序，然后简单地填充一个包含 k 个项目的哈希表。然后，您将需要一个计数器来知道您正在检查的当前单词中有多少项目 - 如果它更高，那么您将哈希表中的最低项目替换为当前项目。
这可能对初始列表有效，但比仅扫描完整列表并使用计数填充哈希表要慢。
你开车去存储中间结果吗？如果真实：
你可能有一些元结构。和一组哈希表。您读取了一部分数据（当您的哈希大小 < 3 mb）并填充哈希表。当 size > 3mb 你保存在磁盘上。如果您限制为 10 mb，则哈希表的大小为 3 mb（例如）。
meta 描述你的哈希表。在元中，您可以存储此哈希中唯一单词的数量和所有单词的数量以及一个世界的最大数量！！！一世
在这之后。您可以从磁盘加载哈希表并合并。
例如，您可以按唯一单词的升序或哈希中一个世界的最大计数加载哈希表。在这一步中，您可能会使用一些启发式方法。