LINQ Ring: Any () vs Contains () dla ogromnych kolekcji

103

Biorąc pod uwagę ogromną kolekcję obiektów, czy istnieje różnica w wydajności między poniższymi?

Kolekcja zawiera :

myCollection.Contains(myElement)

Niezliczone .

myCollection.Any(currentElement => currentElement == myElement)
SDReyes
źródło
7
Zbiór 10 000 000 int. zwycięzcą jest zawartość za 300%. ale warto wziąć pod uwagę wariancje wymienione poniżej.
SDReyes,
1
Wydaje się, że widać wyraźny kontrast między tymi dwoma: thedailywtf.com/Articles/State-of-the-UNION.aspx
David Peterson

Odpowiedzi:

143

Contains()jest metodą instancji, a jej wydajność zależy w dużej mierze od samej kolekcji. Na przykład Contains()na a Listjest O (n), podczas gdy Contains()na a HashSetjest O (1).

Any()jest metodą rozszerzającą i po prostu przejdzie przez kolekcję, stosując delegata do każdego obiektu. Dlatego ma złożoność O (n).

Any()jest jednak bardziej elastyczny, ponieważ możesz przekazać delegata. Contains()może przyjąć tylko przedmiot.

Etienne de Martel
źródło
27
Containsjest również metodą rozszerzającą przeciwko IEnumerable<T>(chociaż niektóre kolekcje mają również własne Containsmetody instancji). Jak mówisz, Anyjest bardziej elastyczny niż Containsdlatego, że możesz przekazać mu niestandardowy predykat, ale Contains może być nieco szybszy, ponieważ nie musi wykonywać wywołania delegata dla każdego elementu.
LukeH,
1
Czy Any () wykonuje operację na wszystkich obiektach w kolekcji, czy kończy się z pierwszym dopasowaniem?
Quarkly
1
Przynajmniej według źródła zatrzymuje się przy pierwszym dopasowaniu. All()działa podobnie.
Etienne de Martel
13

To zależy od kolekcji. Jeśli masz uporządkowaną kolekcję, Containsmożesz przeprowadzić inteligentne wyszukiwanie (binarne, hash, b-tree itp.), Podczas gdy z `Any () w zasadzie utkniesz z wyliczaniem, dopóki go nie znajdziesz (zakładając LINQ-to-Objects) .

Należy również zauważyć, że w przykładzie, Any()jest za pomocą ==operatora, który będzie sprawdzał referencyjnym równości, podczas gdy Containsużyje IEquatable<T>lub Equals()metoda, która może być pominięte.

tster
źródło
4
Dzięki .Any możesz łatwo porównać nieruchomości. Dzięki .Contains możesz po prostu porównać obiekty i potrzebujesz dodatkowego IEqualityComparer do porównywania właściwości.
msfanboy,
1
@msfanboy: To prawda, ale pytanie dotyczyło konkretnie wydajności i pokazywało porównanie całego obiektu. Więc nie sądzę, żeby to miało tutaj znaczenie.
tster
4

Przypuszczam, że zależałoby to od typu, myCollectionktóry dyktuje sposób Contains()realizacji. Na przykład posortowane drzewo binarne może wyszukiwać mądrzej. Może również uwzględniać hash elementu. Any()z drugiej strony wyliczy całą kolekcję, aż zostanie znaleziony pierwszy element spełniający warunek. Nie ma optymalizacji, jeśli obiekt miałby inteligentniejszą metodę wyszukiwania.

Jeff Mercado
źródło
0

Contains () jest również metodą rozszerzającą, która może działać szybko, jeśli używasz jej we właściwy sposób. Na przykład:

var result = context.Projects.Where(x => lstBizIds.Contains(x.businessId)).Select(x => x.projectId).ToList();

To da zapytanie

SELECT Id FROM Projects INNER JOIN (VALUES (1), (2), (3), (4), (5)) AS Data(Item) ON Projects.UserId = Data.Item

natomiast Any () z drugiej strony zawsze iteruje przez O (n).

Mam nadzieję, że to zadziała ....

Uwais
źródło