在Java中查找两个文件中的共同名称

Question

首先，我想明确这个问题的性质与我所知道的其他问题不同。如果不是这样，请告诉我。

给出：

1. 我有一个名字列表 ~3000。 2. 有 ~2500 个文件，其中每个文件都包含一行名称（从名称列表中获取）。 3. 每个文件包含 ~3000 个名称（因此有 ~3000 行，尽管平均值为 400）。

问题：

在给定的时间内，我将提供 2 个文件。我必须创建一个在这两个文件中共同存在的名称列表。

预处理：

为了减少时间复杂度，我进行了预处理，并对所有文件中的名称进行了排序。

我的方法：

1. 对给定列表中的名称进行排序，并将它们从 0 到 2999 进行了索引。 2. 对于每个名称的每个文件：

- 计算组号（名称索引/30） - 计算组值（对于同一组中的每个名称，计算 (2^(name_index%30)) 并相加） - 使用“groupNumber blankSpace groupValue”格式创建一个具有相同名称的新文件。

结果：

现在，每个文件中最多只有 100 行名称（尽管平均值为 400）。现在，我将检查共同的组号，然后通过位操作找到共同的名称。

期望：

请问是否有更短、更好的解决方案？我可以在应用程序中进行预处理并存储新文件，以便在查找共同名称时需要最少的处理。如果我解决问题的方向有误，请告诉我。谢谢您的帮助。

注意事项：

在我的方法中，总文件大小为 258KB（因为我使用了组名和组值）��如果按每行一个名称保存，则大小为 573KB。这些文件必须存储在移动设备上。因此，我需要尽可能地减小文件大小。此外，我正在寻求数据压缩，并且对如何进行数据压缩一无所知。请您讲解一下。

- Comet

---

你的性能要求是什么？ - Colin D

对于以下的代码，有什么问题吗？

1. 按行读取一个文件，将每一行添加到 HashSet 中；
2. 再按行读取第二个文件，检查 HashSet 是否包含给定的行。如果是，就把它添加到结果中；如果不是，则继续执行。

- Petr Janeček

你有多少个独特的名称？如果你希望每个文件以100行结束（但仍然有2500个文件？），那么这将是250,000个单词=行吗？我不太理解的是：“每个文件包含约3000个名称，尽管平均值为400个”。如果每个文件包含3000个名称，那么平均值不是3000吗？ - user unknown

我考虑使用您提供的逻辑，并且是的，它非常简单明了。但问题是该应用程序是为移动设备开发的，因此内存需求应该非常低。希望我现在清楚了。 - Comet

@user_unknown并非每个文件都包含3000行。但上限是3000（即唯一名称的数量）。许多文件具有较少的名称，因此平均值为400。如果我表述不清楚，请告诉我。 - Comet

Answer 1

您尝试过以下方法吗？

1. 从list1中逐个读取名称，并将它们添加到哈希集合中。
2. 逐个从list2中读取名称，查找哈希集合中是否存在。如果它们在哈希集合中，则意味着这个名字在两个文件中都出现。

如果您想预处理以获得更快的速度，请存储每个列表中名称的数量，并将较短的列表选为list1。

- Colin D

---

我的话完全正确。不过我还是有点困惑。这个问题采用了一种超难的方法，而最简单和显而易见的答案可能也是最快的。我们是否遗漏了什么？比如不能使用内存的限制？ - Petr Janeček

可能缺少的内容：性能要求和操作者是Java/编程新手，不知道存在哪些内置结构。 - Colin D

如果是后者，那么这就是为了Comet：HashSet。 - Petr Janeček

由于该应用程序是为移动设备设计的，因此我认为内存要求应该较低。 - Comet

我猜在预处理（就像我所做的那样）之后，将其添加到哈希集中可以解决这个问题。因为经过预处理后，行数最多会减少到100行。 - Comet

Answer 2

Aha！鉴于您在编辑中提到的非常低的内存需求，您可以尝试另一种方法。虽然我仍认为您可以采用其他答案建议的解决方案。带有3000个字符串条目的HashSet不会太大。根据16个字符的 Strings快速近似计算，堆内存应该小于400 kB。尝试一下，然后再回来。整个程序只需要25行代码。

如果该解决方案占用了太多内存，则可以执行以下操作：

1. 对文件中的名称进行排序。
2. 打开两个文件。
3. 从两个文件中读取一行内容。
   1. 如果line1 < line2，则从line1读取一行，重复执行。
   2. 如果line1 > line2，则从line2读取一行，重复执行。
   3. 否则它们相同，将其添加到结果中。重复。

它几乎不会占用内存，并且是使用compareTo()方法（如果用于对名称进行排序）和switch语句的好地方。

文件的大小不会影响内存使用率。

关于数据压缩 - 有许多工具和算法可供使用，可以尝试这个（也要查看相关问题），或者这个。

- Petr Janeček

---

谢谢您的建议。看起来是更好的解决方案。我必须减小文件大小，所以实现了混合解决方案。无论如何，感谢提供链接。 - Comet

Answer 3

你正在尝试使用列表重新实现一个集合。不要这样做。使用一个名称的集合，它会自动处理插入的重复项。

你需要读取两个文件，没有绕过这个步骤的方法。

// in pseudo-java
Set<String> names1 = new HashSet<String>();
for (String name : file1.getLine().trim()) {
  names1.put(name);
}

Set<String> names2 = new HashSet<String>();
for (String name : file2.getLine().trim()) {
  names2.put(name);
}

// with this line, names1 will discard any name not in names2
names1.retainAll(names2);

System.out.println(names1);

假设您像此示例一样使用 HashSet ，您将比较字符串的哈希值，这将显着提高性能。

如果发现性能不足，则开始寻找更快的解决方案。其他任何事情都是过早优化，如果您不知道它必须运行多快，那么就是没有设定目标的优化。找到“最快”的解决方案需要枚举和耗尽每个可能的解决方案，因为您尚未检查的解决方案可能会更快。

- Edwin Buck

---

你不需要存储第二个文件中的名称，因为一个简单的 if (names1.contains(name)) 检查就可以了。但是，是的。 - Petr Janeček

@Slanec，是的，但是通过多次调用if (names1.contains(name))（对于文件2中的每个名称调用一次）仅为了销毁它们而创建了几千个JVM堆栈帧，并且在文件读取过程中强制计算字符串哈希值（在“错误”的条件下可能会导致IO停顿）。另一方面，我的示例可能会使用足够的内存来强制数据从缓存中移出。当询问更快时，最好先构建一些东西，然后说“足够快”或者“能比这更快”。在测量之前做出的任何陈述都是有风险的。 - Edwin Buck

Answer 4

我不确定我是否理解了您的要求和情况。

您有大约2,500个文件，每个文件有3000个单词（或400个？）。有许多重复的单词出现在多个文件中。

现在有人会问您，文件345和文件765有哪些共同之处。

您可以创建一个哈希映射表，其中存储每个单词以及单词出现的文件列表。

如果您获得了包含3000个单词（或400个）的文件345，您可以在哈希映射表中查找，看看文件765在列表中被提到的位置。

然而，2 * 3000并不是很多。如果我在Scala中创建2个字符串列表（它运行在JVM上）：

val g1 = (1 to 3000).map (x=> "" +  r.nextInt (10000))
val g2 = (1 to 3000).map (x=> "" +  r.nextInt (10000))

并构建交集

g1.intersect (g2)

我在一台8年前的笔记本电脑上几乎没有时间就得到了结果（678个元素）。

那么你需要回答多少请求？文件输入有多频繁更改？如果很少，那么读取这2个文件可能是关键点。

你有多少个唯一的单词？也许把它们全部保存在内存中根本不是问题。

- user unknown