algorithm - 像key->value_count这样形式化的10个文件的海量数据如何获取Top 10？

Question

有30个文件，任何一个文件包含大约100,000个数据项，数据项是这样的: key->count，例如abcdefg->100，表示键'abcdefg'的计数值为100，该键可以只在一个文件中出现一次，但也可以在其他文件中出现。

如何获取这10个key，它的总计数值应该在30个文件的所有前10中。

如有任何帮助，我们将不胜感激。

Answer 1

我假设您想要总计数最大的 10 个键 [根据您的第一条评论，这似乎是正确的]

设计指南:

• 由于数据不是太大 [32 位上的 100,000 * 30 个整数 系统大约 11.5 MB]，并假设 key 不是太多 large¹，整个数据集可能会填充到 内存。
• 当数据在内存中时 - 您可以在其上更快地执行任何操作，因为磁盘 IO 比 RAM 慢得多，因此对其进行排序和多次读取预计会慢得多操纵内存中的数据。

算法:

1. 创建一个直方图，它实际上是一个 HashMap:key->int，它将是 在您阅读文件时填充。对于您正在阅读的每个键，如果它已经在直方图中 - 将计数添加到直方图中的现有值，如果它不存在 - 只需将 (key,count) 对添加到直方图中。 [O(n) 平均运行时间]
2. 一旦histogram人口众多 - 找到前 10 名很容易 - 创建一个 min heap ，并迭代直方图，堆应该总是 包含前 10 个值和匹配的键 - 当然。 this thread 中有如何操作的说明。 . - 对于常量 top10，它也是 O(n)。
3. 完成后 - 堆包含您的解决方案，只需显示其内容即可。

优点:

• 只读取一个磁盘 - 因为磁盘比 RAM 慢很多 - 这可能是瓶颈 - 所以最小化磁盘 读/写应该是一个优先事项。
• O(n) 平均运行时间。

缺点:

• 如果您的哈希函数非常差 [不太可能] - 由于哈希表的原因，解决方案可能会衰减为二次时间复杂度。
• 如果 key 很大且无法放入内存，则需要做更多工作 - 请参阅脚注 (1) 如何解决。

---

1:如果假设不成立，可以通过散列 key 并仅存储 key 来部分解决。一旦发生哈希冲突，检查是否相等 - 在磁盘本身中。会增加读取次数，但是碰撞次数应该比较低，hash函数要好。此外，您应该将它们的散列冲突的键加载到内存中[同样，以避免多次磁盘读取]，并且只有它们，它会比元素总数小得多。