1

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

我应该如何获得 10 个键，它的总计数值应该在 30 个文件中的所有前 10 个中。

任何帮助将不胜感激。

4

3 回答 3

2

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

设计指南：

  • 由于数据不是太大[32 位系统上的 100,000 * 30 整数约为 11.5 MB]，并且假设密钥不是太大1，整个数据集可能会填充到内存中。
  • 当数据在内存中时——你可以在它上面做任何更快的事情，因为磁盘 IO 比 RAM 慢得多，所以对它进行排序和多次读取预计比在内存上操作数据要慢得多。

算法 ：

  1. 创建一个直方图，它实际上是一个HashMap:key->int，它将在您阅读文件时填充。对于您正在读取的每个键，如果它已经在直方图中 - 将计数添加到直方图中的现有值，如果它不存在 - 只需将 (key,count) 对添加到直方图中。[O(n)平均运行时间]
  2. 一旦填充了直方图- 找到前 10 个很容易 - 创建一个min heap并迭代直方图，堆应该始终包含前 10 个值和匹配的键 - 当然。在这个线程中有一个解释如何做到这一点。- 对于恒定的top10，它也是O(n)如此。
  3. 完成后 - 堆包含您的解决方案，只需显示其内容。

好处：

  • 只有一个磁盘读取 - 因为磁盘比RAM 慢得多 - 这可能是瓶颈 - 所以尽量减少磁盘读取/写入应该是一个优先事项。
  • O(n)平均运行时间。

坏处：

  • 如果您的哈希函数非常差 [不太可能] - 由于哈希表，解决方案可能会衰减到二次时间复杂度。
  • 如果密钥很大并且不适合内存，则应该做更多的工作 - 请参阅脚注 (1) 如何解决它。

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

于 2012-04-20T09:46:29.957 回答
0

我会尝试以下方法：

  1. 按键排序（例如使用快速排序）每个文件（小心用于比较字符串的内容） - O(nlogn)。
  2. 将所有文件逐个合并为一个，将相等键的计数值相加（使用合并排序中的 Merge 例程 - O(n)）。你会得到一个带有唯一键的巨大散列。
  3. 按计数值对哈希进行排序 - O(nlogn)。
于 2012-04-20T08:15:01.133 回答
0
  1. 按键对每个文件进行排序。如果key无法比较...跳过这个答案~~~
  2. 现在你有多个排序的文件，以及你的比较规则。尝试多路合并。小心这一点，当您合并所有文件中的每个键时，请按照键的顺序并对计数求和。同时，创建一个堆来维护现在的前 10 个键。合并完成后，堆有前 10 个键。
于 2012-04-20T09:28:27.813 回答