5

我目前正在编写一个程序，该程序需要比较可变大小的 ArrayList 中的每个文件。现在，我这样做的方式是通过嵌套代码循环：

         if(tempList.size()>1){
            for(int i=0;i<=tempList.size()-1;i++)
                //Nested loops.  I should feel dirty?
                for(int j=i+1;j<=tempList.size()-1;j++){
                    //*Gets sorted.
                    System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
                }
            }

我已经阅读了一些关于嵌套循环必要性的不同意见，我想知道是否有人有更有效的选择。

乍一看，无论哪种方式，每次比较都需要进行，因此性能应该相当稳定，但我有一定的信心有一种更清洁的方法可以做到这一点。任何指针？

编辑:: 为清楚起见，这只是功能的一部分。文件已根据长度进行比较并放入存储桶中 - 在通过集合的映射并找到长度大于 1 的存储桶后，它会运行它。所以 - 这些都是相同大小的文件。在获取字节之前，我也会进行校验和比较，但现在我只是想清理循环。

此外，圣牛这个网站反应很快。多谢你们。

EDIT2:: 抱歉，为了进一步澄清：我认为文件处理部分我已经很好地掌握了 - 首先，我按长度比较和排序，然后按校验和，然后按字节 - 我遇到的问题是如何正确处理需要有效地比较 ArrayList 中的所有文件，假设它们都需要进行比较。如果嵌套循环就足够了，那很酷，我只是想检查一下这是否是一种合适的方法，按照惯例。

4

5 回答 5

4

一个好的优化是首先计算文件的所有哈希值，然后对列表进行一次循环。

这基本上是因为无论如何您都必须检查列表中的每一对文件，但这意味着每对文件的复杂度为 O(1)，而不是为要检查的每个文件计算很多东西。

你可以这样做：

HashSet<YourFile> fileSet = new HashSet<YourFile>();
ArrayList<YourFile> files = new ArrayList<YourFile>();

class YourFile
{
  int hashcode = -1;

  public int hashCode()
  {
     // override it to provide an hashcode based on file contents
     // you can also cache it to avoid recalculating anything

     if (hashcode == -1)
       hashcode = calculateIt();

     return hashcode;
  }
}

// fill up files
files.add(...);

// do comparisons
for (YourFile f : files)
{
  if (fileSet.contains(f))
    // f and fileSet.get(f) are equal: this is a tricky utilization of the hashCode() method so be careful about it!
  else
  {
    fileSet.put(f);
    // since there's not a file with same hashcode you just add this one
  }
}

这实际上会删除内部循环，因为当您使用hashSet.contains它时会检查所有已添加的文件，但复杂度为 O(1)。

正如 doublep 所述，您必须注意性能，因为当您明确检查字节时，一旦发现两个不同的字节就会停止，同时计算哈希需要检查整个文件。当您有很多文件或文件很小时，这会很好用。最好的办法是对这两种方法进行基准测试，看看是否存在显着差异。

于 2010-04-23T22:17:35.063 回答
4

我对您的 EDIT2 问题的回答分为两部分

部分是如果您有少量文件，那么您的嵌套循环方法应该没问题。性能为O(N**2)，最优解为O(N)。但是，如果N足够小，则使用哪种方法不会有太大区别。如果您确定 N 可以很大，则只需要考虑替代解决方案。

第二部分阐述了一种利用文件哈希来获得O(N)检测重复项的解决方案的算法。这就是前面的答案所暗示的。

  1. 创建一个FileHash类来表示文件哈希值。这需要定义实现文件哈希的字节相等的方法equals(Object)。hashCode()

  2. 创建HashMap<FileHash, List<File>>地图实例。

  3. 对于File您输入中的每个ArrayList：

    1. 计算文件的哈希值，并FileHash为它创建一个对象。
    2. FileHash在地图中查找：
    3. 如果您找到了一个条目，请将当前文件与您从地图中获得的列表中的每个文件进行逐字节比较。如果您在列表中发现重复文件，BINGO！否则将当前文件添加到列表中。
    4. 如果您没有找到条目，请创建一个新的映射条目，其中“FileHash”作为键，当前文件作为值列表的第一个元素。

（请注意，上面的地图实际上是一个多地图，并且有可用的 3rd 方实现；例如，在 Apache commons 集合和 Google 集合中。为了简单起见，我在上面的表格中展示了算法。）

一些性能问题：

  • 如果您使用良好的加密哈希函数来生成文件哈希，那么在 3.3 中找到列表中包含多个元素的条目的机会非常小，并且文件的逐字节比较的机会不会说文件相等也很小。但是，计算加密哈希的成本将大于计算质量较低的哈希的成本。

  • 如果您确实使用了较低质量的哈希，则可以通过在进行逐字节比较之前查看文件大小来降低比较更多文件的潜在成本。如果你这样做，你可以将地图类型HashMap<FileHash, List<FileTuple>>设为 whereFileTuple是一个同时包含 aFile和它的长度的类。

  • 您可以通过仅使用（例如）每个文件的第一个块的散列来降低散列的成本。但这增加了两个文件可能具有相同哈希但仍然不同的可能性；例如在第二个街区。这是否重要取决于文件的性质。（但例如，如果您只是对源代码文件集合的前 256 个字节进行校验和，则可能会发生大量冲突……由于存在相同的版权标头！）

于 2010-04-24T05:40:12.403 回答
3

根据您正在做什么，您可能会通过从不比较不同大小的文件来获得相当大的加速。正如其他答案中所建议的那样，在相同大小的文件中，仅比较具有相同哈希值的文件（通过任何算法）。

编辑：

但是，计算哈希可能会产生反作用。首先，如果您只是将文件与另一个文件进行比较，则永远不要这样做：您需要完全读取文件以构建散列，并且一次读取就足以进行比较，因此您将一无所获。

其次，如果您很少期望匹配并且实际上文件会有很大差异（早期），那么无论要比较的文件数量如何，计算哈希都可能适得其反。这是因为在这种情况下失败的比较会提前失败（即不读取整个文件），而对于哈希构建，您将需要完整读取。或者，您可以构建“部分”散列（例如，文件的前 10 kb 的散列），但请记住使用所有文件的相等块。

于 2010-04-23T22:19:29.127 回答
2

将所有内容与其他所有内容进行比较必然是 O(n²)。但是你可以尝试一些技巧。主要是使比较更便宜；这可以通过为每个文件生成一个哈希码并首先比较它们来完成，这至少可以避免大多数比较（使用足够好的算法，你几乎可以避免每一个）。如果您不需要保留有关哪些文件相等的信息，您也可以加快速度；生成Set每个文件的哈希码，并在最后测试以查看集合的大小是否与文件列表的大小相同。

于 2010-04-23T22:15:17.927 回答
2

一个小的清理是删除初始大小测试 - 如果大小小于 2，它会简单地掉出来而没有进行任何比较。更好地遵守 Java 编码约定将是在循环中进行比较i < tempList.size()而不是i <= tempList.size() - 1- 这只会使您的代码更容易被其他程序员理解。这些更改都不会对性能产生任何影响。

for (int i = 0; i < tempList.size(); i++)
    for (int j = i + 1; j < tempList.size(); j++) {
        //*Gets sorted.
        System.out.println(checkBytes(tempList.get(i), tempList.get(j)));
    }
于 2010-04-23T22:25:54.737 回答