查找出现在所有列表(或数组或集合)中的值

本文关键字：集合 数组 列表 查找 | 更新日期: 2023-09-27 18:13:54

考虑到以下内容:

List<List<int>> lists = new List<List<int>>();
lists.Add(new List<int>() { 1,2,3,4,5,6,7 });
lists.Add(new List<int>() { 1,2 });
lists.Add(new List<int>() { 1,2,3,4 });
lists.Add(new List<int>() { 1,2,5,6,7 });

确定哪些数字出现在所有列表中的最佳/最快方法是什么?

查找出现在所有列表(或数组或集合)中的值

您可以使用。net 3.5 .Intersect()扩展方法:-

List<int> a = new List<int>() { 1, 2, 3, 4, 5 };
List<int> b = new List<int>() { 0, 4, 8, 12 };
List<int> common = a.Intersect(b).ToList();

对于两个列表，可以使用x.Intersect(y)。

要同时处理多个，我们可以这样做:

var intersection = lists.Aggregate((x, y) => x.Intersect(y));

但是这不起作用，因为lambda的结果不是List<int>，所以它不能被反馈进去。这可能会诱使我们尝试:

var intersection = lists.Aggregate((x, y) => x.Intersect(y).ToList());

但是这使得n-1个不必要的调用ToList()，这是相对昂贵的。我们可以使用:

var intersection = lists.Aggregate(
  (IEnumerable<int> x, IEnumerable<int> y) => x.Intersect(y));

应用相同的逻辑，但是在lambda中使用显式类型时，我们可以将Intersect()的结果返回，而不会浪费时间和内存每次创建一个列表，因此给出更快的结果。

如果这个问题经常出现，我们可以通过滚动我们自己的而不是使用Linq:

来进一步(轻微)提高性能。
public static IEnumerable<T> IntersectAll<T>(this IEnumerable<IEnumerable<T>> source)
{
  using(var en = source.GetEnumerator())
  {
    if(!en.MoveNext()) return Enumerable.Empty<T>();
    var set = new HashSet<T>(en.Current);
    while(en.MoveNext())
    {
      var newSet = new HashSet<T>();
      foreach(T item in en.Current)
        if(set.Remove(item))
          newSet.Add(item);
      set = newSet;
    }
    return set;
  }
}

假设仅供内部使用。如果它可以从另一个程序集调用，它应该有错误检查，也许应该定义为只在调用代码的第一个MoveNext()上执行相交操作:

public static IEnumerable<T> IntersectAll<T>(this IEnumerable<IEnumerable<T>> source)
{
  if(source == null)
    throw new ArgumentNullException("source");
  return IntersectAllIterator(source);
}
public static IEnumerable<T> IntersectAllIterator<T>(IEnumerable<IEnumerable<T>> source)
{
  using(var en = source.GetEnumerator())
  {
    if(en.MoveNext())
    {
      var set = new HashSet<T>(en.Current);
      while(en.MoveNext())
      {
        var newSet = new HashSet<T>();
        foreach(T item in en.Current)
          if(set.Remove(item))
            newSet.Add(item);
        set = newSet;
      }
      foreach(T item in set)
        yield return item;
    }
  }
}

(在最后两个版本中，如果最终清空集合，则有可能发生短路，但只有在这种情况相对频繁时才会有回报，否则就是净损失)。

相反，如果这些都不是问题，如果我们知道我们只会想要在列表中这样做，我们可以使用Count和索引来进一步优化: 
public static IEnumerable<T> IntersectAll<T>(this List<List<T>> source)
{
  if (source.Count == 0) return Enumerable.Empty<T>();
  if (source.Count == 1) return source[0];
  var set = new HashSet<T>(source[0]);
  for(int i = 1; i != source.Count; ++i)
  {
    var newSet = new HashSet<T>();
    var list = source[i];
    for(int j = 0; j != list.Count; ++j)
    {
      T item = list[j];
      if(set.Remove(item))
        newSet.Add(item);
    }
    set = newSet;
  }
  return set;
}

进一步，如果我们知道我们总是想要一个列表的结果，我们知道我们不会改变列表，或者如果输入列表发生了变化，我们可以针对存在0或1个列表的情况进行优化(但如果我们可能不需要列表中的输出，这将花费更多):

public static List<T> IntersectAll<T>(this List<List<T>> source)
{
  if (source.Count == 0) return new List<T>(0);
  if (source.Count == 1) return source[0];
  var set = new HashSet<T>(source[0]);
  for(int i = 1; i != source.Count; ++i)
  {
    var newSet = new HashSet<T>();
    var list = source[i];
    for(int j = 0; j != list.Count; ++j)
    {
      T item = list[j];
      if(set.Remove(item))
        newSet.Add(item);
    }
    set = newSet;
  }
  return new List<T>(set);
}

同样，除了使方法不那么广泛适用之外，这在如何使用方面存在风险，因此仅适用于内部代码，您可以知道在事后不会更改输入或输出，或者这无关紧要。

Linq已经提供了Intersect，您也可以利用Aggregate: 

var result = lists.Aggregate((a, b) => a.Intersect(b).ToList());

如果您不相信Intersect方法，或者您只是想看看发生了什么，这里有一段代码应该可以做到这一点:

  // Output goes here
  List<int> output = new List<int>();
  // Make sure lists are sorted
  for (int i = 0; i < lists.Count; ++i) lists[i].Sort();
  // Maintain array of indices so we can step through all the lists in parallel
  int[] index = new int[lists.Count];
  while(index[0] < lists[0].Count)
  {
    // Search for each value in the first list
    int value = lists[0][index[0]];
    // No. lists that value appears in, we want this to equal lists.Count
    int count = 1;
    // Search all the other lists for the value
    for (int i = 1; i < lists.Count; ++i)
    {
      while (index[i] < lists[i].Count)
      {
        // Stop if we've passed the spot where value would have been
        if (lists[i][index[i]] > value) break;
        // Stop if we find value
        if (lists[i][index[i]] == value)
        {
          ++count; 
          break; 
        }
        ++index[i];
      }
      // If we reach the end of any list there can't be any more matches so end the search now
      if (index[i] >= lists[i].Count) goto done;
    }
    // Store the value if we found it in all the lists
    if (count == lists.Count) output.Add(value);
    // Skip multiple occurrances of the same value
    while (index[0] < lists[0].Count && lists[0][index[0]] == value) ++index[0];
  }
  done:
编辑:

我觉得很无聊，就把这个和Jon Hanna的版本做了一些对比。他的速度一直快，通常快50%左右。不过，如果你碰巧有预先排序的列表，我的排名也会以同样的优势胜出。此外，你可以获得进一步的20%左右与不安全的优化。我只是想和大家分享一下

您也可以使用SelectMany和Distinct:

List<int> result = lists
                   .SelectMany(x => x.Where(e => lists.All(l => l.Contains(e))))
                   .Distinct().ToList();
编辑:

List<int> result2 = lists.First().Where(e => lists.Skip(1).All(l => l.Contains(e)))
                         .ToList();
编辑2:

List<int> result3 = lists
        .Select(l => l.OrderBy(n => n).Take(lists.Min(x => x.Count()))).First()
        .TakeWhile((n, index) => lists.Select(l => l.OrderBy(x => x)).Skip(1).All(l => l.ElementAt(index) == n))
        .ToList();
相关文章：