Итерация через 2 списка

Question

У меня есть List<T1> пунктов, а второй List<T2> предметов. Оба списка сортируются в алфавитном порядке по свойству A. Я знаю, что список элементов в List<T2> является подмножеством List<T1>, и нет элементов в List<T2>, которые не существуют в 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 
    } 
} 

Вы можете сделать это быстрее, вызвав BinarySearch с помощью пользовательской IComparer<T>, например:

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>:

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

Если ваши списки очень большие, вы должны измерить производительность каждой опции и выбрать соответственно.
В противном случае выберите один из первых вариантов, который является самым простым.

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