獲得區別的最快方法列表<object>

Question

我正在開發一個能夠找到文件夾之間的文件差異的程序。我製作了一個遍歷給定文件夾的文件夾結構的方法，併爲每個子文件夾構建一棵樹。每個節點都包含一個文件列表，即該文件夾中的文件。每個節點都有一定數量的子項，它們對應於該文件夾中的文件夾。

現在的問題是要找到一個樹中存在的文件，而不是另一個。我有一個方法：「私人列表差異（節點索引1，節點索引2）」，應該這樣做。但問題是我比較樹木的方式。比較兩棵樹需要大量的時間 - 當每個輸入節點包含大約70,000個文件時，Diff方法大約需要3-5分鐘才能完成。

目前，我正在做這種方式：

private List<MyFile> Diff(Node index1, Node index2) 
    { 
     List<MyFile> DifferentFiles = new List<MyFile>(); 

     List<MyFile> Index1Files = FindFiles(index1); 
     List<MyFile> Index2Files = FindFiles(index2); 

     List<MyFile> JoinedList = new List<MyFile>(); 
     JoinedList.AddRange(Index1Files); 
     JoinedList.AddRange(Index2Files); 
     List<MyFile> JoinedListCopy = new List<MyFile>(); 
     JoinedListCopy.AddRange(JoinedList); 
     List<string> ChecksumList = new List<string>(); 

     foreach (MyFile m in JoinedList) 
     { 

      if (ChecksumList.Contains(m.Checksum)) 
      { 
       JoinedListCopy.RemoveAll(x => x.Checksum == m.Checksum); 
      } 
      else 
      { 
       ChecksumList.Add(m.Checksum); 
      } 
     } 

     return JoinedListCopy; 
    } 

和節點類看起來是這樣的：

class Node 
{ 
    private string _Dir; 
    private Node _Parent; 
    private List<Node> _Children; 
    private List<MyFile> _Files; 
} 

Answer 1

，而不是做很多通過List結構搜索（這是很慢），你可以把所有的校驗和成HashSet可以是多更有效地搜索。

private List<MyFile> Diff(Node index1, Node index2) 
{ 
    var Index1Files = FindFiles(index1); 
    var Index2Files = FindFiles(index2); 

    //this is all of the files in both 
    var intersection = new HashSet<string>(Index1Files.Select(file => file.Checksum) 
     .Intersect(Index2Files.Select(file => file.Checksum))); 

    return Index1Files.Concat(Index2Files) 
     .Where(file => !intersection.Contains(file.Checksum)) 
     .ToList(); 
} 

Answer 2

如何：

public static IEnumerable<MyFile> FindUniqueFiles(IEnumerable<MyFile> index1, IEnumerable<MyFile> index2) 
    { 
     HashSet<string> hash = new HashSet<string>(); 

     foreach (var file in index1.Concat(index2)) 
     { 
      if (!hash.Add(file.Checksum)) 
      { 
       hash.Remove(file.Checksum); 
      } 
     } 

     return index1.Concat(index2).Where(file => hash.Contains(file.Checksum)); 
    } 

這將在工作假設一棵樹不會包含重複。 Servy的答案將適用於所有情況。

Answer 3

是否爲樹中的每個元素保留整個FileSystemObject？如果是這樣，我會認爲你的記憶開銷會很大。爲什麼不使用文件名或校驗和並將其放入列表中，然後對其進行比較？

Answer 4

我可以看到，這不僅僅是一個「獨特」功能，你真正需要的是在JoinedListCopy集合中只存在一次的所有實例，而不僅僅是JoinedListCopy集合中所有不同實例的列表。

Servy有一個非常好的答案，我會建議一種不同的方法，它利用了linq的一些更有趣的功能，或者至少我覺得它們很有趣。

var diff_Files = (from a in Index1Files 
       join b in Index2Files 
       on a.CheckSum equals b.CheckSum 
       where !(Index2Files.Contains(a) || Index1Files.Contains(b))).ToList() 

另一種方式的結構，「哪裏」，這可能會更好地工作，文件實例可能實際上並不相同，至於代碼平等而言...

where !(Index2Files.Any(c=>c.Checksum == a.Checksum) || Index1Files.Any(c=>c.Checksum == b.Checksum)) 

看看個別校驗和，而不是整個文件對象實例。

基本策略基本上就是您已經在做的，只是更有效一些：加入收藏並相互過濾以確保您只獲取唯一的條目。

另一種方式做，這是使用計數功能在LINQ

var diff_Files = JoinedListCopy.Where(a=> JoinedListCopy.Count(b=>b.CheckSum == a.CheckSum) == 1).ToList(); 

嵌套的LINQ並不總是在世界上最有效的事情，但應該工作還算不錯，得到所有情況下，只有發生一次。我喜歡這種方法，實際上最好的辦法是，儘可能少地搞亂某些東西，但是我首先使用的連接可能會更有效率。