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

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

第一个是写的很长,而不是非常直接/易于阅读.第二个是短而清晰的,但表现很低,特别是在大型名单上.

这可能是一种优雅的方式吗？

Answer 1

第二个在大型列表上的性能优于第一个. Intersect在检查其他列表的成员资格元素之前,将一个列表的元素放入哈希表中.

Answer 2

当原始明显(最坏情况)O(n*m)时,批判LINQ的性能似乎很奇怪; 我希望HashSet<T>在列表中使用LINQ方法,然后使用流式迭代器块 - 所以性能应该是O(n + m) - 即更好.

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来进一步优化此代码.