遍歷2個列表

Question

我有一個List<T1>項目和第二個項目List<T2>。這兩個列表按屬性A按字母順序排序。我知道List<T2>中的項目列表是List<T1>的子集，並且中不存在List<T1>中不存在的項目。

我需要迭代List<T1>並在每次匹配變量List<T2>時更改變量。什麼是最快和最好的方式來做到這一點？我假設我需要遍歷這兩個列表，但我知道做一個嵌套的foreach是沒有意義的。

Answer 1

對於這種類型的東西，我更喜歡雙重循環。看下面的例子。

var super = new List<Contact>(); 
super.Add(new Contact() {Name = "John"}); 
super.Add(new Contact() {Name = "Larry"}); 
super.Add(new Contact() {Name = "Smith"}); 
super.Add(new Contact() {Name = "Corey"}); 

var sub = new List<Contact>(); 
sub.Add(new Contact() {Name = "Larry"}); 
sub.Add(new Contact() {Name = "Smith"}); 

var subCount = 0; 
for(int i=0; i<super.Count && subCount < sub.Count; i++) 
{ 
    if (super[i].Name == sub[subCount].Name) 
    { 
     Act(super[i], sub[subCount]); 
     subCount++; 
    } 
} 

其中Act(...)執行您正在尋找的任何操作。

循環每次增加超級列表，但只在您找到匹配時遞增子列表。

請注意，這隻適用於你的兩個假設。 1）列表都是排序的，2）第二個列表是第一個列表的子集。

Answer 2

如果名單是不是太大，您這樣做最簡單的方法是調用Contains：

foreach(var item in list1) { 
    if (list2.Contains(item) { 
     //Do something 
    } 
} 

你可以使其更快通過使用自定義IComparer<T>調用BinarySearch，像這樣：

var hashset = new HashSet<YourClass>(list2); 
foreach(var item in list1) { 
    if (hashset.Contains(item) { 
     //Do something 
    } 
} 

：

class MyComparer : IComparer<YourClass> { 
    private MyComparer() { } 
    public static readonly MyComparer Instance = new MyComparer(); 

    public int CompareTo(YourClass a, YourClass b) { 
     //TODO: Handle nulls 
     return a.SomeProperty.CompareTo(b.SomeProperty); 
    } 
} 
foreach(var item in list1) { 
    if (list2.BinarySearch(item, MyComparer.Instance) >= 0) { 
     //Do something 
    } 
} 

.NET 3.5中，你可以通過使用HashSet<T>使其更快

如果您的列表非常大，您應該測量每個選項的性能並進行相應選擇。
否則，請選擇其中一個最簡單的選項。

Answer 3

如果它們都在唯一屬性上排序，則可以在迭代過程中使用它。這個想法是循環遍歷超集，然後基於排序後的唯一屬性推進子集迭代器，直到它匹配或者更大/更小（取決於排序順序）而不是超集。

對於升序排序屬性：

if (subsetList.Count > 0) 
{ 
    using(IEnumerator<T2> subset = subsetList.GetEnumerator()) 
    { 
     subset.MoveNext(); 
     T2 subitem = subsetList.Current; 
     foreach(T1 item in supersetList) 
     { 
      while (item.A > subitem.A && 
        subset.MoveNext()) 
      { 
       subitem = subset.Current; 
      } 

      if (item.A == subitem.A) 
      { 
       // Modify item here. 
      } 
     } 
    } 
} 

注意，這實際上並不依賴於supersetList是的subsetList一個超集。在假設成立的情況下，EndangeredMassa的解決方案更爲簡潔。

Answer 4

您的問題意味着您要避免每次都迭代第二個列表中的所有項目，這是在使用Contains()的最糟糕的天真解決方案中會發生的情況。由於這兩個列表都是排序的，並且list2是list1的子集，因此您知道list1中的條目的索引將小於list2中的相應條目。考慮到這一點，您可以使用兩個統計員製作高效的O（n）解決方案：

Debug.Assert(list1.Count > 0); 
Debug.Assert(list1.Count >= list2.Count); 

var enum1 = list1.GetEnumerator(); 
var enum2 = list2.GetEnumerator(); 

enum1.MoveNext(); 
while (enum2.MoveNext()) 
{ 
    // Skip elements from list1 that aren't equal to the current entry in list2 
    while (!enum1.Current.Equals(enum2.Current)) 
     enum1.MoveNext(); 

    // Fire the OnEqual event for every entry in list1 that's equal to an entry 
    // in list2 
    do { 
     OnEqual(enum1.Current, enum2.Current); 
    } while (enum1.MoveNext() && enum1.Current.Equals(enum2.Current)); 
} 

enum1.Dispose(); 
enum2.Dispose();