Czy istnieje wpływ na wydajność podczas wywoływania ToList ()?

139

Czy podczas używania ToList()istnieje wpływ na wydajność, który należy wziąć pod uwagę?

Pisałem zapytanie o pobranie plików z katalogu, którym jest zapytanie:

string[] imageArray = Directory.GetFiles(directory);

Ponieważ jednak lubię z nim pracować List<>, zdecydowałem się na ...

List<string> imageList = Directory.GetFiles(directory).ToList();

Czy jest więc jakiś wpływ na wydajność, który należy wziąć pod uwagę, decydując się na taką konwersję - czy tylko w przypadku dużej liczby plików? Czy jest to pomijalna konwersja?

Cody
źródło
+1 zainteresowanych poznaniem odpowiedzi również tutaj. IMHO, chyba że aplikacja jest wydajność krytycznych, myślę, że zawsze używać List<T>opowiada się za T[], czy to sprawia, że kod jest bardziej logiczny / odczytu / utrzymaniu (o ile oczywiście konwersji została powodując zauważalne problemy z wydajnością w takim przypadku będę re- odwiedź to chyba).
Sepster
Tworzenie listy z tablicy powinno być super tanie.
leppie
2
@Sepster Podaję tylko typ danych, który jest potrzebny do wykonania pracy. Gdybym nie musiał dzwonić Addlub Removezostawiłbym to jako IEnumerable<T>(lub nawet lepiej var)
pswg
4
Myślę, że w tym przypadku lepiej zadzwonić EnumerateFileszamiast GetFiles, aby powstała tylko jedna tablica.
tukaef
3
GetFiles(directory), jak to jest obecnie zaimplementowane w .NET, prawie tak new List<string>(EnumerateFiles(directory)).ToArray(). GetFiles(directory).ToList()Tworzy więc listę, tworzy z niej tablicę, a następnie ponownie tworzy listę. Jak mówi 2kay, powinieneś wolał robić EnumerateFiles(directory).ToList()tutaj.
Joren

Odpowiedzi:

178

IEnumerable.ToList()

Tak, IEnumerable<T>.ToList()ma wpływ na wydajność, jest to operacja O (n) , chociaż prawdopodobnie będzie wymagać uwagi tylko w operacjach krytycznych dla wydajności.

ToList()Operacja użyje List(IEnumerable<T> collection)konstruktora. Ten konstruktor musi wykonać kopię tablicy (bardziej ogólnie IEnumerable<T>), w przeciwnym razie przyszłe modyfikacje oryginalnej tablicy również zmienią się na źródle, T[]co nie byłoby ogólnie pożądane.

Chciałbym powtórzyć, że będzie to miało znaczenie tylko w przypadku ogromnej listy, kopiowanie fragmentów pamięci jest dość szybką operacją do wykonania.

Poręczna wskazówka Asvs.To

Zauważysz, że w LINQ istnieje kilka metod, które zaczynają się od As(takie jak AsEnumerable()) i To(takie jak ToList()). Metody, które zaczynają się od, Towymagają konwersji, jak powyżej (tj. Mogą wpływać na wydajność), a metody rozpoczynające się od Asnie wymagają i będą wymagały tylko rzutowania lub prostej operacji.

Dodatkowe informacje na temat List<T>

Oto trochę więcej szczegółów, jak List<T>działa, jeśli jesteś zainteresowany :)

A List<T>używa również konstrukcji zwanej tablicą dynamiczną, której rozmiar należy zmienić na żądanie, to zdarzenie zmiany rozmiaru kopiuje zawartość starej tablicy do nowej tablicy. Zaczyna się więc od małych i powiększa w razie potrzeby .

To jest różnica między atrybutami Capacityi Countna List<T>. Capacityodnosi się do rozmiaru tablicy za kulisami, Countjest liczbą elementów w List<T>której jest zawsze <= Capacity. Więc kiedy element jest dodawany do listy, zwiększając go poza Capacity, rozmiar List<T>jest podwojony i tablica jest kopiowana.

Daniel Imms
źródło
2
Chciałem tylko podkreślić, że List(IEnumerable<T> collection)konstruktor sprawdza, czy parametr kolekcji ma wartość, ICollection<T>a następnie od razu tworzy nową wewnętrzną tablicę o wymaganym rozmiarze. Jeśli kolekcja parametrów nie jest ICollection<T>, konstruktor wykonuje iterację po niej i wywołuje Addkażdy element.
Justinas Simanavicius
Należy zauważyć, że funkcja ToList () może być często postrzegana jako myląco wymagająca operacja. Dzieje się tak podczas tworzenia zapytania IEnumerable <> za pośrednictwem zapytania LINQ. zapytanie linq jest konstruowane, ale nie jest wykonywane. wywołanie ToList () uruchomi zapytanie i dlatego wydaje się, że wymaga dużej ilości zasobów - ale to zapytanie jest intensywne, a nie operacja ToList () (chyba że jest to naprawdę ogromna lista)
dancer42
36

Czy istnieje wpływ na wydajność podczas wywoływania metody toList ()?

Tak oczywiście. Teoretycznie i++ma nawet wpływ na wydajność, spowalnia program o może kilka taktów.

Co robi .ToList?

Kiedy wywołujesz .ToList, kod wywołuje, Enumerable.ToList()która jest metodą rozszerzającą that return new List<TSource>(source). W odpowiednim konstruktorze, w najgorszych okolicznościach, przechodzi przez pojemnik na przedmioty i dodaje je jeden po drugim do nowego pojemnika. Więc jego zachowanie ma niewielki wpływ na wydajność. Niemożliwe jest bycie wydajnym szyjką butelki dla twojej aplikacji.

Co jest nie tak z kodem w pytaniu

Directory.GetFilesprzechodzi przez folder i natychmiast zwraca nazwy wszystkich plików do pamięci, istnieje potencjalne ryzyko, że ciąg [] będzie kosztował dużo pamięci, spowalniając wszystko.

Co wtedy należy zrobić

To zależy. Jeśli Ty (a także logika biznesowa) gwarantujesz, że ilość plików w folderze jest zawsze mała, kod jest akceptowalny. Ale nadal sugeruje się użycie wersji leniwej: Directory.EnumerateFilesw C # 4. Jest to bardziej podobne do zapytania, które nie zostanie wykonane natychmiast, możesz dodać do niego więcej zapytań, takich jak:

Directory.EnumerateFiles(myPath).Any(s => s.Contains("myfile"))

co zatrzyma przeszukiwanie ścieżki, gdy tylko zostanie znaleziony plik, którego nazwa zawiera "myfile". To oczywiście ma lepszą wydajność .GetFiles.

Cheng Chen
źródło
19

Czy istnieje wpływ na wydajność podczas wywoływania metody toList ()?

Tak jest. Użycie metody rozszerzenia Enumerable.ToList()spowoduje utworzenie nowego List<T>obiektu z IEnumerable<T>kolekcji źródłowej, co oczywiście ma wpływ na wydajność.

Jednak zrozumienie List<T>może pomóc w określeniu, czy wpływ na wydajność jest znaczący.

List<T>używa tablicy ( T[]) do przechowywania elementów listy. Tablice nie mogą być rozszerzane po ich przydzieleniu, więc List<T>użyje tablicy o zbyt dużej wielkości do przechowywania elementów listy. Gdy List<T>rozmiar przekroczy rozmiar podstawowej tablicy, należy zaalokować nową tablicę, a zawartość starej tablicy musi zostać skopiowana do nowej większej tablicy, zanim lista będzie mogła się powiększyć.

Kiedy nowy List<T>jest konstruowany z an, IEnumerable<T>istnieją dwa przypadki:

  1. Implementacja kolekcji źródłowej ICollection<T>: Następnie ICollection<T>.Countsłuży do uzyskania dokładnego rozmiaru kolekcji źródłowej, a pasująca tablica zapasowa jest przydzielana przed skopiowaniem wszystkich elementów kolekcji źródłowej do tablicy zapasowej przy użyciu ICollection<T>.CopyTo(). Ta operacja jest dość wydajna i prawdopodobnie będzie mapowana na jakąś instrukcję CPU do kopiowania bloków pamięci. Jednak z punktu widzenia wydajności nowa macierz wymaga pamięci, a do kopiowania wszystkich elementów wymagane są cykle procesora.

  2. W przeciwnym razie rozmiar kolekcji źródłowej jest nieznany, a moduł wyliczający IEnumerable<T>jest używany do dodawania każdego elementu źródłowego pojedynczo do nowego List<T>. Początkowo tablica zapasowa jest pusta i tworzona jest tablica o rozmiarze 4. Następnie, gdy ta tablica jest zbyt mała, rozmiar jest podwajany, więc tablica podstawowa rośnie w ten sposób o 4, 8, 16, 32 itd. Za każdym razem, gdy tablica zapasowa rośnie, musi zostać ponownie przydzielona i wszystkie dotychczas przechowywane elementy muszą zostać skopiowane. Ta operacja jest znacznie bardziej kosztowna w porównaniu z pierwszym przypadkiem, w którym tablica o odpowiednim rozmiarze może zostać utworzona od razu.

    Ponadto, jeśli twoja kolekcja źródłowa zawiera powiedzmy 33 elementy, lista skończy się na tablicy 64 elementów marnujących trochę pamięci.

W twoim przypadku kolekcja źródłowa jest tablicą implementowaną, ICollection<T>więc wpływ na wydajność nie jest czymś, o co powinieneś się martwić, chyba że twoja tablica źródłowa jest bardzo duża. Wywołanie ToList()po prostu skopiuje tablicę źródłową i zawinie ją w List<T>obiekt. Nawet wykonanie drugiego etui nie jest powodem do zmartwień w przypadku małych kolekcji.

Martin Liversage
źródło
5

„Czy istnieje wpływ na wydajność, który należy wziąć pod uwagę?”

Problem z twoim precyzyjnym scenariuszem polega na tym, że przede wszystkim Twoim prawdziwym zmartwieniem o wydajność będzie szybkość dysku twardego i wydajność pamięci podręcznej dysku.

Z tej perspektywy wpływ jest z pewnością nieistotny do tego stopnia, że NIE, nie trzeba go brać pod uwagę.

ALE TYLKO wtedy, gdy naprawdę potrzebujesz funkcji List<>struktury, aby być może bardziej produktywnym, albo bardziej przyjazny algorytm, albo jakąś inną zaletę. W przeciwnym razie celowo dodajesz nieznaczne uderzenie w wydajność, bez żadnego powodu. W takim przypadku oczywiście nie powinieneś tego robić! :)

jross
źródło
4

ToList()tworzy nową Listę i umieszcza na niej elementy, co oznacza, że ​​jest to związane z kosztem wykonania ToList(). W przypadku małej kolekcji nie będzie to bardzo zauważalny koszt, ale posiadanie dużej kolekcji może spowodować spadek wydajności w przypadku korzystania z ToList.

Generalnie nie powinieneś używać ToList (), chyba że praca, którą wykonujesz, nie może zostać wykonana bez konwersji kolekcji na List. Na przykład, jeśli chcesz tylko iterować po kolekcji, nie musisz wykonywać ToList

Jeśli wykonujesz zapytania względem źródła danych, na przykład bazy danych używającej LINQ to SQL, koszt wykonania ToList jest znacznie wyższy, ponieważ gdy używasz ToList z LINQ to SQL zamiast wykonywać opóźnione wykonanie, tj. Ładuj elementy w razie potrzeby (co może być korzystne w wielu scenariuszach) natychmiast ładuje elementy z bazy danych do pamięci

Haris Hasan
źródło
Haris: Czego nie jestem pewien co do oryginalnego źródła Co stanie się z oryginalnym źródłem po wywołaniu ToList ()
TalentTuner
@Saurabh GC wyczyści to
pswg
@Saurabh nic się nie stanie z oryginalnym źródłem. Elementy oryginalnego źródła będą odnosić się do nowo utworzonej listy
Haris Hasan
„jeśli chcesz tylko iterować w kolekcji, nie musisz wykonywać ToList” - więc jak powinieneś iterować?
SharpC
4

Będzie to tak (nie) wydajne, jak:

var list = new List<T>(items);

Jeśli zdemontujesz kod źródłowy konstruktora, który przyjmuje an IEnumerable<T>, zobaczysz, że zrobi kilka rzeczy:

  • Zadzwoń collection.Count, więc jeśli collectionjest IEnumerable<T>, wymusi wykonanie. Jeśli collectionjest tablicą, listą itp., To powinno być O(1).

  • Jeśli collectionimplementuje ICollection<T>, zapisze elementy w wewnętrznej tablicy przy użyciu ICollection<T>.CopyTometody. To powinno być O(n), jest ndługość kolekcji.

  • Jeśli collectionnie zaimplementuje ICollection<T>, dokona iteracji przez elementy kolekcji i doda je do wewnętrznej listy.

Tak więc, tak, będzie zużywał więcej pamięci, ponieważ musi utworzyć nową listę, aw najgorszym przypadku tak będzieO(n) , ponieważ będzie iterował przez iterację, collectionaby utworzyć kopię każdego elementu.

Oscar Mederos
źródło
3
close, 0(n)gdzie njest całkowitą sumą bajtów zajmowanych przez ciągi w oryginalnej kolekcji, a nie liczbą elementów (a dokładniej n = bajty / rozmiar słowa)
user1416420
@ user1416420 Mogę się mylić, ale dlaczego? Co jeśli jest to zbiór innego typu (np. bool, intEtc.)? Naprawdę nie musisz tworzyć kopii każdego ciągu w kolekcji. Po prostu dodajesz je do nowej listy.
Oscar Mederos
nadal nie ma znaczenia nowa alokacja pamięci i kopiowanie bajtów jest tym, co zabija tę metodę. Bool zajmie również 4 bajty w .NET. Właściwie każde odwołanie do obiektu w .NET ma co najmniej 8 bajtów, więc jest dość powolne. pierwsze 4 bajty wskazują na tablicę typów, a kolejne 4 bajty wskazują na wartość lub miejsce w pamięci, gdzie można znaleźć wartość
user1416420
3

Biorąc pod uwagę wydajność pobierania listy plików, ToList()jest znikoma. Ale tak naprawdę nie w innych scenariuszach. To naprawdę zależy od tego, gdzie go używasz.

  • Podczas wywoływania tablicy, listy lub innej kolekcji tworzysz kopię kolekcji jako plik List<T>. Tutaj wydajność zależy od wielkości listy. Powinieneś to zrobić, gdy jest to naprawdę konieczne.

    W twoim przykładzie wywołujesz to w tablicy. Iteruje po tablicy i dodaje elementy jeden po drugim do nowo utworzonej listy. Zatem wpływ na wydajność zależy od liczby plików.

  • Dzwoniąc na zasadzie IEnumerable<T>, to zmaterializować się IEnumerable<T>(zazwyczaj zapytanie).

Mohammad Dehghan
źródło
2

ToList Utworzy nową listę i skopiuje elementy z oryginalnego źródła do nowo utworzonej listy więc jedyną rzeczą jest skopiowanie elementów z oryginalnego źródła i zależy to od rozmiaru źródła

TalentTuner
źródło