遍历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();