替代嵌套循环进行比较

Question

我目前正在编写一个程序,需要比较可变大小的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中的所有文件,假设它们都需要进行比较.如果一个嵌套循环就足够了,那很酷,我只想检查这是一个合适的方法,按惯例.

Answer 1

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

这基本上是因为无论如何你都必须检查列表中的每一对文件，但这意味着每对文件的复杂度仅为 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 中所述，您必须小心性能，因为当您简单地检查字节时，一旦发现两个不同的字节，您就会停止，而计算哈希将需要检查整个文件。当您有很多文件或文件相当小时，这会很有效。最好的办法是对两种方法进行基准测试，看看是否存在显着差异。

Answer 2

我对您的 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. 如果找到条目，请将当前文件与从映射中获取的列表中的每个文件进行按字节比较。如果您在列表中找到重复的文件，宾果！否则将当前文件添加到列表中。
   4. 如果未找到条目，请创建一个新的映射条目，以“FileHash”作为键，并将当前文件作为值列表的第一个元素。

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

一些性能问题：

• 如果您使用良好的加密散列函数来生成文件散列，那么在 3.3 中找到列表中具有多个元素的条目的机会微乎其微，并且文件的按字节比较也不会发生的机会微乎其微。说文件相等也是小得可怜。然而，计算加密哈希的成本将大于计算较低质量哈希的成本。

• 如果您确实使用较低质量的哈希值，则可以通过在进行字节比较之前查看文件大小来降低比较更多文件的潜在成本。如果这样做，您可以将映射类型设置HashMap<FileHash, List<FileTuple>>为同时保存 a及其长度的FileTuple类。File

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