Schnittmenge mehrerer Listen mit IEnumerable.Intersect ()

83

Ich habe eine Liste von Listen, für die ich den Schnittpunkt finden möchte:

var list1 = new List<int>() { 1, 2, 3 };
var list2 = new List<int>() { 2, 3, 4 };
var list3 = new List<int>() { 3, 4, 5 };
var listOfLists = new List<List<int>>() { list1, list2, list3 };

// expected intersection is List<int>() { 3 };

Gibt es eine Möglichkeit, dies mit IEnumerable.Intersect () zu tun?

EDIT: Ich hätte klarer sein sollen: Ich habe wirklich eine Liste von Listen, ich weiß nicht, wie viele es geben wird, die drei Listen oben waren nur ein Beispiel, was ich habe, ist tatsächlich eine IEnumerable<IEnumerable<SomeClass>>

LÖSUNG

Vielen Dank für alle tollen Antworten. Es stellte sich heraus, dass es vier Möglichkeiten gab, dies zu lösen: Liste + Aggregat (@Marcel Gosselin), Liste + foreach (@JaredPar, @Gabe Moothart), HashSet + Aggregat (@jesperll) und HashSet + foreach (@Tony the Pony). Ich habe einige Leistungstests für diese Lösungen durchgeführt (unterschiedliche Anzahl von Listen , Anzahl von Elementen in jeder Liste und maximale Größe für Zufallszahlen .

Es stellt sich heraus, dass das HashSet in den meisten Situationen eine bessere Leistung als die Liste aufweist (außer bei großen Listen und kleinen Zufallszahlen, da es sich vermutlich um HashSet handelt). Ich konnte keinen wirklichen Unterschied zwischen der foreach-Methode und dem Aggregat feststellen Methode (die foreach-Methode ist etwas besser.)

Für mich ist die Aggregatmethode wirklich ansprechend (und ich gehe davon als akzeptierte Antwort aus), aber ich würde nicht sagen, dass es die am besten lesbare Lösung ist. Nochmals vielen Dank an alle!

Oskar
quelle

Antworten:

72

Wie wäre es mit:

var intersection = listOfLists
    .Skip(1)
    .Aggregate(
        new HashSet<T>(listOfLists.First()),
        (h, e) => { h.IntersectWith(e); return h; }
    );

Auf diese Weise wird es optimiert, indem überall und immer noch dasselbe HashSet in einer einzigen Anweisung verwendet wird. Stellen Sie einfach sicher, dass die listOfLists immer mindestens eine Liste enthält.

Jesper Larsen-Ledet
quelle
1
Wow, auf keinen Fall hätte ich mir über diese Lösung Gedanken machen können. Sobald Sie die Lösung gefunden haben, scheint es offensichtlich ..... hummmm, nein, ich werde einen Kommentar hinterlassen, nur um sicherzugehen, dass meine Mitarbeiter nicht glauben, dass ich zu viel Gras nehme :)
Samuel
Funktionsparadigma gewinnt)
Anatol
Warum wird der Skip benötigt? Fragen, weil ich nicht weiß
Issa Fram
Überspringen ist vorhanden, da das erste Element für das anfängliche Auffüllen des Hashsets verwendet wird. Sie müssen dies tun, da es sich sonst um eine Reihe von Kreuzungen mit einer leeren Menge handelt.
SirPentor
Ich verstehe die Lösung. Ich denke e steht für Enumerator? Kann ich auch fragen, wofür h steht? Ich denke h steht für HashSet?
Quan
62

Sie können in der Tat Intersectzweimal verwenden. Ich glaube jedoch, dass dies effizienter sein wird:

HashSet<int> hashSet = new HashSet<int>(list1);
hashSet.IntersectWith(list2);
hashSet.IntersectWith(list3);
List<int> intersection = hashSet.ToList();

Natürlich kein Problem mit kleinen Sätzen, aber wenn Sie viele große Sätze haben, kann dies von Bedeutung sein.

Grundsätzlich Enumerable.Intersectmuss bei jedem Aufruf ein Satz erstellt werden. Wenn Sie wissen, dass Sie mehr Satzvorgänge ausführen werden, können Sie diesen Satz genauso gut beibehalten.

Behalten Sie nach wie vor die Leistung im Vergleich zur Lesbarkeit im Auge - die Verkettung von Methoden zum Intersectzweimaligen Aufrufen ist sehr ansprechend.

EDIT: Für die aktualisierte Frage:

public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists)
{
    HashSet<T> hashSet = null;
    foreach (var list in lists)
    {
        if (hashSet == null)
        {
            hashSet = new HashSet<T>(list);
        }
        else
        {
            hashSet.IntersectWith(list);
        }
    }
    return hashSet == null ? new List<T>() : hashSet.ToList();
}

Oder wenn Sie wissen, dass es nicht leer ist und dass Skip relativ billig ist:

public List<T> IntersectAll<T>(IEnumerable<IEnumerable<T>> lists)
{
    HashSet<T> hashSet = new HashSet<T>(lists.First());
    foreach (var list in lists.Skip(1))
    {
        hashSet.IntersectWith(list);
    }
    return hashSet.ToList();
}
Jon Skeet
quelle
1
@Skeet "Tony das Pony"?
Gabe Moothart
Ja, das foreach macht Sinn. Gibt es einen Leistungsunterschied im Vergleich zur Aggregatmethode in Marcel's Antwort?
Oskar
@Oskar: Ja, meine Antwort verwendet ein einzelnes Hashset, anstatt jedes Mal ein neues zu erstellen. Sie können jedoch weiterhin Aggregat mit einem Satz verwenden ... wird bearbeitet.
Jon Skeet
Ick ... habe gerade versucht, eine Aggregatlösung zu erarbeiten, und es ist schwierig, weil HashSet.IntersectWith null zurückgibt :(
Jon Skeet
1
Hallo. Eine Frage zu Ihrer IntersectAll()Methode (die eine Handvoll ist): Gibt es eine einfache Möglichkeit, einen Selektor als Parameter hinzuzufügen, Werte (z. B. :) zu vergleichen Func<TResult, TKey> selectorund dennoch zu verwenden InsertectWith()?
Tigrou
28

Versuchen Sie dies, es funktioniert, aber ich möchte die .ToList () im Aggregat wirklich loswerden.

var list1 = new List<int>() { 1, 2, 3 };
var list2 = new List<int>() { 2, 3, 4 };
var list3 = new List<int>() { 3, 4, 5 };
var listOfLists = new List<List<int>>() { list1, list2, list3 };
var intersection = listOfLists.Aggregate((previousList, nextList) => previousList.Intersect(nextList).ToList());

Aktualisieren:

Nach dem Kommentar von @pomber ist es möglich, das ToList()Innere des AggregateAufrufs zu entfernen und nach außen zu verschieben, um ihn nur einmal auszuführen. Ich habe nicht auf Leistung getestet, ob der vorherige Code schneller als der neue ist. Die erforderliche Änderung besteht darin, den generischen Typparameter der AggregateMethode in der letzten Zeile wie folgt anzugeben :

var intersection = listOfLists.Aggregate<IEnumerable<int>>(
   (previousList, nextList) => previousList.Intersect(nextList)
   ).ToList();
Marcel Gosselin
quelle
Danke, ich habe das gerade ausprobiert und es funktioniert! Ich habe Aggregate () noch nie benutzt, aber ich denke, es war so etwas, nach dem ich gesucht habe.
Oskar
Wie ich als Kommentar zu Tonys Antwort angegeben habe, glaube ich, dass seine Lösung eine bessere Leistung bringen wird.
Marcel Gosselin
3
Sie können die .ToList () im Aggregat entfernen, wenn Sie Aggregate <IEnumerable <int >>
pomber
@pomber, ich kann nicht glauben, dass dein Kommentar 3 Jahre ohne Gegenstimme vergangen ist. Nun, heute ist dein Tag, mein Freund.
Sean
5

Dies ist meine Version der Lösung mit einer Erweiterungsmethode, die ich IntersectMany genannt habe.

public static IEnumerable<TResult> IntersectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
{
    using (var enumerator = source.GetEnumerator())
    {
        if(!enumerator.MoveNext())
            return new TResult[0];

        var ret = selector(enumerator.Current);

        while (enumerator.MoveNext())
        {
            ret = ret.Intersect(selector(enumerator.Current));
        }

        return ret;
    }
}

Die Verwendung wäre also ungefähr so:

var intersection = (new[] { list1, list2, list3 }).IntersectMany(l => l).ToList();
Gigi
quelle
4

Sie könnten Folgendes tun

var result = list1.Intersect(list2).Intersect(list3).ToList();
JaredPar
quelle
1
Danke, aber ich habe wirklich eine Liste von Listen, nicht drei separate Listen. Ich brauche etwas, das unabhängig davon funktioniert, wie viele Listen in listOfLists vorhanden sind.
Oskar
4
@Oskar Sie könnten das leicht in einer Schleife laufen lassen
Gabe Moothart
2

Dies ist meine einzeilige Lösung für List of List (ListOfLists) ohne Schnittfunktion:

var intersect = ListOfLists.SelectMany(x=>x).Distinct().Where(w=> ListOfLists.TrueForAll(t=>t.Contains(w))).ToList()

Dies sollte für .net 4 (oder höher) funktionieren.

Sergey
quelle
Vielen Dank!!!
Vương Hữu Thiện
0

Nachdem ich im Internet gesucht und nicht wirklich etwas gefunden hatte, das mir gefiel (oder das funktionierte), schlief ich darauf und fand es. Meins verwendet eine Klasse ( SearchResult), die eine enthält EmployeeId, und das ist das, was ich brauche, um über Listen hinweg gemeinsam zu sein. Ich gebe alle Datensätze zurück, die EmployeeIdin jeder Liste eine enthalten. Es ist nichts Besonderes, 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();
}

Hier ist ein Beispiel, das nur eine Liste von Ints verwendet, keine Klasse (dies war meine ursprüngliche Implementierung).

static List<int> FindCommon(List<List<int>> items)
{
    Dictionary<int, int> oldList = new Dictionary<int, int>();
    Dictionary<int, int> newList = new Dictionary<int, int>();

    oldList = items[0].ToDictionary(x => x, x => x);

    foreach (List<int> list in items.Skip(1))
    {
        foreach (int i in list)
        {
            if (oldList.Keys.Contains(i))
            {
                newList.Add(i, i);
            }
        }

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

    return oldList.Values.ToList();
}
Birdus
quelle
-1

Dies ist eine einfache Lösung, wenn Ihre Listen alle klein sind. Wenn Sie größere Listen haben, ist diese nicht so leistungsfähig wie das Hash-Set:

public static IEnumerable<T> IntersectMany<T>(this IEnumerable<IEnumerable<T>> input)
{
    if (!input.Any())
        return new List<T>();

    return input.Aggregate(Enumerable.Intersect);
}
Harakim
quelle