Struktury danych .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Szybkość, pamięć i kiedy z nich korzystać?

.NET ma wiele skomplikowanych struktur danych. Niestety niektóre z nich są dość podobne i nie zawsze jestem pewien, kiedy użyć jednego, a kiedy innego. Większość moich książek w języku C # i Visual Basic mówi o nich do pewnego stopnia, ale tak naprawdę nigdy nie wchodzą w szczegóły.

Jaka jest różnica między Array, ArrayList, List, Hashtable, Dictionary, SortedList i SortedDictionary?

Które są policzalne (IList - czy można wykonywać pętle „foreach”)? Które używają par klucz / wartość (IDict)?

Co z śladem pamięci? Szybkość wstawiania? Szybkość pobierania?

Czy są jakieś inne struktury danych, o których warto wspomnieć?

Wciąż szukam więcej szczegółów na temat użycia pamięci i szybkości (notacja Big-O).

Z czubka mojej głowy:

• Array* - reprezentuje oldskulową tablicę pamięci - coś w rodzaju aliasu dla normalnej type[]tablicy. Potrafi wyliczyć. Nie może rosnąć automatycznie. Zakładałbym bardzo szybką prędkość wstawiania i wycofywania.

• ArrayList- automatycznie rosnąca tablica. Dodaje więcej kosztów ogólnych. Można wyliczyć., Prawdopodobnie wolniejszy niż normalny układ, ale wciąż dość szybki. Są one często używane w .NET

• List- jedna z moich ulubionych - może być używana z ogólnymi, więc możesz mieć silnie typowaną tablicę, np List<string>. Poza tym zachowuje się bardzo podobnieArrayList

• Hashtable- zwykły stary hashtable. Najgorszy przypadek od O (1) do O (n). Potrafi wyliczyć właściwości wartości i kluczy oraz wykonać pary klucz / wartość

• Dictionary - to samo co powyżej, tylko silnie wpisane za pomocą generycznych, takich jak Dictionary<string, string>

• SortedList- posortowana lista ogólna. Zwalniane przy wstawianiu, ponieważ musi dowiedzieć się, gdzie umieścić rzeczy. Może wyliczać. Prawdopodobnie to samo przy pobieraniu, ponieważ nie musi się uciekać, ale usuwanie będzie wolniejsze niż zwykła stara lista.

Zwykle używam Listi Dictionarycały czas - kiedy zaczniesz używać ich silnie napisanych za pomocą generyków, naprawdę trudno jest wrócić do standardowych nie-ogólnych.

Istnieje również wiele innych struktur danych - istnieje KeyValuePairwiele przydatnych rzeczy, SortedDictionaryktóre mogą być przydatne.

Jeśli to możliwe, użyj ogólnych. To zawiera:

• List zamiast ArrayList
• Słownik zamiast HashTable

Po pierwsze, wszystkie kolekcje w .NET implementują IEnumerable.

Po drugie, wiele kolekcji jest duplikatami, ponieważ w wersji 2.0 frameworku dodano elementy generyczne.

Tak więc, chociaż kolekcje ogólne prawdopodobnie dodają funkcje, w przeważającej części:

• Lista jest ogólną implementacją ArrayList.
• Słownik jest ogólną implementacją Hashtable

Tablice to kolekcja o stałym rozmiarze, w której można zmienić wartość przechowywaną pod danym indeksem.

SortedDictionary to IDictionary, który jest sortowany na podstawie kluczy. SortedList to IDictionary, który jest sortowany na podstawie wymaganego IComparer.

Tak więc implementacje IDictionary (te obsługujące KeyValuePairs) to: * Hashtable * Dictionary * SortedList * SortedDictionary

Kolejną kolekcją dodaną w .NET 3.5 jest zestaw Hashset. Jest to kolekcja obsługująca operacje na zestawach.

Ponadto LinkedList jest standardową implementacją listy połączonych (lista jest listą tablic dla szybszego wyszukiwania).

Oto kilka ogólnych wskazówek dla Ciebie:

• Możesz używać foreachna typach, które implementują IEnumerable. IListjest zasadniczo IEnumberablez właściwościami Counti Item(dostęp do elementów za pomocą indeksu zerowego). IDictionaryz drugiej strony oznacza, że ​​możesz uzyskać dostęp do elementów według dowolnego indeksu z haszowaniem.

• Array, ArrayListA Listwszystko realizować IList. Dictionary, SortedDictionaryi Hashtablewdrożyć IDictionary.

• Jeśli używasz platformy .NET 2.0 lub nowszej, zalecane jest użycie ogólnych odpowiedników wymienionych typów.

• Aby poznać złożoność czasu i przestrzeni różnych operacji na tych typach, należy zapoznać się z ich dokumentacją.

• Struktury danych .NET znajdują się w System.Collectionsprzestrzeni nazw. Istnieją biblioteki typów, takie jak PowerCollections, które oferują dodatkowe struktury danych.

• Aby uzyskać dokładne zrozumienie struktur danych, zapoznaj się z zasobami takimi jak CLRS .

Struktury danych .NET:

Więcej informacji na temat tego, dlaczego ArrayList i List są tak naprawdę różne

Tablice

Jak twierdzi jeden użytkownik, tablice są kolekcją „starej szkoły” (tak, tablice są uważane za kolekcję, ale nie są częścią System.Collections). Ale czym jest „stara szkoła” o tablicach w porównaniu z innymi kolekcjami, tj. Tymi, które wymieniłeś w swoim tytule (tutaj ArrayList i List (Of T))? Zacznijmy od podstaw, patrząc na tablice.

Na początek tablice w Microsoft .NET to „mechanizmy, które pozwalają traktować kilka [związanych logicznie] elementów jako jedną kolekcję” (patrz link do artykułu). Co to znaczy? Tablice przechowują poszczególne elementy (elementy) sekwencyjnie, jeden po drugim w pamięci z adresem początkowym. Korzystając z tablicy, możemy łatwo uzyskać dostęp do sekwencyjnie przechowywanych elementów zaczynających się pod tym adresem.

Poza tym i w przeciwieństwie do programowania 101 powszechnych koncepcji, tablice mogą być bardzo złożone:

Tablice mogą być jednowymiarowe, wielowymiarowe lub zniszczone (o tablicach postrzępionych warto przeczytać). Same tablice nie są dynamiczne: po zainicjowaniu tablica o rozmiarze n rezerwuje wystarczająco dużo miejsca do przechowywania n liczby obiektów. Liczba elementów w tablicy nie może rosnąć ani kurczyć się. Dim _array As Int32() = New Int32(100)rezerwuje wystarczającą ilość miejsca w bloku pamięci, aby tablica zawierała 100 obiektów typu pierwotnego Int32 (w tym przypadku tablica jest inicjowana tak, aby zawierała 0). Adres tego bloku jest zwracany do _array.

Zgodnie z artykułem specyfikacja języka wspólnego (CLS) wymaga, aby wszystkie tablice były zerowane. Tablice w .NET obsługują tablice niezerowe; jest to jednak mniej powszechne. W wyniku „powszechności” tablic zerowych Microsoft poświęcił wiele czasu na optymalizację ich wydajności ; dlatego macierze jednowymiarowe oparte na zerach (SZ) są „specjalne” - i naprawdę najlepsza implementacja tablicy (w przeciwieństwie do wielowymiarowych itp.) - ponieważ SZ mają specyficzne instrukcje języka pośredniego do manipulowania nimi.

Tablice są zawsze przekazywane przez odniesienie (jako adres pamięci) - ważny element układanki Array, którą należy znać. Podczas gdy sprawdzają granice (wyrzucą błąd), sprawdzanie granic można również wyłączyć w tablicach.

Ponownie, największą przeszkodą dla tablic jest to, że nie można ich zmieniać rozmiarów. Mają „stałą” pojemność. Przedstawiamy ArrayList i List (Of T) w naszej historii:

ArrayList - lista ogólna

ArrayList (wraz z List(Of T)- chociaż istnieją pewne krytyczne różnice tutaj wyjaśnione później) - to chyba najlepiej traktowane jako kolejnego dodatku do kolekcji (w szerokim tego słowa znaczeniu). ArrayList dziedziczy po interfejsie IList (potomek „ICollection”) interfejsu. Same ArrayLists są bardziej obszerne - wymagają większego obciążenia - niż Listy.

IListumożliwia implementacji traktowanie ArrayLists jako list o stałej wielkości (takich jak tablice); jednak oprócz dodatkowej funkcjonalności dodanej przez ArrayLists, nie ma rzeczywistych korzyści z używania ArrayLists, które mają stały rozmiar, ponieważ ArrayLists (ponad tablicami) w tym przypadku są znacznie wolniejsze.

Z mojego czytania, ArrayLists nie można postrzępić: „Używanie tablic wielowymiarowych jako elementów ... nie jest obsługiwane”. Znów kolejny gwóźdź do trumny ArrayLists. ArrayLists również nie są „wpisane” - co oznacza, że pod spodem wszystko, ArrayList jest po prostu Array dynamiczne obiektów: Object[]. Wymaga to dużej ilości boksu (niejawnego) i rozpakowania (jawnego) podczas implementacji ArrayLists, ponownie zwiększając ich obciążenie.

Nieuzasadniona myśl: myślę, że pamiętam albo czytając lub słysząc od jednego z moich profesorów, że ArrayLists są rodzajem drania koncepcyjnego, który próbuje przenieść się z Tablic do Kolekcji typu List, tj. Chociaż kiedyś był wielkim ulepszeniem Tablic, nie są już najlepszą opcją, ponieważ dokonano dalszego rozwoju kolekcji

List (Of T): What ArrayList stał się (i miał nadzieję, że będzie)

Różnica w użyciu pamięci jest na tyle znacząca, że ​​List (Of Int32) zużył 56% mniej pamięci niż ArrayList zawierający ten sam prymitywny typ (8 MB vs. 19 MB w powyższej demonstracji połączonej z dżentelmenem: ponownie, połączony tutaj ) - chociaż jest to wynik złożony z komputera 64-bitowego. Ta różnica naprawdę pokazuje dwie rzeczy: po pierwsze (1), „obiekt” typu Int32 w ramce (ArrayList) jest znacznie większy niż czysty typ pierwotny Int32 (List); po drugie (2) różnica jest wykładnicza w wyniku wewnętrznego działania 64-bitowej maszyny.

Jaka jest różnica i czym jest lista (Of T) ? MSDN definiuje List(Of T)jako „… silnie wpisaną listę obiektów, do których można uzyskać dostęp za pomocą indeksu”. Znaczenie ma tutaj bit „silnie typowany”: Lista (Of T) „rozpoznaje” typy i przechowuje obiekty jako ich typy. Tak więc an Int32jest przechowywane jako Int32a nie Objecttyp. Eliminuje to problemy spowodowane przez boksowanie i rozpakowywanie.

MSDN określa, że ​​ta różnica ma zastosowanie tylko podczas przechowywania typów pierwotnych, a nie typów referencyjnych. Zbyt duża różnica występuje naprawdę na dużą skalę: ponad 500 elementów. Co bardziej interesujące, w dokumentacji MSDN czytamy: „Korzystną dla Ciebie implementacją jest zastosowanie implementacji klasy List (Of T) zamiast klasy ArrayList ....”

Zasadniczo List (Of T) jest ArrayList, ale lepiej. Jest to „ogólny odpowiednik” ArrayList. Podobnie jak ArrayList, nie ma gwarancji, że zostanie posortowane do czasu posortowania (przejdź do rysunku). Lista (Of T) ma również kilka dodatkowych funkcji.

Współczuję temu pytaniu - również znalazłem (znajduję?) Oszałamiający wybór, więc postanowiłem naukowo sprawdzić, która struktura danych jest najszybsza (zrobiłem test przy użyciu VB, ale wyobrażam sobie, że C # będzie taki sam, ponieważ oba języki zrób to samo na poziomie CLR). Tutaj możesz zobaczyć niektóre wyniki testów porównawczych przeprowadzone przeze mnie (jest też dyskusja o tym, który typ danych najlepiej wykorzystać w jakich okolicznościach).

Są dość dobrze zapisane w inteligencji. Po prostu wpisz System.Collections. lub System.Collections.Generics (preferowane), a otrzymasz listę i krótki opis tego, co jest dostępne.

Tabele skrótów / słowniki są wydajnością O (1), co oznacza, że ​​wydajność nie jest funkcją wielkości. To ważne, aby wiedzieć.

EDYCJA: W praktyce średnia złożoność czasu dla wyszukiwań Hashtable / Dictionary <> wynosi O (1).

Kolekcje ogólne będą działać lepiej niż ich nie-ogólne odpowiedniki, zwłaszcza podczas iteracji wielu elementów. Wynika to z tego, że boksowanie i rozpakowywanie już nie występuje.

Ważna uwaga na temat Hashtable vs. Dictionary dla systematycznej inżynierii handlu wysokiej częstotliwości: Problem bezpieczeństwa wątków

Hashtable jest bezpieczny dla wielu wątków. Słownikowe statyczne elementy słownika są bezpieczne dla wątków, ale nie można zagwarantować, że są to dowolne elementy instancji.

Zatem Hashtable pozostaje „standardowym” wyborem w tym względzie.

Istnieją subtelne i niezbyt subtelne różnice między zbiorami rodzajowymi i nietypowymi. Używają jedynie różnych podstawowych struktur danych. Na przykład Hashtable gwarantuje jeden pisarz-wiele czytelników bez synchronizacji. Słownik nie.

Najpopularniejsze struktury i kolekcje danych C #

• Szyk
• ArrayList
• Lista
• Połączona lista
• Słownik
• HashSet
• Stos
• Kolejka
• SortedList

C # .NET ma wiele różnych struktur danych, na przykład jedną z najczęstszych jest tablica. Jednak C # ma wiele bardziej podstawowych struktur danych. Wybór odpowiedniej struktury danych do użycia jest częścią napisania dobrze ustrukturyzowanego i wydajnego programu.

W tym artykule omówię wbudowane struktury danych C #, w tym nowe wprowadzone w C # .NET 3.5. Należy pamiętać, że wiele z tych struktur danych dotyczy innych języków programowania.

Szyk

Prawdopodobnie najprostszą i najczęstszą strukturą danych jest tablica. Tablica AC # jest w zasadzie listą obiektów. Jego cechami charakterystycznymi jest to, że wszystkie obiekty są tego samego typu (w większości przypadków) i jest ich określona liczba. Charakter tablicy pozwala na bardzo szybki dostęp do elementów na podstawie ich pozycji na liście (znanej również jako indeks). Tablica AC # jest zdefiniowana w następujący sposób:

[object type][] myArray = new [object type][number of elements]

Kilka przykładów:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Jak widać z powyższego przykładu, tablica może być zainicjalizowana bez elementów lub z zestawu istniejących wartości. Wstawianie wartości do tablicy jest proste, o ile pasują. Operacja staje się kosztowna, gdy jest więcej elementów niż rozmiar tablicy, w którym to momencie tablica musi zostać rozwinięta. Trwa to dłużej, ponieważ wszystkie istniejące elementy muszą zostać skopiowane do nowej, większej tablicy.

ArrayList

Struktura danych C #, ArrayList, jest tablicą dynamiczną. Oznacza to, że ArrayList może zawierać dowolną liczbę obiektów i dowolnego typu. Ta struktura danych została zaprojektowana w celu uproszczenia procesów dodawania nowych elementów do tablicy. Pod maską ArrayList to tablica, której rozmiar jest podwajany za każdym razem, gdy zabraknie miejsca. Podwojenie rozmiaru tablicy wewnętrznej jest bardzo skuteczną strategią, która w długim okresie zmniejsza kopiowanie elementów. Nie dostaniemy tutaj tego dowodu. Struktura danych jest bardzo prosta w użyciu:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Minusem struktury danych ArrayList jest to, że należy przywrócić pobierane wartości z powrotem do ich pierwotnego typu:

int arrayListValue = (int)myArrayList[0]

Źródła i więcej informacji można znaleźć tutaj :

• Struktury danych C #
• Kolekcje i struktury danych
• Lista vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Collections.Generic Namespace
• Przestrzeń nazw System.Collections

Uważam, że sekcja „Wybierz kolekcję” Dokumentów Microsoft na stronie Kolekcja i struktura danych jest bardzo przydatna

Kolekcje C # i struktury danych: Wybierz kolekcję

A także następującą macierz, aby porównać niektóre inne funkcje