如何查找一个列表中的元素是否在另一个列表中？

Question

我想知道第一个列表中是否至少有一个元素可以在第二个列表中找到。

我看到两种方法可以做到。假设我们的列表为：

List<string> list1 = new[] { "A", "C", "F", "H", "I" };
List<string> list2 = new[] { "B", "D", "F", "G", "I" };

第一种方法使用循环：

bool isFound = false;
foreach (item1 in list1)
{
    if (list2.Contains(item1))
    {
        isFound = true;
        break;
    }
}

第二种方法直接使用了 Linq：

bool isFound = list1.Intersect(list2).Any();

第一个方法写起来很冗长，不太直观易读。第二个方法则简短明了，但对于大型列表性能较低。

有什么优雅的方法可以解决这个问题吗？

- Arseni Mourzenko

---

我认为第二个对于大型列表来说会更快。因为第一个是 O(list1.Count*list2.Count) 而第二个是 O(list1.Count+list2.Count)。不过第二个需要更多的内存。 - CodesInChaos

如果您真的想要像第一个示例一样使用LINQ进行精确搜索，请使用bool isFound = list1.Any(list2.Contains); - Ani

但是当然，这个变体和原始代码一样具有二次性能。 - CodesInChaos

Answer 1

第二个比第一个在处理大型列表时的性能更好。 Intersect 在检查另一个列表的元素是否属于它之前，将一个列表的元素放入哈希表中。

- mqp

---

我认为在第二种情况下，将计算两个列表的交集，然后才会执行“Any”。我错了吗？ - Arseni Mourzenko

交集是惰性计算的。我认为它首先将list2创建为一个哈希集，然后在遍历list1时返回并添加到哈希集中。 - CodesInChaos

@MainMa - 是的，你在那个问题上错了。它会对第一个集合进行哈希处理，然后使用迭代器块来遍历第二个集合。在每个点上，你只返回一个匹配项。迭代器块在返回内容之前不会完全运行。没有必要在集合中计算完整的匹配项。只有当Any()返回false时，它才会完全运行-否则它将在第一个匹配项处短路序列。 - Marc Gravell

是的，你错了。你可以将它想象成在循环中与break相同的方式工作。交集是懒惰计算的，一旦发现第一个元素存在于其中，Any()就会返回，不再检查其他元素。 - mqp

Answer 2

当原始算法的最坏情况时间复杂度为O(n*m)时，批评LINQ性能似乎有些奇怪。我认为LINQ方法会在列表上使用HashSet<T>，然后使用流迭代器块，因此性能应该是O(n+m)，即更好。

- Marc Gravell

Answer 3

我认为第二种方法对于大型列表会更快。因为第一种方法的时间复杂度是O(list1.Count*list2.Count)，而第二种方法是O(list1.Count+list2.Count)。但第二种方法需要更多的内存。

而且，linq的开销通常是手工编写代码的常数倍数。我猜第二种方法比命令式代码慢最多两倍，甚至可能不到。它使用了O(list1.Count+list2.Count)的内存，如果你在保持线性性能的同时仔细编写低内存使用的代码，则可以将其降至O(Min(list1,list2))。

这段代码在大型列表上应该相对快速：

bool isFound = false;
HashSet<string> set2=new HashSet<string>(list2);
foreach (item1 in list1)
{
    if (set2.Contains(item1))
    {
        isFound = true;
        break;
    }
}

您可以通过将较小的列表转换为哈希集而不是始终使用list2来进一步优化此代码。

- CodesInChaos

Answer 4

接受的答案很好，但是它不能与Linq-to-sql一起使用，因为没有Intersect的映射。在这种情况下，您应该使用：

bool isFound = table.Any(row => list2.Contains(row.FieldWithValue));

这将被编译为WHERE EXISTS。

- Marko Juvančič

Answer 5

这是另一种方法，用来判断一个列表的元素是否存在于另一个列表中。

bool present = List1.Any(t => List2.Any(y => y == t));

- user11961350