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

Question

у меня 2 IEnumerable<int>

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

Каков наилучший способ определить, присутствует ли любое число в y в x?
В настоящее время я использую:

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

Было бы значительно быстрее проходить и проверять каждый по отдельности?

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

Списки относительно легкие, не более 50 дюймов по x и 4 по y, если это имеет значение при рассмотрении.

Answer 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() против Any(). В итоге:

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

Answer 2

РЕДАКТИРОВАТЬ: оригинальный ответ ниже действительно имеет дело с точки зрения сложности. Если последовательности достаточно короткие, все вызовы через GetNext(), построение HashSet и т. Д. Будут на самом деле дороже, чем использование Intersect(y).Any(). Однако в этом случае оба вызова будут очень быстрыми.

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

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

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

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

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

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

Answer 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;

Очевидно, что 2-й намного быстрее в среднем. Производительность Any() будет аналогичной (не то же самое, что благодаря HashSet) для второго фрагмента, тогда как Count() будет аналогична первому.

Answer 4

Тебе лучше это сделать:

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

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

Answer 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 мс.
• Пересечение повторяется: 4 раза за 1168 мс.
• IndexOf повторяется: 4194423 раза за 1000 мс.

Мои результаты по двум массивам из 50 предметов. Чем выше итерации, тем лучше:

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