Kolekcje i struktury danych

  • Artykuł

Podobne dane mogą być często obsługiwane wydajniej podczas przechowywania i manipulowania nimi jako kolekcji. Możesz użyć System.Array klasy lub klas w System.Collectionsprzestrzeniach nazw , System.Collections.Generic, System.Collections.Concurrenti System.Collections.Immutable do dodawania, usuwania i modyfikowania pojedynczych elementów lub 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 pod typem w czasie kompilacji. Z tego powodu kolekcje ogólne zwykle oferują lepszą wydajność. Kolekcje ogólne akceptują parametr typu podczas ich konstruowania i 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 Store. Kolekcje inne niż ogólne przechowują elementy jako Object, wymagają rzutu, a większość nie jest obsługiwana w przypadku tworzenia aplikacji ze sklepu Windows Store. Jednak w starszym kodzie mogą być widoczne kolekcje inne niż ogólne.

Począwszy od .NET Framework 4, kolekcje w System.Collections.Concurrent przestrzeni nazw zapewniają wydajne operacje bezpieczne wątkowo na potrzeby uzyskiwania dostępu do elementów kolekcji z wielu 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 i nie można zmodyfikować oryginalnej kolekcji.

Typowe funkcje kolekcji

Wszystkie kolekcje udostępniają metody dodawania, usuwania lub znajdowania elementów w kolekcji. Ponadto wszystkie kolekcje, które bezpośrednio lub pośrednio implementują 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 obie te kolekcje.

    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. Zmniejsza to kod wymagany do korzystania z kolekcji; jednak wpływ na wydajność kolekcji może mieć negatywny wpływ. Na przykład w przypadku List<T>elementu , jeśli Count wartość jest mniejsza niż Capacity, dodanie elementu jest operacją O(1). Jeśli pojemność musi zostać zwiększona, aby pomieścić nowy element, dodanie elementu staje się operacją O(n), gdzie n to Count. Najlepszym sposobem uniknięcia niskiej wydajności spowodowanej przez wiele lokalizacji rzeczywistych jest ustawienie początkowej pojemności na szacowany rozmiar kolekcji.

    Jest BitArray to szczególny przypadek; jego pojemność jest taka sama jak jego długość, która jest taka sama jak jego liczba.

  • Spójna dolna granica

    Dolna granica kolekcji jest indeksem pierwszego elementu. Wszystkie indeksowane kolekcje w System.Collections przestrzeniach nazw mają dolną granicę zera, co oznacza, że są indeksowane 0. 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 (System.Collections tylko klasy).

    Typy kolekcji innych niż ogólne w System.Collections przestrzeni nazw zapewniają pewne bezpieczeństwo wątków z synchronizacją; zazwyczaj są one widoczne za pośrednictwem elementów SyncRoot i IsSynchronized . Te kolekcje nie są domyślnie bezpieczne wątkowo. Jeśli potrzebujesz skalowalnego i wydajnego dostępu wielowątkowego 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 Kolekcje wątków Sejf.

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 jesteś nowym użytkownikem kolekcji ogólnych, ta tabela pomoże Ci wybrać kolekcję ogólną, która działa najlepiej dla danego zadania.

Chcę... Opcje kolekcji ogólnej Opcje kolekcji nieogólne Opcje kolekcji bezpieczne wątkowo 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
Używanie elementów pierwszy na pierwszym wyjęcie (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 są usuwane lub dodawane 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 Najgorsza sprawa 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>.AddWyszukiwania 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> Wyszukiwania O(1) O(1) – lub ściśle O(n) ImmutableDictionary<T> Wyszukiwania 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. Jednak ImmutableList<T>, 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 foreach pętli jest wydajne, ponieważ ImmutableList<T> używa drzewa binarnego do przechowywania danych zamiast prostej tablicy, takiej jak List<T> użycie. Tablica może być bardzo szybko indeksowana, natomiast drzewo binarne musi przechodzić w dół do momentu znalezienia węzła z żądanym indeksem.

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

Tytuł 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 niegenerycznych, takich 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 Omówienie użycia porównań równości i porównań sortowania w kolekcjach.
Sortowane typy kolekcji Opisuje posortowaną wydajność i charakterystykę kolekcji
Typy kolekcji tablic wartości funkcji mieszającej i słowników Opisuje funkcje ogólnych i niegenerycznych typów słowników opartych na skrótach.
Kolekcje Sejf wątków 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.Niezmienny Wprowadza niezmienne kolekcje i udostępnia linki do typów kolekcji.

Tematy pomocy

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable