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

Question

У меня есть 2 IEnumerable<int>

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

Что это лучший лучший способ определить, есть ли в ИНТ у присутствует в х?
В настоящее время я использую:

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 Интсом в й и 4 в у, если это имеет значение при рассмотрении.

Answer 1

Было бы быстро использовать Any method вместо Count method:

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

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

Я написал об этом более подробно in a blog post, который подробно рассказывает о том, когда следует использовать Count() против Any(). В итоге:

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

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

Это прервет как только он находит ни одного матча, а также прекратить перечисление через коллекции.

Answer 4

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() будет аналогичен первому.

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 iterated: 4194423 раз в 1000 мс.

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

• InnerLoop итерировано: 375712 раз в 1000 мс.
• Пересечение итераций: 203721 раз в 1000 мс.
• IndexOf iterated: 668421 раз в 1000ms.