schnellste Weg, um gemeinsame Elemente über mehrere Listen in C#

Question

Angesichts der folgenden zu finden:

List<List<Option>> optionLists; 

was wäre ein schneller Weg sein, um die Teilmenge der Option Objekte zu bestimmen, die in allen N-Listen erscheinen? Die Gleichheit wird durch eine Zeichenfolgeeigenschaft wie option1.Value == option2.Value bestimmt.

Also sollten wir mit List<Option> enden, wo jedes Element nur einmal angezeigt wird.

Answer 1

Ok, dies wird die Liste der Option Objekte finden, die einen Wert in alle Liste haben.

var x = from list in optionLists 
     from option in list 
     where optionLists.All(l => l.Any(o => o.Value == option.Value)) 
     orderby option.Value 
     select option; 

Es tut nicht einem „deutlichen“ wählen, so wird es mehr Option Objekte zurück, mit dem gleichen Wert einige von ihnen.

Answer 2

Sortieren, dann etwas tun, das einer Mischsortierung ähnelt.

Grundsätzlich würden Sie dies tun:

1. Rufen Sie das erste Element aus jeder Liste
2. die Elemente vergleichen, gleich, wenn der Ausgang
3. Wenn eines der Elemente vor den anderen sind, sortieren weise , abrufen aus der entsprechenden Liste ein neues Element, um es zu ersetzen, andernfalls neue Objekte abrufen, sie alle aus dem ganzen Liste
4. Solange Sie noch Einzelteile erhielten, ersetzen 2. zurück

Answer 3

Wie wäre es mit einem hashSet? Auf diese Weise können Sie tun, was Sie wollen, in O (n), wobei n die Anzahl der Elemente in allen Listen kombiniert ist, und ich denke, das ist der schnellste Weg, dies zu tun.

Sie müssen nur jede Liste iterieren und die Werte fügen Sie in die Hashset finden Wenn Sie einen Schlüssel einsetzen, die bereits vorhanden Sie falsch als Rückgabewert des .add method, sonst wahr zurückgegeben wird

erhalten

Answer 4

Hier ist eine viel efficent Implementierung:

static SortedDictionary<T,bool>.KeyCollection FindCommon<T> (List<List<T>> items) 
{ 
    SortedDictionary<T, bool> 
    current_common = new SortedDictionary<T, bool>(), 
    common = new SortedDictionary<T, bool>(); 

    foreach (List<T> list in items) 
    { 
    if (current_common.Count == 0) 
    { 
     foreach (T item in list) 
     { 
     common [item] = true; 
     } 
    } 
    else 
    { 
     foreach (T item in list) 
     { 
     if (current_common.ContainsKey(item)) 
      common[item] = true; 
     else 
      common[item] = false; 
     } 
    } 

    if (common.Count == 0) 
    { 
     current_common.Clear(); 
     break; 
    } 

    SortedDictionary<T, bool> 
     swap = current_common; 

    current_common = common; 
    common = swap; 
    common.Clear(); 
    } 

    return current_common.Keys; 
}  

Es funktioniert durch eine Menge aller Elemente, die für alle Listenerstellung so weit verarbeitet und jede Liste zu vergleichen mit dieser s et, Erstellen einer temporären Menge der Elemente, die der aktuellen Liste und der Liste der bisher üblichen Elemente gemeinsam sind. Effektiv ein O (n.m), wobei n die Anzahl der Listen und m die Anzahl der Einträge in den Listen ist.

Ein Beispiel der Verwendung es:

static void Main (string [] args) 
{ 
    Random 
    random = new Random(); 

    List<List<int>> 
    items = new List<List<int>>(); 

    for (int i = 0 ; i < 10 ; ++i) 
    { 
    List<int> 
     list = new List<int>(); 

    items.Add (list); 

    for (int j = 0 ; j < 100 ; ++j) 
    { 
     list.Add (random.Next (70)); 
    } 
    } 

    SortedDictionary<int, bool>.KeyCollection 
    common = FindCommon (items); 

    foreach (List<int> list in items) 
    { 
    list.Sort(); 
    } 

    for (int i = 0 ; i < 100 ; ++i) 
    { 
    for (int j = 0 ; j < 10 ; ++j) 
    { 
     System.Diagnostics.Trace.Write (String.Format ("{0,-4:D} ", items [j] [i])); 
    } 

    System.Diagnostics.Trace.WriteLine (""); 
    } 

    foreach (int item in common) 
    { 
    System.Diagnostics.Trace.WriteLine (String.Format ("{0,-4:D} ", item)); 
    } 
} 

Answer 5

ich die Performance-Statistiken nicht haben, aber wenn Sie wollen nicht Ihre eigene Methode, verschiedene Sammlungen Bibliotheken rollen haben ein ‚Set‘ oder ‚Set (T) 'Objekt, das die üblichen festgelegten Verfahren bieten. (aufgelistet in der Reihenfolge, in der ich sie benutzen würde).

1. IESI Collections (buchstäblich nur Set-Klassen)
2. PowerCollections (eine Weile nicht mehr aktualisiert)
3. C5 (nie benutzt persönlich)

Answer 6

Aufbauend auf Matt's answer, da wir in Optionen nur daran interessiert sind dass alle Listen gemeinsam sind, können wir einfach nach Optionen in der ersten Liste suchen, die die anderen teilen:

var sharedOptions = 
    from option in optionLists.First().Distinct() 
    where optionLists.Skip(1).All(l => l.Contains(option)) 
    select option; 

Wenn eine Optionsliste keine doppelten Werte enthalten kann, ist der Aufruf Distinct nicht erforderlich. Wenn die Listen in der Größe stark variieren, wäre es besser, über die Optionen in der kürzesten Liste zu iterieren, anstatt die Liste zu öffnen, die zufällig First ist. Sortierte oder gehashte Sammlungen könnten verwendet werden, um die Suchzeit des Contains Aufrufs zu verbessern, obwohl es für eine moderate Anzahl von Elementen keinen großen Unterschied machen sollte.

Answer 7

Sie können dies tun, indem Vorkommen aller Elemente in allen Listen zählen - die Elemente, deren Vorkommen Zahl ist gleich der Anzahl der Listen, sind in allen Listen:

static List<T> FindCommon<T>(IEnumerable<List<T>> lists) 
    { 
     Dictionary<T, int> map = new Dictionary<T, int>(); 
     int listCount = 0; // number of lists 

     foreach (IEnumerable<T> list in lists) 
     { 
      listCount++; 
      foreach (T item in list) 
      { 
       // Item encountered, increment count 
       int currCount; 
       if (!map.TryGetValue(item, out currCount)) 
        currCount = 0; 

       currCount++; 
       map[item] = currCount; 
      } 
     } 

     List<T> result= new List<T>(); 
     foreach (KeyValuePair<T,int> kvp in map) 
     { 
      // Items whose occurrence count is equal to the number of lists are common to all the lists 
      if (kvp.Value == listCount) 
       result.Add(kvp.Key); 
     } 

     return result; 
    } 

Answer 8

/// <summary> 
    /// The method FindCommonItems, returns a list of all the COMMON ITEMS in the lists contained in the listOfLists. 
    /// The method expects lists containing NO DUPLICATE ITEMS. 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="allSets"></param> 
    /// <returns></returns> 
    public static List<T> FindCommonItems<T>(IEnumerable<List<T>> allSets) 
    { 
     Dictionary<T, int> map = new Dictionary<T, int>(); 
     int listCount = 0; // Number of lists. 
     foreach (IEnumerable<T> currentSet in allSets) 
     { 
      int itemsCount = currentSet.ToList().Count; 
      HashSet<T> uniqueItems = new HashSet<T>(); 
      bool duplicateItemEncountered = false; 
      listCount++; 
      foreach (T item in currentSet) 
      { 
       if (!uniqueItems.Add(item)) 
       { 
        duplicateItemEncountered = true; 
       }       
       if (map.ContainsKey(item)) 
       { 
        map[item]++; 
       } 
       else 
       { 
        map.Add(item, 1); 
       } 
      } 
      if (duplicateItemEncountered) 
      { 
       uniqueItems.Clear(); 
       List<T> duplicateItems = new List<T>(); 
       StringBuilder currentSetItems = new StringBuilder(); 
       List<T> currentSetAsList = new List<T>(currentSet); 
       for (int i = 0; i < itemsCount; i++) 
       { 
        T currentItem = currentSetAsList[i]; 
        if (!uniqueItems.Add(currentItem)) 
        { 
         duplicateItems.Add(currentItem); 
        } 
        currentSetItems.Append(currentItem); 
        if (i < itemsCount - 1) 
        { 
         currentSetItems.Append(", "); 
        } 
       } 
       StringBuilder duplicateItemsNamesEnumeration = new StringBuilder(); 
       int j = 0; 
       foreach (T item in duplicateItems) 
       { 
        duplicateItemsNamesEnumeration.Append(item.ToString()); 
        if (j < uniqueItems.Count - 1) 
        { 
         duplicateItemsNamesEnumeration.Append(", "); 
        } 
       } 
       throw new Exception("The list " + currentSetItems.ToString() + " contains the following duplicate items: " + duplicateItemsNamesEnumeration.ToString()); 
      } 
     } 
     List<T> result= new List<T>(); 
     foreach (KeyValuePair<T, int> itemAndItsCount in map) 
     { 
      if (itemAndItsCount.Value == listCount) // Items whose occurrence count is equal to the number of lists are common to all the lists. 
      { 
       result.Add(itemAndItsCount.Key); 
      } 
     } 

     return result; 
    } 

Answer 9

@Skizz Die Methode ist nicht korrekt. Es gibt auch Elemente zurück, die nicht allen Listen in Elementen gemeinsam sind. Hier ist die korrigierte Methode:

/// <summary>. 
    /// The method FindAllCommonItemsInAllTheLists, returns a HashSet that contains all the common items in the lists contained in the listOfLists, 
    /// regardless of the order of the items in the various lists. 
    /// </summary> 
    /// <typeparam name="T"></typeparam> 
    /// <param name="listOfLists"></param> 
    /// <returns></returns> 
    public static HashSet<T> FindAllCommonItemsInAllTheLists<T>(List<List<T>> listOfLists) 
    { 
     if (listOfLists == null || listOfLists.Count == 0) 
     { 
      return null; 
     } 
     HashSet<T> currentCommon = new HashSet<T>(); 
     HashSet<T> common = new HashSet<T>(); 

     foreach (List<T> currentList in listOfLists) 
     { 
      if (currentCommon.Count == 0) 
      { 
       foreach (T item in currentList) 
       { 
        common.Add(item); 
       } 
      } 
      else 
      { 
       foreach (T item in currentList) 
       { 
        if (currentCommon.Contains(item)) 
        { 
         common.Add(item); 
        } 
       } 
      } 
      if (common.Count == 0) 
      { 
       currentCommon.Clear(); 
       break; 
      } 
      currentCommon.Clear(); // Empty currentCommon for a new iteration. 
      foreach (T item in common) /* Copy all the items contained in common to currentCommon. 
             *   currentCommon = common; 
             * does not work because thus currentCommon and common would point at the same object and 
             * the next statement: 
             *   common.Clear(); 
             * will also clear currentCommon. 
             */ 
      { 
       if (!currentCommon.Contains(item)) 
       { 
        currentCommon.Add(item); 
       } 
      } 
      common.Clear(); 
     } 

     return currentCommon; 
    } 

Answer 10

Nach der Suche der ‚net und nicht wirklich kommen mit etwas, das ich mochte (oder das funktionierte), schlief ich auf sie und kam mit dieser. Mein SearchResult ist Ihrem Option ähnlich. Es hat eine EmployeeId darin und das ist die Sache, die ich in den Listen üblich sein muss. Ich gebe alle Datensätze zurück, die eine EmployeeId in jeder Liste enthalten. Es ist nicht schick, aber es ist einfach und leicht zu verstehen, genau das, was ich mag. Für kleine Listen (mein Fall) sollte es gut funktionieren - und jeder kann es verstehen!

private List<SearchResult> GetFinalSearchResults(IEnumerable<IEnumerable<SearchResult>> lists) 
{ 
    Dictionary<int, SearchResult> oldList = new Dictionary<int, SearchResult>(); 
    Dictionary<int, SearchResult> newList = new Dictionary<int, SearchResult>(); 

    oldList = lists.First().ToDictionary(x => x.EmployeeId, x => x); 

    foreach (List<SearchResult> list in lists.Skip(1)) 
    { 
     foreach (SearchResult emp in list) 
     { 
      if (oldList.Keys.Contains(emp.EmployeeId)) 
      { 
       newList.Add(emp.EmployeeId, emp); 
      } 
     } 

     oldList = new Dictionary<int, SearchResult>(newList); 
     newList.Clear(); 
    } 

    return oldList.Values.ToList(); 
}