Struktury danych. NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - szybkość, pamięć i kiedy używać każdego z nich?

Jeśli to możliwe, użyj leków generycznych. Obejmuje to:

• Lista zamiast ArrayList
• Słownik zamiast HashTable

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

Po drugie, wiele zbiorów jest duplikatami, ponieważ generyki zostały dodane w wersji 2.0 frameworka.

Tak więc, chociaż zbiory generyczne prawdopodobnie dodają cechy, w przeważającej części:

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

Tablice są zbiorem o stałym rozmiarze, w którym można zmienić wartość przechowywaną w danym indeks.

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

Zatem implementacje IDictionary (te wspierające KeyValuePairs) są: * Hashtable * Słownik * SortedList * SortedDictionary

Kolejną kolekcją dodaną w. NET 3.5 jest Hashset. Jest to kolekcja, która obsługuje operacje set.

Również LinkedList jest standardową linked-listą implementacja (lista jest array-list dla szybszego wyszukiwania).

Oto kilka ogólnych wskazówek dla ciebie:

• Możesz użyć foreach Na typach implementujących IEnumerable. {[2] } jest zasadniczo IEnumberable z właściwościami Count i Item (dostęp do elementów przy użyciu indeksu bazującego na 0). IDictionary z drugiej strony oznacza, że możesz uzyskać dostęp do elementów za pomocą dowolnego indeksu hashable.

• Array, ArrayList i List wszystkie implementują IList. Dictionary, SortedDictionary, i Hashtable wdrożyć IDictionary.

• Jeśli używasz. NET 2.0 lub wyższej wersji, zaleca się, aby używasz generycznych odpowiedników wymienionych typów.

• W przypadku złożoności czasowej i przestrzennej różnych operacji na tego typu należy zapoznać się z ich dokumentacją.

• Struktury danych. NET są w przestrzeni nazw System.Collections. Istnieją biblioteki typów, takie jak PowerCollections, które oferują dodatkowe struktury danych.

• Aby dokładnie zrozumieć struktury danych, zapoznaj się z zasobami takimi jak CLRS.

Dobry ściągacz opisujący złożoność struktur danych, algorytmów itp.

Współczuję pytaniu - ja też znalazłem(znaleźć?) wybór oszałamiający, więc postanowiłem sprawdzić, która struktura danych jest najszybsza (test zrobiłem używając VB, ale wyobrażam sobie, że C# będzie takie samo, ponieważ oba języki robią to samo na poziomie CLR). Możesz zobaczyć Niektóre wyniki benchmarkingu przeprowadzone przeze mnie tutaj (Istnieje również dyskusja, który typ danych jest najlepszy do wykorzystania w jakich okolicznościach).

Struktury danych. NET:

Więcej do rozmowy o tym, dlaczego ArrayList i lista są rzeczywiście różne

Tablice

Jak stwierdza jeden użytkownik, tablice są kolekcją "old school" (tak, tablice są uważane za kolekcję, choć nie są częścią System.Collections). Ale czym jest" old school " o tablicach w porównaniu do innych kolekcji, tj. tych, które wymieniłeś w tytule(tutaj ArrayList i List (of T))? Zacznijmy od podstaw, patrząc na tablice.

To start, Tablice W Microsoft. NET są "mechanizmami, które pozwalają traktować kilka [logicznie powiązanych] elementów jako pojedynczą kolekcję"(patrz artykuł połączony). Co to znaczy? Tablice przechowują poszczególne elementy (elementy) kolejno, jeden po drugim w pamięci z adresem początkowym. Używając 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 wspólnych koncepcji, Tablice naprawdę mogą być dość złożone:

Tablice mogą być jednowymiarowe, wielowymiarowe lub jadded (warto o nich przeczytać). Tablice same w sobie nie są dynamiczne: po zainicjalizacji tablica o rozmiarze N rezerwuje wystarczająco dużo miejsca, aby pomieścić N liczbę obiektów. Liczba elementów w tablicy nie może rosnąć ani się kurczyć. Dim _array As Int32() = New Int32(100) zastrzega wystarczająco dużo miejsca na bloku pamięci, aby tablica zawierała 100 obiektów typu prymitywnego Int32(w tym przypadku tablica jest inicjalizowana na 0s). Adres tego bloku jest zwracany na _array.

Zgodnie z artykułem, Common Language Specification (CLS) wymaga, aby wszystkie tablice były oparte na 0. Tablice w. NET obsługują tablice niezerowe; jest to jednak mniej powszechne. W związku z "powszechnością" macierzy zero, Microsoft poświęcił dużo czasu na optymalizację ich wydajności ; dlatego macierze single dimension, zero-based (SZs) są "specjalne" - i naprawdę najlepszą implementacją tablicy (w przeciwieństwie do wielowymiarowych itp.)- ponieważ SZs mają specyficzne instrukcje języka pośredniczącego do manipulowania nimi.

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

Ponownie, największą przeszkodą dla tablic jest to, że nie są one ponownie spore. Mają" stałą " pojemność. Przedstawiamy ArrayList i List(z T) do naszej historii:

ArrayList-lista niestandardowa

ArrayList (wraz z List(Of T) - choć istnieją pewne krytyczne różnice, tutaj wyjaśnione później) - jest być może najlepszym dodatkiem do zbiorów (w szerokim tego słowa znaczeniu). ArrayList dziedziczy po interfejsie IList (potomek 'ICollection'). ArrayLists, same w sobie, sąwiększe - wymagające więcejnapowietrznych - niż listy.

IList umożliwia implementacja traktująca ArrayLists jako listy o stałym rozmiarze (jak tablice); jednak poza dodatkową funkcjonalnością dodaną przez ArrayLists, nie ma realnych korzyści z używania tablic o stałym rozmiarze, Ponieważ ArrayLists (ponad tablicami) w tym przypadku są znacznie wolniejsze.

Z mojej lektury wynika, że ArrayLists nie mogą być postrzępione: "używanie tablic wielowymiarowych jako elementów... nie jest obsługiwane". Kolejny gwóźdź do trumny Arraylistów. ArrayLists także nie są "typowane" - co oznacza, że, Pod wszystkim, ArrayList jest po prostu dynamiczną tablicą obiektów: Object[]. Wymaga to dużo boksu (implicit) i unboxingu (explicit)podczas implementacji ArrayLists, ponownie dodając do ich narzutu.

bezpodstawna myśl: myślę, że pamiętam albo czytanie lub słyszałem od jednego z moich profesorów, że ArrayLists są rodzajem bękarta pojęciowego dziecka próby przejścia z tablic do kolekcji typu List, tj. Tablice nie są już najlepszą opcją, ponieważ dalszy rozwój został dokonany w odniesieniu do zbiorów

List(of T): czym stał się ArrayList (i miał nadzieję być)

Różnica w zużyciu pamięci jest na tyle znacząca, że lista (Int32) zużywała 56% mniej pamięci niż lista ArrayList zawierająca ten sam prymitywny typ (8 MB vs. 19 MB w powyższej demonstracji linked: again, linked here) - choć jest to wynik spotęgowany przez 64-bitowy maszyna. Ta różnica pokazuje dwie rzeczy: po pierwsze (1), boxed Int32-type "object" (ArrayList) jest znacznie większy niż czysty Int32 primitive type (List); po drugie (2), Różnica jest wykładnicza w wyniku wewnętrznego działania 64-bitowej maszyny.

Więc jaka jest różnica i co to jest lista (T)? MSDN definiuje List(Of T) jako "... silnie wpisana lista obiektów, do których można uzyskać dostęp przez indeks."Znaczenie ma tutaj bit "mocno wpisany": a List (of T) 'rozpoznaje' typy i przechowuje obiekty jako ich typ. Tak więc {[7] } jest przechowywany jako Int32, a nie Object. Eliminuje to problemy spowodowane boksem i rozpakowywaniem.

MSDN określa tę różnicę tylko w przypadku przechowywania typów prymitywnych, a nie typów referencyjnych. różnica występuje naprawdę na dużą skalę: ponad 500 elementów. Co ciekawsze, w dokumentacji MSDN czytamy: "korzystnie jest używać specyficznych typów Implementacja klasy List (of T) zamiast użycia klasy ArrayList...."

Zasadniczo List (of T) jest ArrayList, ale lepiej. Jest to" ogólny odpowiednik " ArrayList. Podobnie jak ArrayList, nie ma gwarancji, że zostanie posortowana, dopóki nie zostanie posortowana (go figure). List (of T) posiada również pewne dodatkowe funkcje.

Są napisane całkiem dobrze w intellisense. Wystarczy wpisać System.Kolekcje. lub System.Kolekcje.Generics (preferowane), a otrzymasz listę i krótki opis tego, co jest dostępne.

Hashtables / słowniki są o (1) performance, co oznacza, że performance nie jest funkcją wielkości. To ważne wiedzieć.

EDIT: w praktyce średnia złożoność czasowa dla wyszukiwań Hashtable / Dictionary wynosi O(1).

Kolekcje generyczne będą działać lepiej niż ich nie-generyczne odpowiedniki, zwłaszcza gdy iteracja przez wiele elementów. Dzieje się tak dlatego, że boks i unboxing nie występują już.

Ważna uwaga na temat Hashtable vs Dictionary for high frequency systematic trading engineering: thread Safety Issue

Hashtable jest bezpieczny dla wielu wątków. Dictionary public static members są bezpieczne dla wątków, ale żadne instancje members nie są gwarantowane.

Więc Hashtable pozostaje "standardowym" wyborem w tym zakresie.

Właściwie, myślę, że MSDN pomaga udzielić całkiem dobrych odpowiedzi na wszystkie te pytania. Po prostu sprawdź Kolekcje. NET.

Istnieją subtelne i nie tak subtelne różnice między zbiorami generycznymi i niegenerycznymi. Używają jedynie różnych bazowych struktur danych. Na przykład Hashtable gwarantuje jeden pisarz-wielu czytelników bez synchronizacji. Słownik nie.

Najpopularniejsze struktury i kolekcje danych C#

• Array
• ArrayList
• lista
• LinkedList
• Słownik
• HashSet
• Stack
• Kolejka
• SortedList

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

W tym artykule przejdę do wbudowanych struktur danych C#, w tym do nowych wprowadzanych w C#.NET 3.5. Zauważ, że wiele z tych struktur danych ma zastosowanie do innych języków programowania.

Array

Najprostszą i najpowszechniejszą strukturą danych jest tablica. Tablica C# jest w zasadzie listą obiektów. Jego definiowanie cechy są takie, ż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 w liście (inaczej zwanej indeksem). Tablica C# jest zdefiniowana w następujący sposób:

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

Niektóre przykłady:

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

Jak widać z powyższego przykładu, tablica może być zainializowana bez elementów lub z zestawu istniejących wartości. Wstawianie wartości do tablicy jest proste, o ile fit. Operacja staje się kosztowna, gdy jest więcej elementów niż rozmiar tablicy, w którym to momencie tablica musi zostać rozszerzona. 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 mieć dowolną ilość obiektów i dowolnego typu. Ta struktura danych została zaprojektowana w celu uproszczenia procesów dodawania nowych elementów do tablica. Pod maską ArrayList jest tablicą, której rozmiar jest podwojony za każdym razem, gdy zabraknie miejsca. Podwojenie rozmiaru tablicy wewnętrznej jest bardzo skuteczną strategią, która zmniejsza ilość kopiowania elementów w dłuższej perspektywie. Nie będziemy mieli dowodów. 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 trzeba przywrócić pobrane wartości z powrotem do ich oryginalnego typu:

int arrayListValue = (int)myArrayList[0]

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

• C # Struktury Danych
• Kolekcje i struktury danych
• lista vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Kolekcje.Ogólna Przestrzeń Nazw
• System.Przestrzeń Nazw Zbiorów