c - 如何找到 1T 数字中出现频率最高的数字？

Question

如何找到 1T（即 10^12）个数中出现频率最高的数（int 类型）？

我的前提是：

• 我的内存限制为 4G（即 4·10^9）字节。
• 所有数字都存储在一个文件中作为输入。
• 输出只是一个数字。
• 所有数字（int 类型）都存储在一个或多个文件中
• 文件结构是二进制或行存储的。

---

编辑于：2013.04.22 17:08 感谢您的评论： 加： - 外部存储不受限制。

Answer 1

首先要注意，这个问题至少和元素区别问题一样难。

因此，解决方案应遵循相同的方法：

1. 排序（使用外部排序）并在计算每个数字的出现次数并寻找最大值时进行迭代。
2. 散列解决方案：将数字散列到适合内存的存储桶中（请注意，相同数字的所有出现都将散列到同一个存储桶），对于每个存储桶 - 找到最频繁的数字，并将其存储。然后从所有桶中遍历所有候选人并选择最好的。
   在这里，您可以对每个桶进行排序（在内存中）并找到最频繁的数字，或者您可以创建一个直方图（使用哈希图，具有不同的哈希函数）来查找桶中每个项目的频率。
   请注意，存储桶被写入磁盘，并一个接一个地加载到内存中，每次只有一小部分数据存储在 RAM 中。

另一种更具可扩展性的方法是使用map-reduce，使用简单的 map-reduce 步骤来计算每个数字的出现次数，然后找到其中的最大值：

map(number):
  emit(number,'1')
reduce(number,list):
  emit (number, size(list))

剩下的就是找到具有最高值的数字 - 这可以在线性扫描中完成。

Answer 2

如何使用文件系统存储数字计数器？

例如，如果你的数字是 uint32，你可以创建 65536 个目录，每个目录有 65536 个文件。目录名将是数字的两个高字节，文件名 - 低两个字节。当您遇到数字 X 时，您将其拆分为两部分并获取文件名，打开该文件并在其中增加计数器（或在其中写入 1，如果文件不存在）。

填充该文件结构后，您可以递归地扫描具有最大价值的树查找文件。

那将非常缓慢，但几乎不会吃掉任何内存。

Answer 3

蛮力：

• 记住 = 0;
• 重复：
  • 取第一个未标记的数字并计算它在文件 (n1) 中的出现次数。
  • 将每个出现的数字标记为已读。（用空格 fe 覆盖它）
  • 如果 (n1 > 记住) 记住 = n1;

Answer 4

使用哈希表，键是数字，值是计数。O(n) 将所有数字插入哈希表 O(Unique numbers) 以找到最频繁的数字。