2

我有一个 2GB 的大文本文件，它有 5 列由制表符分隔。仅当 5 列中有 4 列匹配时，才会将行称为重复行。

现在，我正在做 dduping，首先将每个列加载到单独的 List 中，然后遍历列表，删除遇到的重复行并聚合。

问题：处理一个文件需要 20 多个小时。 我有 25 个这样的文件要处理。

任何人都可以分享他们的经验，他们将如何进行这种重复？

这个 dduping 将是一个丢弃的代码。所以，我一直在寻找一些快速/肮脏的解决方案，以尽快完成工作。

这是我的伪代码（大致）

Iterate over the rows
  i=current_row_no.    
    Iterate over the row no. i+1 to last_row
                    if(col1 matches  //find duplicate
                        && col2 matches
                        && col3 matches  
                        && col4 matches)
                        { 
                           col5List.set(i,get col5); //aggregate 
                        }

重复的例子

A 和 B 将重复 A=(1,1,1,1,1), B=(1,1,1,1,2), C=(2,1,1,1,1) 并且输出将be A=(1,1,1,1,1+2) C=(2,1,1,1,1) 【注意B已经被踢出】

4

5 回答 5

3

HashMap 将是您最好的选择。在单个恒定时间操作中，您可以检查重复并获取适当的聚合结构（我的代码中的 Set）。这意味着您可以在 O(n) 中遍历整个文件。这是一些示例代码：

public void aggregate() throws Exception
  {
    BufferedReader bigFile = new BufferedReader(new FileReader("path/to/file.csv"));

    // Notice the paramter for initial capacity. Use something that is large enough to prevent rehashings.
    Map<String, HashSet<String>> map = new HashMap<String, HashSet<String>>(500000);

    while (bigFile.ready())
    {
      String line = bigFile.readLine();
      int lastTab = line.lastIndexOf('\t');
      String firstFourColumns = line.substring(0, lastTab);

      // See if the map already contains an entry for the first 4 columns
      HashSet<String> set = map.get(firstFourColumns);

      // If set is null, then the map hasn't seen these columns before
      if (set==null)
      {
        // Make a new Set (for aggregation), and add it to the map
        set = new HashSet<String>();
        map.put(firstFourColumns, set);
      }

      // At this point we either found set or created it ourselves
      String lastColumn = line.substring(lastTab+1);
      set.add(lastColumn);
    }
    bigFile.close();

    // A demo that shows how to iterate over the map and set structures
    for (Map.Entry<String, HashSet<String>> entry : map.entrySet())
    {
      String firstFourColumns = entry.getKey();
      System.out.print(firstFourColumns + "=");

      HashSet<String> aggregatedLastColumns = entry.getValue();
      for (String column : aggregatedLastColumns)
      {
        System.out.print(column + ",");
      }
      System.out.println("");
    }
  }

几点：

  • HashMap 的 initialCapaticy 参数很重要。如果条目的数量大于容量，则结构会被重新散列，这非常慢。默认初始容量为 16，这将导致您多次重新散列。选择一个您知道大于前四列的唯一集数的值。
  • 如果聚合中的有序输出很重要，您可以将 HashSet 切换为 TreeSet。
  • 此实现将使用大量内存。如果您的文本文件是 2GB，那么您可能需要 jvm 中的大量 RAM。您可以添加 jvm 参数-Xmx4096m以将最大堆大小增加到 4GB。如果您没有至少 4GB，这可能不适合您。
  • 这也是一个可并行化的问题，所以如果你不顾一切，你可以线程化它。不过，对于一次性代码来说，这将是一个很大的努力。[编辑：正如评论中指出的那样，这一点可能不正确]
于 2012-04-10T15:45:31.847 回答
1

我会在前四列对整个列表进行排序，然后遍历列表，知道所有重复项都在一起。这将为您提供 O(NlogN) 的排序和 O(N) 的遍历，而不是 O(N^2) 的嵌套循环。

于 2012-04-10T15:31:35.323 回答
1

我会使用记录的 HashSet。这可能导致 O(n) 时间而不是 O(n^2)。您可以创建一个类，该类具有每个字段，每行一个实例。

你需要有相当数量的内存，但现在 16 到 32 GB 相当便宜。

于 2012-04-10T15:42:58.350 回答
0

我会做一些与 Eric 的解决方案类似的事情，但不是将实际字符串存储在 HashMap 中，而是存储行号。因此，对于特定的四列散列，您将存储散列到该值的行号列表。然后在通过数据的第二条路径上，您可以删除这些行号处的重复项/根据需要添加 +x。

这样，您的内存需求将小很多。

于 2012-04-10T15:58:28.050 回答
0

如果您有足够的（免费）RAM，已经发布的解决方案很好。由于 Java 倾向于“仍然工作”，即使它进行大量交换，如果您认为 RAM 可能是限制因素，请确保您没有太多的交换活动。

如果您的 RAM 真的太少，一个简单的“一次性”解决方案是首先将文件划分为多个文件，具体取决于前四列中的数据（例如，如果第三列值或多或少均匀分布，则按该列的最后两位数字）。只需检查一次文件，并在读取记录时将它们写入 100 个不同的文件，具体取决于分区值。这将需要最少的 RAM，然后您可以使用更少的内存来处理剩余的文件（如果分区值分布良好，则每个文件只有大约 20MB），然后再次连接结果。

明确一点：如果你有足够的 RAM（不要忘记操作系统也希望有一些用于磁盘缓存和后台活动），这个解决方案会更慢（甚至可能是 2 倍，因为两倍的数量数据需要被读取和写入），但如果你被交换到死，它可能会快很多:-)

于 2012-04-10T17:25:58.990 回答