Определите, содержит ли IEnumerable <T> какой-либо объект другого IEnumerable <T>

Ответ 1

Лучше всего использовать Any метод вместо Count:

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

Это предполагает, что реализация IEnumerable<int> также не реализует ICollection<int>. В этом случае Count (в случае, когда IEnumerable<T> реализует ICollection<T>), является операцией O (N), а Any всегда является операцией O (1). (поскольку он проверяет только один элемент). Однако поведение Count является деталью реализации, и вы не должны полагаться на это.

Я написал об этом более подробном в сообщении в блоге, в котором подробно описывается, когда использовать Count() vs. Any(). Вкратце:

• DO используйте метод расширения Enumerable.Any для проверки наличия элементов в последовательности.
• НЕ использовать использовать метод Enumerable.Count расширения в сравнении с нулем, так как следующие семантически эквивалентны:
  • sequence.Count() == 0
  • !sequence.Any()
• НЕ используйте метод расширения Enumerable.Count в сравнении с условием "не ноль", так как следующие семантически эквивалентны:
  • sequence.Count != 0
  • sequence.Any()

Ответ 2

EDIT: первоначальный ответ ниже действительно имеет дело с точки зрения сложности. Если последовательности достаточно коротки, все вызовы через GetNext(), построив HashSet и т.д., Будут фактически более дорогими, чем использование Intersect(y).Any(). Однако в любом случае оба вызова будут действительно очень быстрыми.

Другими словами, Intersect(y).Any() определенно масштабируется лучше, поскольку две последовательности становятся длиннее, но если вы абсолютно уверены, что последовательности коротки, решение вложенного цикла будет быстрее.

Оригинальный ответ

Нет, Intersect() будет быстрее, чем двухпетлевое решение, но, как писал КасперОн, Any() будет быстрее, чем Count(), потому что он выйдет, как только он увидит элемент.

Предполагая последовательности длины N и M, Intersect будет O(N + M), тогда как двухконтурное решение O(N * M).

Intersect создает a HashSet из "внутренней" последовательности (это требует сложности O(M)), а затем циклически проходит внешнюю последовательность (которая принимает сложность O(N)), давая любой элемент, который находится в наборе. Эти результаты передаются по потоку - внутренняя последовательность будет оцениваться, когда первый элемент запрашивается из Intersect(), но это только доходит до нахождения первого совпадения (если есть). Используя Any(), вы будете иметь "раннее", если есть какие-либо совпадения, поэтому нам не нужно учитывать общее количество совпадений при разработке сложности.

Потоки результатов из скал LINQ - это хорошо, чтобы ваша голова круглая (а также отложенное исполнение).

Ответ 3

Intersect в порядке, но, как говорили другие, я бы не назвал .Count() результатом.

Причина заключается в том, что Intersect не создает пересечение двух списков. Он создает IEnumerable, который способен перечислить это пересечение, но на самом деле он не перечисляет эти результаты. Большая часть работы откладывается до тех пор, пока вы окончательно не перейдете к этому перечислению.

Проблема с Count заключается в том, что она выполняет итерацию по всей нумерации. Таким образом, он не только всегда учитывает все результаты, но и заставляет всю работу участвовать в вычислении этих результатов.

Вызов Any вместо этого будет очень быстрым путем сравнения, потому что перед возвратом вы вычислите не более одного результата пересечения. Конечно, в случае, когда нет совпадений, все равно придется перебирать весь список. Тем не менее, это не хуже, чем вы были раньше. На самом деле, это еще быстрее, потому что, как сказал Джон Скит, функция 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() была бы аналогична первой.

Ответ 4

Вам лучше сделать это:

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

Это будет отменено, как только он найдет одно совпадение, и перестанет перечисляться через коллекции.

Ответ 5

Этот вопрос и последний ответ более 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 раз в 1000 мс.
• Пересечение: 1 раз в 1168 м.
• IndexOf итерации: 4194423 раз в 1000 мс.

Мои результаты над двумя 50 массивами элементов. Более высокие итерации лучше:

• InnerLoop повторил: 375712 раз в 1000 мс.
• Пересечение повторится: 203721 раз в 1000 мс.
• IndexOf итерации: 668421 раз в 1000 мс.