使用IEnumerable.Intersect()交叉多个列表

Question

我有一个列表列表,我想找到这样的交集:

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 };

有没有办法用IEnumerable.Intersect()做到这一点？

编辑:我应该更清楚这一点:我真的有一个列表列表,我不知道会有多少列表,上面的三个列表只是一个例子,我所拥有的实际上是一个 IEnumerable<IEnumerable<SomeClass>>

解

谢谢你的所有好评.事实证明,解决这个问题有四种选择:List +聚合(@Marcel Gosselin),List + foreach(@JaredPar,@ Gabe Moothart),HashSet +聚合(@jesperll)和HashSet + foreach(@Tony the Pony).我对这些解决方案进行了一些性能测试(不同数量的列表,每个列表中的元素数量和随机数最大值.

事实证明,对于大多数情况,HashSet比List更好(除了大型列表和小的随机数大小,因为我猜HashSet的性质.)我找不到foreach方法和聚合之间的任何真正区别方法(foreach方法执行得稍好一些.)

对我来说,聚合方法真的很吸引人(我将其视为已接受的答案)但我不会说这是最可读的解决方案..再次感谢所有!

Answer 1

怎么样:

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

这样,它通过使用相同的HashSet进行优化,并且仍然在单个语句中.只需确保listOfLists始终包含至少一个列表.

Answer 2

你确实可以使用Intersect两次.但是,我相信这会更有效:

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

小套装当然不是问题,但如果你有很多大套装,它可能很重要.

基本上Enumerable.Intersect需要在每次调用时创建一个集合 - 如果你知道你将要做更多的集合操作,那么你可以保持这个集合.

与以往一样,密切注意性能与可读性 - Intersect两次调用的方法链接非常有吸引力.

编辑:对于更新的问题:

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

或者如果你知道它不会是空的,那么Skip会相对便宜:

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

Answer 3

尝试这个,它的工作原理,但我真的想摆脱聚合中的.ToList().

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

更新:

在@pomber发表评论之后,可以摆脱调用ToList()内部Aggregate并将其移出外部仅执行一次.我没有测试性能是否比以前的代码更快.所需的更改是Aggregate在最后一行指定方法的泛型类型参数,如下所示:

var intersection = listOfLists.Aggregate<IEnumerable<int>>(
   (previousList, nextList) => previousList.Intersect(nextList)
   ).ToList();

Answer 4

您可以执行以下操作

var result = list1.Intersect(list2).Intersect(list3).ToList();

Answer 5

这是我的解决方案版本，带有我称为 IntersectMany 的扩展方法。

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;
    }
}

所以用法是这样的：

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