1

我正在阅读有关算法问题的内容，其中一个如下：

有一个包含数百万行数据的文件，有 2 行是相同的。这些行太长了，可能不适合记忆。找到 2 条相同的线。

建议的解决方案是分段读取行并为每行创建散列。
例如，您通过构建第 1 行的第 1 部分的哈希（可以在内存中读取）然后构建第 1 行的第 2 部分的哈希到第 1 行的第 N 部分来构建第 1 行的哈希。
将哈希存储在文件或哈希表​​。对于任何相同的哈希值，比较行。如果线条相同，我们解决了它。

尽管我从高层次上理解了这个解决方案，但我不知道如何实现它。我们如何将哈希与文件中的特定行相关联？这是语言实现的细节吗？
例如，在 Java 中我们将如何解决这个问题？

4

3 回答 3

2

真正的答案是购买更多内存。您可以在 Java 2 GB 中拥有的最长字符串，并且现在可以安装在机器中。您可以以不到 200 美元的价格购买 32 GB。

但要解决问题，我建议你

  • 找到每一行的偏移量。
  • 找到相同长度的线（使用偏移量的差异）
  • 计算具有相同长度的行的 64 位或更长的哈希值。
  • 对于具有相同哈希的行，进行逐字节比较。

注意：如果您没有足够的内存来缓存整个文件，这将需要很长时间。如果您有一台 32 GB 的机器并且它有一个 64 GB 的文件，那么每次传递大约需要 20 分钟，并且这有多个传递。

1）哪个API可以找到偏移量？

您计算已读取的字节数，这就是偏移量。

2）真正的答案是购买更多的内存项目经理不同意这个对于真实的产品。你有不一样的经历吗？

我向他们指出，如果他们认为这是对资源的良好利用，我可以花一天的时间花费他们 > 1000 美元（即使这不是我得到的报酬），从而节省 100 美元的可重用内存。我让他们决定；）

我 8 岁的儿子在他制造的 PC 中有 8 GB，因为内存花了我 24 英镑。然而，您是对的，有些项目经理认为 8 GB 对于专业人士来说太多了，而他们每小时要花费这么多钱！？我在 PC 中有 16 GB，我不用来运行任何严重的东西，因为我在 256 GB 的机器上工作。这些天你可以购买 2 TB 的机器，这对于大多数应用程序来说都是多余的。;)

于 2013-01-14T18:54:26.457 回答
0

虽然我同意解决方案是利用现代技术，并利用如今的廉价内存，但问题在于锻炼大脑并了解如何在给定的限制条件下解决问题。

您谈到的散列相当简单。java 解决方案可以利用引擎盖下的一些东西，这可能会掩盖实际发生的事情，所以我将首先解释解决方案，然后再解释 java 实现。

通用解决方案：

Hashing，如 SHA1、MD5 等，通过压缩输入生成一个整数。假设您只能在每行中存储前 MB 的字符。

  • 您将遍历每一行，获取前 MB 的字符，然后将其传递给散列算法（例如 MD5）。
  • 然后将哈希映射为键，将行号列表/数组映射为值。
  • 在第一次通过后，任何匹配前 MB 字符的行都将以相同的散列结束，因此在映射中的相同列表中。
  • 为了准备第二遍，您搜索地图并剔除任何仅包含一个行号的列表。
  • 然后，您通过从映射中的剩余条目中编译行号来创建行号列表，这些行将是第二遍中检查的唯一行。
  • 第二遍，您从行列表中的每一行中提取第二 MB 字符，将它们散列并以与第一遍相同的方式将它们放入地图中。
  • 遍历映射中的条目，剔除只有一个行号的哈希条目。
  • 重复第二步，但增加字符块 (MB) 以与通行号一致。
  • 当你到达一个只有一个带有多个行号的散列并且该散列只有两个元素的通道时，这些行是相同的两个。

这本质上是一个树搜索。

Java 方法：Java 有一个名为 HashMap 的类，它会自动对键进行哈希处理。通过使用

HashMap<String,ArrayList<Integer>>

对于您的主地图，您只需每次调用

  • map.get(mbBlock).add(lineNumber); 当然，您应该检查这是否是第一次使用此键，以免出现空指针异常。
  • 每次通过后，剔除仅包含一行的条目。
  • 重复剩余的行，直到你只剩下两个行号
于 2013-01-14T19:32:11.167 回答
0

  1. 获取每行的前 k 个字符，其中 k 是可配置的。做你的散列以找到可能具有相同行的几组行。

  2. 根据第一步的结果，您极大地缩小了搜索范围，在每个较小的组上运行您的算法以获取接下来的 k 个字符。

  3. 如果不是在最坏的情况下，搜索范围在每一轮之后都会显着缩小。

算法的诀窍是把大问题分解成小问题，充分利用前面步骤的结果。

于 2013-01-18T16:55:08.250 回答