替代嵌套循環比較

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的桶之後，它運行這個。所以 - 這些都是相同大小的文件。我會在進入字節之前進行校驗和比較，但現在我只是想清理循環。

另外，聖牛這個網站反應速度很快。多謝你們。我想 - 首先，我比較和排序的長度，然後通過校驗和，然後按字節 - 我有問題的進一步澄清：文件處理部分我有一個體面的把握，我認爲 - 是如何正確處理需要比較ArrayList中的所有文件，假設它們都需要進行比較。如果嵌套循環對此足夠了，那很酷，我只是想檢查這是一個合適的方法，按照慣例。

Answer 1

我的回答你的問題EDIT2分爲兩個部分

的部分是，如果你有一個小的文件，那麼你的嵌套循環的方法應該是罰款。性能爲O(N**2)，最佳解決方案爲O(N)。但是，如果N足夠小，則使用哪種方法不會產生太大影響。如果你確信N可能很大，你只需要考慮一個替代解決方案。

第二部分闡述了一種算法，該算法利用文件哈希得到用於檢測重複項的O(N)解決方案。這是以前的答案提到的。

1. 創建一個FileHash類來表示文件哈希值。這需要定義equals(Object)和hashCode()實現文件哈希的按字節等同的方法。

2. 創建一個HashMap<FileHash, List<File>>地圖實例。

3. 對於您輸入ArrayList每個File：

   1. 計算該文件的哈希，併爲它創建一個FileHash對象。
   2. 在地圖中查找FileHash：
   3. 如果您發現了一個條目，請將您當前的文件與從地圖獲取的列表中的每個文件進行按字節進行比較。如果您在列表中找到重複的文件，BINGO！否則，將當前文件添加到列表中。
   4. 如果你沒有找到一個條目，創建了「FileHash`一個新的映射條目爲重點，與當前文件作爲值列表的第一個元素。

（註上面的地圖實際上是一張多地圖，並且有第三方實現可用;例如在Apache公共收藏和Google收藏中。我提出的算法在上面簡單起見形式）

一些性能問題：

• 如果你使用一個很好的加密哈希函數來生成文件哈希值，那麼機會在3.3中找到一個條目中有多個元素的條目非常小，並且文件的字節比較不會說文件是相等的機會也很小。但是，計算加密哈希的開銷將大於計算較低質量哈希的開銷。

• 如果你使用一個低質量的哈希值，你可以做你的逐個字節比較之前減少通過查看文件大小比較多個文件的潛在成本。如果你這樣做就可以使地圖類型HashMap<FileHash, List<FileTuple>>其中FileTuple是同時擁有一個File和長度的類。

• 你可能只用（說）每個文件的第一個塊的哈希散列降低的成本。但是這增加了兩個文件可能具有相同散列但仍然不同的可能性;例如在第二塊。這是否重要取決於文件的性質。 （但是，舉例來說，如果您只檢查了一組源代碼文件的前256個字節，則可能會遇到大量衝突......由於存在相同的版權標題！）

Answer 2

比較一切和其他所有東西一樣，必然是O（n²）。但你可以嘗試一些技巧。主要的是比較便宜;這可以通過爲每個文件生成一個哈希碼並首先比較這些哈希碼來完成，這至少可以避免大多數比較（使用足夠好的算法，並且幾乎可以避免每一個）。如果您不需要保留有關哪些文件相同的信息，則還可以加快速度;產生每個文件的哈希碼的Set，並在最後測試以查看該集合的大小是否與文件列表的大小相同。

Answer 3

一個好的優化方法是首先計算文件的所有哈希值，然後在列表中執行一個循環。

這基本上是因爲你無論如何都要檢查你列表中的每一對文件，但這意味着每一對文件只有一個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 4

根據你正在做什麼，你可能會得到相當大的加速，從不比較不同大小的文件。在相同大小的文件中，只比較具有相同散列的文件（通過任何算法），正如其他答案中所建議的那樣。

編輯：

計算散列可以conunterproductive，雖然。首先，如果您僅將文件與另一文件進行比較，請不要這樣做：您需要完全讀取文件以構建散列，並且一次讀取已足以進行比較，因此您將不會獲得任何結果。其次，如果你很少期望匹配，並且實際上文件會有很大的不同（早期），計算散列可能會適得其反，無論要比較的文件數量如何。這是因爲在這種情況下失敗的比較會提前失敗（即不讀取整個文件），而對於哈希構建，則需要完整的讀取。或者，您可以構建「部分」散列（例如，文件的前10 kb的散列），但請記住使用相同的所有文件塊。

Answer 5

一個小小的清理工作就是刪除初始尺寸測試 - 如果尺寸小於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))); 
    }