Udostępnij za pośrednictwem

Kolekcje i struktury danych

Podobne dane mogą być często obsługiwane wydajniej podczas przechowywania i manipulowania nimi jako kolekcji. Możesz użyć klasy System.Array lub klas w przestrzeniach nazw System.Collections, System.Collections.Generic, System.Collections.Concurrent i System.Collections.Immutable do dodawania, usuwania i modyfikowania pojedynczych elementów lub całego zakresu elementów w kolekcji.

Istnieją dwa główne typy kolekcji; kolekcje ogólne i kolekcje inne niż ogólne. Kolekcje ogólne są bezpieczne w czasie kompilacji. W związku z tym kolekcje ogólne zwykle oferują lepszą wydajność. Kolekcje ogólne akceptują parametr typu podczas ich konstruowania. Nie wymagają rzutowania do i z Object typu podczas dodawania lub usuwania elementów z kolekcji. Ponadto większość kolekcji ogólnych jest obsługiwana w aplikacjach ze Sklepu Windows. Kolekcje niegeneryczne przechowują elementy jako Object, wymagają rzutowania i większość z nich nie jest obsługiwana w przypadku tworzenia aplikacji Sklepu Windows. Jednak w starszym kodzie mogą być widoczne kolekcje niemające ogólnego charakteru.

W .NET Framework 4 i nowszych wersjach kolekcje w przestrzeni nazw System.Collections.Concurrent zapewniają wydajne, bezpieczne dla wątków operacje do uzyskiwania dostępu do elementów kolekcji z różnych wątków. Niezmienne klasy kolekcji w System.Collections.Immutable przestrzeni nazw (pakiet NuGet) są z natury bezpieczne wątkowo, ponieważ operacje są wykonywane na kopii oryginalnej kolekcji, a oryginalna kolekcja nie może być modyfikowana.

Typowe funkcje kolekcji

Wszystkie kolekcje zapewniają metody dodawania, usuwania lub znajdowania elementów w kolekcji. Ponadto wszystkie kolekcje bezpośrednio lub pośrednio implementujące ICollection interfejs lub ICollection<T> interfejs współużytkują następujące funkcje:

Ponadto wiele klas kolekcji zawiera następujące funkcje:

  • Właściwości pojemności i liczby

    Pojemność kolekcji to liczba elementów, które może zawierać. Liczba kolekcji jest liczbą elementów, które faktycznie zawiera. Niektóre kolekcje ukrywają pojemność, liczbę lub oba te elementy.

    Większość kolekcji automatycznie rozszerza pojemność po osiągnięciu bieżącej pojemności. Pamięć jest ponownie przydzielana, a elementy są kopiowane ze starej kolekcji do nowej. Ten projekt zmniejsza kod wymagany do korzystania z kolekcji. Jednak wydajność kolekcji może mieć negatywny wpływ. Na przykład, dla elementu List<T>, jeśli wartość Count jest mniejsza niż Capacity, dodanie elementu jest operacją O(1). Jeśli pojemność musi zostać zwiększona, aby uwzględnić nowy element, dodanie elementu stanie się operacją O(n), gdzie n to Count. Najlepszym sposobem uniknięcia słabej wydajności spowodowanej przez wiele realokacji jest ustawienie początkowej pojemności na szacowany rozmiar kolekcji.

    BitArray to szczególny przypadek; jego pojemność jest taka sama jak jego długość, co jest takie samo jak jego liczebność.

  • Spójna dolna granica

    Dolna granica kolekcji jest indeksem pierwszego elementu. Wszystkie indeksowane kolekcje w System.Collections namespace'ach mają indeks początkowy równy zero, co oznacza, że są indeksowane od zera. Array domyślnie ma dolną granicę zera, ale można zdefiniować inną dolną granicę podczas tworzenia wystąpienia klasy Array przy użyciu polecenia Array.CreateInstance.

  • Synchronizacja dostępu z wielu wątków (tylko dla System.Collections klas).

    Nieogólne typy kolekcji w przestrzeni nazw System.Collections zapewniają pewne bezpieczeństwo wątków dzięki synchronizacji; zazwyczaj udostępniane są za pośrednictwem członków SyncRoot i IsSynchronized. Te kolekcje nie są domyślnie bezpieczne dla wątków. Jeśli potrzebujesz skalowalnego i wydajnego wielowątkowego dostępu do kolekcji, użyj jednej z klas w System.Collections.Concurrent przestrzeni nazw lub rozważ użycie niezmiennej kolekcji. Aby uzyskać więcej informacji, zobacz Thread-Safe Kolekcje.

Wybieranie kolekcji

Ogólnie rzecz biorąc, należy używać kolekcji ogólnych. W poniższej tabeli opisano niektóre typowe scenariusze kolekcji i klasy kolekcji, których można użyć w tych scenariuszach. Jeśli dopiero zaczynasz korzystać z kolekcji ogólnych, poniższa tabela pomoże Ci wybrać kolekcję ogólną, która najlepiej sprawdza się w twoim zadaniu:

Chcę... Opcje kolekcji ogólnej Opcje kolekcji nieogólne Opcje kolekcji, które są bezpieczne dla wątków lub niezmienne
Przechowywanie elementów jako par klucz/wartość w celu szybkiego wyszukiwania według klucza Dictionary<TKey,TValue> Hashtable

(Kolekcja par klucz/wartość, które są zorganizowane na podstawie kodu skrótu klucza).		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Uzyskiwanie dostępu do elementów według indeksu List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Stosowanie zasady pierwsze weszło, pierwsze wyszło (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Korzystanie z danych last-in-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Sekwencyjnie uzyskiwanie dostępu do elementów LinkedList<T> Brak rekomendacji Brak rekomendacji
Otrzymywanie powiadomień, gdy elementy zostaną usunięte lub dodane do kolekcji. (implementuje INotifyPropertyChanged i INotifyCollectionChanged) ObservableCollection<T> Brak rekomendacji Brak rekomendacji
Posortowana kolekcja SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Zestaw funkcji matematycznych HashSet<T>

SortedSet<T>		 Brak rekomendacji ImmutableHashSet<T>

ImmutableSortedSet<T>

Algorytmiczna złożoność kolekcji

Podczas wybierania klasy kolekcji warto rozważyć potencjalne kompromisy w wydajności. Skorzystaj z poniższej tabeli, aby dowiedzieć się, jak różne typy kolekcji modyfikowalne porównują się ze złożonością algorytmiczną do odpowiadających im niezmiennych odpowiedników. Często niezmienne typy kolekcji są mniej wydajne, ale zapewniają niezmienność — co często jest prawidłową korzyścią porównawczą.

Modyfikowalny Amortyzowane Najgorszy przypadek Niezmienialny Złożoność
Stack<T>.Push O(1) O(n) ImmutableStack<T>.Push O(1)
Queue<T>.Enqueue O(1) O(n) ImmutableQueue<T>.Enqueue O(1)
List<T>.Add O(1) O(n) ImmutableList<T>.Add O(log n)
List<T>.Item[Int32] O(1) O(1) ImmutableList<T>.Item[Int32] O(log n)
List<T>.Enumerator O(n) O(n) ImmutableList<T>.Enumerator O(n)
HashSet<T>.AddWyszukaj O(1) O(n) ImmutableHashSet<T>.Add O(log n)
SortedSet<T>.Add O(log n) O(n) ImmutableSortedSet<T>.Add O(log n)
Dictionary<T>.Add O(1) O(n) ImmutableDictionary<T>.Add O(log n)
Dictionary<T> Wyszukiwanie O(1) O(1) — lub ściśle O(n) ImmutableDictionary<T> Wyszukiwanie O(log n)
SortedDictionary<T>.Add O(log n) O(n dziennik n) ImmutableSortedDictionary<T>.Add O(log n)

Element List<T> może być skutecznie wyliczany przy użyciu for pętli lub foreach pętli. Element ImmutableList<T>, jednak wykonuje słabe zadanie wewnątrz for pętli ze względu na czas O(log n) dla indeksatora. Wyliczanie ImmutableList<T> przy użyciu pętli foreach jest wydajne, ponieważ ImmutableList<T> używa drzewa binarnego do przechowywania danych zamiast tablicy, którą wykorzystuje List<T>. Tablicę można szybko indeksować, podczas gdy drzewo binarne musi być przechodzine w dół do momentu znalezienia węzła z żądanym indeksem.

Dodatkowo, SortedSet<T> ma taką samą złożoność jak ImmutableSortedSet<T>, ponieważ oba używają drzew binarnych. Znacząca różnica polega na tym, że ImmutableSortedSet<T> używa niezmiennego drzewa binarnego. Ponieważ ImmutableSortedSet<T> oferuje również klasę, która umożliwia mutację System.Collections.Immutable.ImmutableSortedSet<T>.Builder , można mieć zarówno niezmienność, jak i wydajność.

Nazwa Opis
Wybieranie klasy kolekcji Opisuje różne kolekcje i pomaga wybrać jedną z nich dla danego scenariusza.
Często używane typy kolekcji Opisuje powszechnie używane typy kolekcji ogólnych i nieogólne, takie jak System.Array, System.Collections.Generic.List<T>i System.Collections.Generic.Dictionary<TKey,TValue>.
Kiedy należy używać kolekcji ogólnych Omówienie użycia typów kolekcji ogólnych.
Porównania i sortowanie w kolekcjach Omawia użycie porównań równości i sortowania w kolekcjach.
Sortowane typy kolekcji Opisuje wydajność i właściwości posortowanych kolekcji.
Typy kolekcji tabel skrótów i słowników Opisuje funkcje ogólnych i niegenerycznych typów słowników opartych na skrótach.
Thread-Safe kolekcje Opisuje typy kolekcji, takie jak System.Collections.Concurrent.BlockingCollection<T> i System.Collections.Concurrent.ConcurrentBag<T> , które obsługują bezpieczny i wydajny współbieżny dostęp z wielu wątków.
System.Collections.Immutable Wprowadza niezmienne kolekcje i udostępnia linki do typów kolekcji.

Źródło