Проверьте, имеют ли два списка значения общего доступа в C#

Question

Я хотел бы знать, имеют ли два списка общие значения перед применением пересечения. Что-то вроде bool DoIntersect (listA, listB) было бы невероятно!

Это код, который я придумал:

// Person is a class with Id and Name properties 
List<Person> people1; 
List<Person> people2; 

// Populate people1 and people2... 

// My current solution (pseudocode obviously)... 

if (DoIntersect(people1, people2)) 
{ 
    people1 = people1.Intersect(people2) 
} 
else 
{ 
    /* No shared people */ 
    throw exception; 
} 

// Continue with the process... 

Answer 1

Это зависит от того, что именно вы хотите:

// are there any common values between a and b? 
public static bool SharesAnyValueWith<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    return a.Intersect(b).Any(); 
} 

Для списков, которые не перекрывают друг друга, это будет перебирать а и б каждый раз. Для списков, которые перекрываются, это приведет к повторению всей последовательности через a, затем через b, пока не будет найден первый перекрывающий элемент.

// does a contain all of b? (ignores duplicates) 
public static bool ContainsAllFrom<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    return !b.Except(a).Any(); 
} 

Это будет перебирать один раз, а затем будет перебирать б, остановка на первом элементе в б не в.

// does a contain all of b? (considers duplicates) 
public static bool ContainsAllFrom<T>(this IEnumerable<T> a, IEnumerable<T> b) 
{ 
    // get the count of each distinct element in a 
    var counts = a.GroupBy(t => t).ToDictionary(g => g.Key, g => g.Count()); 
    foreach (var t in b) { 
     int count; 
     // if t isn't in a or has too few occurrences return false. Otherwise, reduce 
     // the count by 1 
     if (!counts.TryGetValue(t, out count) || count == 0) { return false; } 
     counts[t] = count - 1; 
    } 

    return true; 
} 

Подобным образом, это будет перебирать один раз, а затем будет перебирать б, остановка на первом элементе в б не в.

Answer 2

Я считаю, не изменяя тот факт, что вы используете список, вы не можете получить более высокую производительность.

Однако, если бы 2 отсортированных списков начать с (требует накладных расходов при их создании), то вы можете перебирать их со сложностью O (N), чтобы выяснить, если у вас есть общие ценности.

Edit:

Хотя оригинальный OP не имеет 2 отсортированных списков, в случае, если кто-то будет нужно, здесь реализация для проверки Пересечения в точке О (п):

public Boolean DoIntersect(SortedList<int,String> listA,SortedList<int,String> listB ) 
    { 
     if (listA == null || listA.Count == 0 || listB == null || listB.Count == 0) 
     { 
      return false; 
     } 
     var keysA = listA.Keys; 
     var keysB = listB.Keys; 
     int i = 0, j = 0; 
     while (i < listA.Count && j < listB.Count) 
     { 
      if (keysA[i] < keysB[j]) 
      { 
       i++; 
      }else if (keysA[i] > keysB[j]) 
      { 
       j++; 
      } 
      else 
      { 
       return true; 
      } 
     } 

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