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

Я имею 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 ints в x и 4 в y, если это имеет значение в соображении.

16
задан Cœur 9 July 2019 в 15:43
поделиться

4 ответа

Это было бы самым быстрым для использования 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(). Таким образом:

  • ДЕЙСТВИТЕЛЬНО использовать Enumerable.Any дополнительный метод для проверки на существование элементов в последовательности.
  • НЕ использовать Enumerable.Count дополнительный метод в сравнениях с нулем, как следующее семантически эквивалентны:
    • sequence.Count() == 0
    • !sequence.Any()
  • НЕ используйте Enumerable.Count дополнительный метод в сравнениях с “не нулевым” условием, как следующее семантически эквивалентны:
    • sequence.Count != 0
    • sequence.Any()
27
ответ дан 30 November 2019 в 16:58
поделиться

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

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

Исходный ответ

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

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

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

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

4
ответ дан 30 November 2019 в 16:58
поделиться

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

Причина, это Пересекается, не создает пересечение двух списков. Это создает 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;

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

3
ответ дан 30 November 2019 в 16:58
поделиться

Вы лучше из выполнения этого:

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

Это прервется, как только это находит единственное соответствие, и прекратите перечислять через наборы.

1
ответ дан 30 November 2019 в 16:58
поделиться
Другие вопросы по тегам:

Похожие вопросы: