pasujące elementy z dwóch list (lub tablic)

Question

Mam problem z moją pracą, która, mam nadzieję, sprowadza się do następujących: Mam dwa List<int> s, i chcę sprawdzić, czy którykolwiek z s w ListA jest równy dowolny int w ListB. (Mogą to być tablice, jeśli to ułatwia życie, ale myślę, że List<> ma wbudowaną magię, która może pomóc.) I jestem pewien, że jest to problem przyjazny dla LINQ, ale pracuję tutaj w 2.0.

Moje rozwiązanie dotąd do foreach poprzez Lista, a następnie foreach przez ListB,

foreach (int a in ListA) 
{ 
    foreach (int b in ListB) 
    { 
     if (a == b) 
     { 
      return true; 
     } 
    } 
} 

co było faktycznie dość śliski, gdy byli na trzy pozycje długie, ale teraz są one długie i 200 często nie pasują, więc otrzymujemy najgorszy przypadek porównań N^2. Nawet 40 000 porównań przebiega dość szybko, ale myślę, że może mi brakować czegoś, ponieważ N^2 wydaje się dość naiwny dla tego konkretnego problemu.

Dzięki!

Answer 1

Z LINQ, to jest trywialne, jak można nazwać Intersect extension method na Enumerable class dać wam zestaw przecięcie dwóch tablicach:

var intersection = ListA.Intersect(ListB); 

Jednak to ustawić skrzyżowanie, czyli jeśli ListA i ListB nie mają w nim wartości unikatowych, nie dostaniesz żadnych kopii. Innymi słowy, jeśli następuje:

var ListA = new [] { 0, 0, 1, 2, 3 }; 
var ListB = new [] { 0, 0, 0, 2 }; 

Następnie ListA.Intersect(ListB) produkuje:

{ 0, 2 } 

Jeśli spodziewasz:

{ 0, 0, 2 } 

Wtedy będziesz musiał utrzymać liczyć przedmioty samodzielnie i wydajność/dekrement podczas skanowania dwóch list.

pierwsze, że chcesz zbierać Dictionary<TKey, int> z wykazami poszczególnych elementów:

var countsOfA = ListA.GroupBy(i => i).ToDictionary(g => g.Key, g => g.Count()); 

Stamtąd można zeskanować i umieścić ListB że na liście gdy natkniesz elementu w countsOfA :

// The items that match. 
IList<int> matched = new List<int>(); 

// Scan 
foreach (int b in ListB) 
{ 
    // The count. 
    int count; 

    // If the item is found in a. 
    if (countsOfA.TryGetValue(b, out count)) 
    { 
     // This is positive. 
     Debug.Assert(count > 0); 

     // Add the item to the list. 
     matched.Add(b); 

     // Decrement the count. If 
     // 0, remove. 
     if (--count == 0) countsOfA.Remove(b); 
    } 
} 

można to zawinąć w metodę rozszerzenia że odracza wykonanie tak:

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first, 
    IEnumerable<T> second) 
{ 
    // Call the overload with the default comparer. 
    return first.MultisetIntersect(second, EqualityComparer<T>.Default); 
} 

public static IEnumerable<T> MultisetIntersect(this IEnumerable<T> first, 
    IEnumerable<T> second, IEqualityComparer<T> comparer) 
{ 
    // Validate parameters. Do this separately so check 
    // is performed immediately, and not when execution 
    // takes place. 
    if (first == null) throw new ArgumentNullException("first"); 
    if (second == null) throw new ArgumentNullException("second"); 
    if (comparer == null) throw new ArgumentNullException("comparer"); 

    // Defer execution on the internal 
    // instance. 
    return first.MultisetIntersectImplementation(second, comparer); 
} 

private static IEnumerable<T> MultisetIntersectImplementation(
    this IEnumerable<T> first, IEnumerable<T> second, 
    IEqualityComparer<T> comparer) 
{ 
    // Validate parameters. 
    Debug.Assert(first != null); 
    Debug.Assert(second != null); 
    Debug.Assert(comparer != null); 

    // Get the dictionary of the first. 
    IDictionary<T, long> counts = first.GroupBy(t => t, comparer). 
     ToDictionary(g => g.Key, g.LongCount(), comparer); 

    // Scan 
    foreach (T t in second) 
    { 
     // The count. 
     long count; 

     // If the item is found in a. 
     if (counts.TryGetValue(t, out count)) 
     { 
      // This is positive. 
      Debug.Assert(count > 0); 

      // Yield the item. 
      yield return t; 

      // Decrement the count. If 
      // 0, remove. 
      if (--count == 0) counts.Remove(t); 
     } 
    } 
} 

Zauważ, że oba te podejścia są (i przepraszam jeśli jestem rozbiór notacji Big-O tutaj) O(N + M) gdzie N jest numerem pozycji w pierwszej tablicy i M jest liczba elementów w drugiej tablicy . Musisz przeskanować każdą listę tylko raz i zakłada się, że otrzymanie kodów skrótu i ​​wykonywanie wyszukiwań w hasłach to operacja O(1) (stała).

Answer 2

Co powiesz na temat używania metody BinarySearch zamiast powtarzania wszystkich elementów w wewnętrznej pętli?

Answer 3

Załaduj całą listę ListA do instancji HashSet, a następnie przetestuj element foreach na liście B w zestawie HastSet: Jestem prawie pewny, że będzie to O (N).

//untested code ahead 
HashSet<int> hashSet = new HashSet<int>(ListA); 
foreach (int i in ListB) 
{ 
    if (hashSet.Contains(i)) 
     return true; 
} 

Tutaj to samo w jednym wierszu:

return new HashSet<int>(ListA).Overlaps(ListB); 

HashSet nie istnieje w .NET 3.5, więc w .NET 2.0 można użyć Dictionary<int,object> (zamiast używania HashSet<int>) i zawsze przechowuj null jako obiekt/wartość w Słowniku, ponieważ interesują Cię tylko klucze.

Answer 4

Zamiast iteracja każdej listy, przyjrzeć się metodzie List.Contains:

foreach (int a in ListA) 
{ 
    if (ListB.Contains(a)) 
    return true; 
} 

Answer 5

Chris daje O (N) rozwiązanie przez mieszania. Teraz, w zależności od stałego współczynnika (z powodu skrótu), warto rozważyć rozwiązanie O (N log (N)) poprzez sortowanie. Istnieje kilka różnych wariantów, które możesz rozważyć w zależności od przypadku użycia.

1. Sortowanie ListB (O (log n (N)), i za pomocą algorytmu wyszukiwania, aby analizować każdy element w Lista (która znów O (N) * o (log (n))).

2. Sortuj zarówno lista i ListB (o (log N (N)), i używać o (n) algorytm porównania tych list duplikatów.

Jeśli oba wykazy będą wykorzystywane więcej niż raz, preferowana jest druga metoda.