Linq performance: Any vs. Содержит

Question

Этот вопрос относится к this one, но не совсем тот же Я думаю,.

Дано:

class Foo 
{ 
    public string Bar { get; set; } 
} 
... 
var c1 = new List<Foo>() { ... }; 
var c2 = new List<Foo>() { ... }; 

Следующие 2 петли дают одинаковый результат:

foreach (var item in c2.Where(f => c1.Any(f1 => f1.Bar.Equals(f.Bar)))) 
    { ... } 

    foreach (var item in c2.Where(f => c1.Select(f1 => f1.Bar).Contains(f.Bar))) 
    { ... } 

ли они одинаково быстро?

Разница с the other question, является ли дополнительное заявление Select здесь, изменяет важность характера базовой коллекции.

Другими словами: делает это содержит:

foos.Contains(foo1) 

действуют на том же "вид коллекции" как этот:

foos.Select(f=>f.Bar).Contains(foo1.Bar) 

Моя возможно -naive- мысль может быть: «Как только мы отстаем от выбора Linq, все просто« Списки », поэтому оба и« Содержат »- это O (n)».

Answer 1

Эти два вопроса в основном реализуют один и тот же алгоритм. Каждый из них будет перебирать c1 для каждого элемента в c2, сравните Bar свойства двух объектов и верните их, как только будет найдена совпадение. Асимптотическая сложность обоих случаев одинакова, что означает, что они будут одинаково хорошо масштабироваться (или, в случае необходимости, одинаково плохи) по мере увеличения размера этих двух наборов. Могут быть незначительные различия между ними в накладных расходах, связанных с одним методом над другим, но разница не будет существенной, и они будут меньше и меньше по мере увеличения размера коллекций. Нет никакой реальной причины для выбора одной из двух над другой.

Существует опция, которую вы не показать, что это немного быстрее, чем любой из них. Вы можете использовать Join, чтобы найти все предметы в c1, которые также существуют в c2, не делая линейный поиск по последовательности:

var query = from first in c1 
    join second in c2 
    on first.Bar equals second.Bar 
    select first; 

Другим вариантом было бы использовать HashSet вместо List, так как это может быть гораздо более легко найти:

var set = new HashSet<string>(c1.Select(item => item.Bar)); 

var query = c2.Where(item => set.Contains(item.Bar)); 

(Это решение довольно близко к тому, что Join будет делать внутри.)

Оба из этих решений будет лот быстрее, чем любое из предлагаемых вами решений.

Answer 2

Ваш первый подход будет повторять и сравнивать один раз и возвращать результаты.

Второй запрос будет медленнее, потому что он будет итерировать и извлечь свойство Bar в коллекцию, а затем повторить и сравнить с f.Bar, чтобы создать окончательный результат.