java - 替代嵌套循环进行比较

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)));
                }
            }

我读过一些关于嵌套循环必要性的不同意见，我想知道是否有人有更有效的替代方案。

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

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

此外，天哪，这个网站的响应速度很快。谢谢，伙计们。

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 所述，您必须注意性能，因为当您简单地检查字节时，一旦发现两个不同的字节就会停止，而计算哈希将需要检查整个文件。当您有很多文件或文件很小时，这会很有效。最好的办法是对这两种方法进行基准测试，看看是否存在显着差异。