4

首先，我想明确指出，这个问题的性质与据我所知已经发布的其他问题不同。如果不是这样，请告诉我。

给定

  1. 我有一个名字列表~3000。
  2. 有约 2500 个文件，其中包含一行中的名称（取自名称列表）
  3. 每个文件包含约 3000 个名称（因此约 3000 行，尽管 avg 为 400）

问题

在给定时间，我将获得 2 个文件。我必须创建两个文件中通用的名称列表。

预处理

为了降低时间复杂度，我已经完成了预处理并对所有文件中的名称进行了排序。

我的方法

  1. 对给定列表中的名称进行排序，并将它们从 0 到 2999 编入索引
  2. 在每个文件中为每个名称
  • 计算组号（name_index / 30）
  • 计算组值（对于同一组中的每个名称计算 (2^(name_index%30)) 并添加）
  • 以“groupNumber blankSpace groupValue”格式创建一个具有相同名称的新文件

结果

现在我将在每个文件中最多包含 100 行，而不是在每个文件中包含 ~3000（虽然平均为 400）名称。现在我必须检查公共组号，然后通过位操作，我可以找出常用名称。

期待

任何人都可以建议一个更短更好的问题解决方案。我可以在我的应用程序中进行预处理和存储新文件，以便在查找常用名称时需要最少的处理。

如果我在错误的方向上解决问题，请告诉我。提前致谢。

积分

在我的方法中，总文件的大小为 258KB（因为我使用了组名和组值），如果它在每行中按名称保存，它的大小为 573KB。这些文件必须存储在移动设备上。所以我需要尽可能减小尺寸。我也期待数据压缩，但我不知道如何做到这一点。请注意解释。

4

4 回答 4

4

您是否尝试过以下操作？

  1. 从 list1 中一次读取名称 1，将它们添加到哈希集中。
  2. 一次从列表 2 中读取一个名称，在从列表 1 创建的哈希集中查找它们。如果它们在哈希集中，则意味着名称对两个文件都是通用的。

如果要进行预处理以获得额外的速度，请将名称的数量存储在每个列表中，然后选择较短的列表作为 list1。

于 2012-05-09T20:37:12.050 回答
2

啊哈！鉴于您在编辑中声明的内存要求非常低，您还可以做另一件事。

尽管我仍然认为您可以寻求其他答案建议的解决方案。HashSet具有 3000个条目的 AString不会变得太大。我对 16 字符的快速近似Strings表明堆内存低于 400 kB。试试看，然后回去。这就像整个程序的 25 行代码。

如果解决方案占用了太多内存，那么您可以这样做：

  1. 对文件中的名称进行排序。拥有这总是一件好事。
  2. 打开这两个文件。
  3. 从两个文件中读取一行。
    1. 如果line1 < line2，从 中读取一行line1，重复。
    2. 如果line1 > line2，从 中读取一行line2，重复。
    3. 否则它们是相同的，添加到结果中。重复。

它几乎不吃任何记忆，我认为这是一个使用compareTo()方法（如果你用它来对名称进行排序）和switch语句的好地方。

文件的大小根本不影响内存使用。

关于数据压缩 - 您可以使用很多工具和算法，试试这个（也看看相关问题），或者这个这个。

于 2012-05-10T09:10:55.137 回答
0

您正在尝试使用列表重新实现 Set。不要那样做。使用一组名称，它将自动处理插入的重复。

您需要阅读这两个文件，没有办法这样做。

// 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像本示例那样使用，您将比较字符串的哈希值，这将显着提高性能。

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

于 2012-05-09T21:00:20.327 回答
0

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

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

现在有人会问你，file-345 和 file-765 有哪些共同点。

您可以创建一个 Hashmap，在其中存储每个单词，以及一个文件列表，单词出现在其中。

如果你得到文件 345，它有 3000 个字（400？），你在 hashmap 中查找它，看看列表中提到文件 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 个文件可能是关键点。

你有多少独特的词？也许将它们全部保存在内存中完全没有问题。

于 2012-05-09T21:21:02.513 回答