18

我有2个IEnumerable<int>

IEnumerable<int> x;
IEnumerable<int> y;

确定 x 中是否存在 y 中的任何 int 的最佳方法是什么？
目前我正在使用：

return x.Intersect<int>(y).Count() > 0;

单独循环和测试每个程序会明显更快吗？

foreach (int i in x)
{
    foreach (int j in y)
    {
        if (i == j) return true;
    }
}
return false;

这些列表相对较轻，x 中不超过 50 个整数，y 中不超过 4 个，如果这在考虑中很重要的话。

4

5 回答 5

30

使用Any方法而不是Count方法是最快的：

return x.Intersect<int>(y).Any();

这假设IEnumerable<int>实现也没有实现ICollection<int>. 在这种情况下，Count（在IEnumerable<T>implements的情况下ICollection<T>）是 O(N) 操作，而Any始终是O(1) 操作。（因为它只检查单个元素）。但是， 的行为Count是一个实现细节，您不应该依赖它。

我在一篇博文中更深入地讨论了这一点，详细介绍了何时使用Count()与Any(). 总之：

  • 请使用Enumerable.Any扩展方法检查序列中是否存在元素。
  • 不要在与零的比较中使用Enumerable.Count扩展方法，因为以下在语义上是等效的：
    • sequence.Count() == 0
    • !sequence.Any()
  • 不要在与“非零”条件比较时使用Enumerable.Count扩展方法，因为以下在语义上是等效的：
    • sequence.Count != 0
    • sequence.Any()
于 2009-03-27T19:22:05.040 回答
4

编辑：下面的原始答案确实涉及复杂性。如果序列足够短，通过GetNext(), 构建HashSet等的所有调用实际上将比使用 更昂贵Intersect(y).Any()。但是，在这种情况下，无论如何，这两个电话都会非常快。

换句话说，Intersect(y).Any()随着两个序列变长，肯定可以更好地扩展，但是如果您绝对确定序列很短，那么嵌套循环解决方案会更快。

原始答案

不，Intersect()会比双循环解决方案更快 - 但正如 CasperOne 所写的那样，它会Any()更快，Count()因为它会在看到一个元素时立即退出。

假设序列长度为 N 和 M，相交将为 ，O(N + M)而双环解为O(N * M)。

HashSetIntersect从“内部”序列（这需要复杂性）构建 a O(M)，然后遍历外部序列（需要O(N)复杂性），产生集合中的任何元素。这些结果是流式传输的 - 当从 请求第一个元素时将评估内部序列Intersect()，但这仅适用于找到第一个匹配项（如果有）。如果有任何匹配，使用Any()您将“提前退出”，因此我们在计算复杂性时不需要考虑匹配的总数。

来自 LINQ 的流式传输结果 - 值得一试（以及延迟执行）。

于 2009-03-27T19:22:14.620 回答
3

Intersect没关系，但正如其他人所说，我不会要求.Count()结果。

原因是 Intersect 不会创建两个列表的交集。它创建了一个IEnumerable能够枚举该交集的对象，但实际上还没有枚举这些结果。大部分工作都被推迟到您最终迭代此枚举的时候。

问题Count在于它确实迭代了整个枚举。因此，它不仅总是计算所有结果，而且还导致计算这些结果所涉及的所有工作也运行。

相比之下，调用Any会非常快，因为您将在返回之前最多计算一个交集结果。当然，在没有匹配的情况下，它仍然需要迭代整个列表。然而，这并不比你以前更糟。事实上，它仍然更快，因为正如 Jon Skeet 所提到的，该Intersect函数使用 HashSet 来计算结果，而不是遍历所有内容。您的最佳和平均案例得到了极大的改善。

这就像这两个片段之间的区别：

int count = 0;
foreach (int i in x)
{
   foreach (int j in y)
   {
      if (i==j) count++;
   }
}
return (count > 0);

.

// this one should look familiar
foreach (int i in x)
{
    foreach (int j in y)
    {
       if (i==j) return true;
    }
}
return false;

显然，第二个平均要快得多。的性能Any()将类似于（由于 HashSet，与第二个片段不同），而与第一个片段Count()类似。

于 2009-03-27T19:24:38.763 回答
1

你最好这样做：

return x.Intersect(y).Any();

这将在找到单个匹配项后立即中止，并停止枚举集合。

于 2009-03-27T19:24:09.077 回答
0

与我的回答相比，这个问题和最后一个答案已经超过 1 年了；但是，我的发现与公认的答案不同。我发现循环比使用 Intersect.Any() 快得多。也许我的基准代码不正确？

这是我用来查找 Intersect、嵌套循环和 IndexOf 循环之间每秒迭代次数的代码。请原谅VB。;)

Dim ArrayLength As Integer = 50
Dim doesContain As Boolean = False
Dim counter As Integer = 0
Dim sw As New System.Diagnostics.Stopwatch()
Dim BigArray1 As String() = New String(ArrayLength) {}
Dim BigArray2 As String() = New String(ArrayLength) {}
Dim rand As New Random(DateTime.Now.Millisecond)
For i As Integer = 0 To ArrayLength
    BigArray1(i) = Convert.ToChar(rand.Next(0, 255)).ToString()
    BigArray2(i) = Convert.ToChar(rand.Next(0, 255)).ToString()
Next
Dim AnEnumerable1 As IEnumerable(Of String) = BigArray1
Dim AnEnumerable2 As IEnumerable(Of String) = BigArray2

counter = 0
sw.Restart()
Do
    doesContain = False
    For Each x As String In AnEnumerable1
        For Each y As String In AnEnumerable2
            If x.Equals(y) Then
                doesContain = True
                Exit For
            End If
        Next
        If doesContain Then Exit For
    Next
    counter += 1
Loop While sw.ElapsedMilliseconds < 1000
Console.WriteLine("InnerLoop iterated:  " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.")

counter = 0
sw.Restart()
Do
    doesContain = AnEnumerable1.Intersect(AnEnumerable2).Any()
    counter += 1
Loop While sw.ElapsedMilliseconds < 1000
Console.WriteLine("Intersect iterated:  " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.")

counter = 0
sw.Restart()
Do
    For Each x As String In AnEnumerable1
        If Array.IndexOf(Of String)(BigArray2, x) <> -1 Then
            Exit For
        End If
    Next
    counter += 1
Loop While sw.ElapsedMilliseconds < 1000
Console.WriteLine("IndexOf iterated:    " & counter.ToString() & " times in " & sw.ElapsedMilliseconds.ToString() & "ms.")

我的结果超过了两个 5,000,000 项数组。更高的迭代更好：

  • InnerLoop 迭代：2974553 次，1000ms。
  • 相交迭代：1168ms 内 4 次。
  • IndexOf 迭代：4194423 次，1000ms。

我的结果超过了两个 50 项数组。更高的迭代更好：

  • InnerLoop 迭代次数：375712 次，1000ms。
  • Intersect 迭代次数：1000ms 203721 次。
  • IndexOf 迭代次数：1000ms 668421 次。
于 2010-11-17T17:10:09.237 回答