algorithm - 查找文件中 k 个最常见的单词 - 内存使用

Question

假设您有一个很大的文件，比如 1GB。该文件每行包含一个单词(总共 n 个单词)，您想要在该文件中找到 k 个最频繁出现的术语。

现在，假设您有足够的内存来存储这些单词，在减少内存使用量和 Big-O 复杂性中的恒定开销方面，什么是解决这个问题的更好方法？我相信可以使用两种基本算法:

1. 使用哈希表和最小堆来存储出现次数和前 K 个单词。这是 O(n + nlogk) ~ O(N)
2. 使用 trie 树存储单词和出现次数，然后遍历 trie 树以计算出现次数最多的单词。这是 O(n*p) ~ O(N) 其中 p 是最长单词的长度。

哪种方法更好？

此外:如果您没有足够的内存用于哈希表/特里(即 10MB 左右的有限内存)，那么最好的方法是什么？

Answer 1

关于常量哪个更有效是非常依赖。一方面，trie 为插入所有元素提供了严格的 O(N) 时间复杂度，而在最坏的情况下，哈希表可能会衰减到二次时间。
另一方面，对于cache，尝试效率不是很高。 - 每次查找都需要 O(|S|) 随机访问 内存请求，这可能会导致性能显着下降。

这两种方法都是有效的，我认为在选择一种而不是另一种时应该考虑多种因素，比如最大值 latency (如果是实时系统)、吞吐量和开发时间。

如果平均案例性能很重要，我建议生成一堆文件并运行 statistical analysis 哪种方法更好。 Wilcoxon signed test 是实际使用中的最先进的假设检验。

---

关于嵌入式系统:这两种方法仍然有效，但在这里:trie 中的每个“节点”(或一堆节点)都将在磁盘上而不是在 RAM 上。请注意，这意味着 对于 O(|S|) 随机访问磁盘搜索每个条目，这可能会很慢。

对于哈希解决方案，您有 10MB，假设他们可以将其中的 5MB 用于磁盘指针的哈希表。我们还假设你可以在这 5MB 上存储 500 个不同的磁盘地址(这里是悲观分析)，这意味着你在每次哈希查找后还剩下 5MB 来加载一个桶，如果你有 500 个桶，加载因子为 0.5，这意味着您可以存储 500 * 5MB * 0.5 ~= 1.25GB > 1GB 的数据，因此使用哈希表解决方案，因此使用哈希 - 每次查找只需要 O(1) 随机磁盘搜索以找到包含相关字符串的桶。

请注意，如果仍然不够，我们可以重新散列指针表，这与 paging table 中所做的非常相似。在虚拟内存机制中。

由此我们可以得出结论，对于嵌入式系统，哈希解决方案在大多数情况下都更好(请注意，在最坏的情况下它可能仍会遭受高延迟，这里没有 Elixir )。

---

附言， radix tree 通常比 trie 更快、更紧凑，但与哈希表相比，trie 具有相同的副作用(当然，虽然不那么重要)。