Megosztás:

Gyűjtemények és adatstruktúrák

A hasonló adatok gyakran hatékonyabban kezelhetők, ha gyűjteményként tárolják és kezelik őket. Az System.Array osztályt vagy a System.Collections, System.Collections.Generic, System.Collections.Concurrent és System.Collections.Immutable névterekben található osztályokat használhatja a gyűjtemény egyes elemeinek vagy elemtartományának hozzáadásához, eltávolításához és módosításához.

Két fő gyűjteménytípus létezik; általános gyűjtemények és nem általános gyűjtemények. Az általános gyűjtemények fordítási időben típusbiztosak. Emiatt az általános gyűjtemények általában jobb teljesítményt nyújtanak. Az általános gyűjtemények a létrehozásakor elfogadják a típusparamétert. Nem követelik meg, hogy a gyűjtemény elemeinek hozzáadásakor vagy eltávolításakor a Object típusra és onnan konvertáljon. Emellett a legtöbb általános gyűjtemény támogatott a Windows Áruházbeli alkalmazásokban. A nem generikus gyűjtemények elemeket tárolnak Object formában, ami típuskonverziót igényel, és a legtöbb nem támogatott a Windows Áruház alkalmazásfejlesztés során. Előfordulhat azonban, hogy a régebbi kódban nem általános gyűjtemények láthatók.

A .NET-keretrendszer 4- és újabb verzióiban a System.Collections.Concurrent névtérben lévő gyűjtemények hatékony szálbiztos műveleteket biztosítanak a több szálból származó gyűjteményelemek eléréséhez. A névtér (System.Collections.ImmutableNuGet-csomag) nem módosítható gyűjteményosztályai eredendően szálbiztosak, mivel a műveletek az eredeti gyűjtemény egy példányán hajthatók végre, és az eredeti gyűjtemény nem módosítható.

Gyakori gyűjteményfunkciók

Minden gyűjtemény metódusokat biztosít a gyűjtemény elemeinek hozzáadásához, eltávolításához vagy kereséséhez. Ezen kívül minden gyűjtemény, amely közvetlenül vagy közvetve implementálja az ICollection interfészt vagy az interfészt ICollection<T> , a következő funkciókkal rendelkezik:

  • A gyűjtemény számbavételének lehetősége

    A .NET-gyűjtemények implementálhatják a System.Collections.IEnumerable vagy System.Collections.Generic.IEnumerable<T> ahhoz, hogy engedélyezzék a gyűjtemények végigiterálását. Az enumerátorok a gyűjtemény bármely elemére mutató mozgatható mutatóként tekinthetők. A foreach, in utasítás és a For Each...Next utasítás a metódus által biztosított enumerátort használja, és rejti el az enumerátor manipulálásának összetettségét. Emellett minden implementált System.Collections.Generic.IEnumerable<T> gyűjtemény lekérdezhető típusnak minősül, és lekérdezhető a LINQ használatával. A LINQ-lekérdezések általános mintát biztosítanak az adatok eléréséhez. Ezek általában tömörebbek és olvashatóbbak, mint a standard foreach hurkok, és szűrési, rendezési és csoportosítási képességeket biztosítanak. A LINQ-lekérdezések a teljesítményt is javíthatják. További információ: LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Introduction to LINQ Query (C#) és Basic Query Operations (Visual Basic).

  • A gyűjtemény tartalmának tömbbe másolása

    A metódussal CopyTo minden gyűjtemény átmásolható egy tömbbe. Az új tömb elemeinek sorrendje azonban azon a sorrenden alapul, amelyben az enumerátor visszaadja őket. Az eredményül kapott tömb mindig egydimenziós, nulla alsó határral.

Emellett számos gyűjteményosztály a következő funkciókat tartalmazza:

  • Kapacitás és darabszám tulajdonságai

    A gyűjtemények kapacitása a tartalmazható elemek száma. Egy gyűjtemény elemszáma a ténylegesen tartalmazott elemek száma. Egyes gyűjtemények elrejtik a kapacitást, a darabszámot vagy mindkettőt.

    A gyűjtemények többsége az aktuális kapacitás elérésekor automatikusan kibővül. A rendszer újratelepíti a memóriát, és az elemeket átmásolja a régi gyűjteményből az újba. Ez a kialakítás csökkenti a gyűjtemény használatához szükséges kódot. A gyűjtemény teljesítményét azonban negatívan befolyásolhatja. Például egy List<T>elem hozzáadása O(1) művelet, ha Count kisebb, mint Capacity. Ha a kapacitást növelni kell az új elem elhelyezéséhez, akkor egy elem hozzáadása O(n) művelet lesz, ahol n az van Count. A több újratelepítés által okozott gyenge teljesítmény elkerülésének legjobb módja, ha a kezdeti kapacitást a gyűjtemény becsült méretének állítja be.

    Az BitArray egy különleges eset; kapacitása megegyezik a hosszával, és ez egyezik a darabszámával.

  • Konzisztens alsó határ

    A gyűjtemény alsó határa az első elem indexe. A névterekben a System.Collections indexált gyűjtemények alsó határa nulla, ami azt jelenti, hogy 0-val indexáltak. Array alapértelmezés szerint nulla alsó korláttal rendelkezik, de a TömbosztályArray.CreateInstanceegy példányának létrehozásakor egy másik alsó határ definiálható.

  • Szinkronizálás több szálból (System.Collections csak osztályokból) való hozzáféréshez.

    A System.Collections névtér speciális gyűjteménytípusai bizonyos szintű szálbiztonságot biztosítanak szinkronizálással, általában a SyncRoot és IsSynchronized tagokon keresztül van kitéve. Ezek a gyűjtemények alapértelmezés szerint nem szálbiztosak. Ha skálázható és hatékony többszálú hozzáférést szeretne egy gyűjteményhez, használja a System.Collections.Concurrent névtér egyik osztályát, vagy fontolja meg egy nem módosítható gyűjtemény használatát. További információ: Thread-Safe Gyűjtemények.

Gyűjtemény kiválasztása

Általában általános gyűjteményeket kell használnia. Az alábbi táblázat néhány gyakori gyűjteményforgatókönyvet és az ezekhez a forgatókönyvekhez használható gyűjteményosztályokat ismerteti. Ha még nem használja az általános gyűjteményeket, az alábbi táblázat segít kiválasztani a feladatához leginkább megfelelő általános gyűjteményt:

Akarok... Általános gyűjtemény beállításai Nem általános gyűjteménybeállítások Szálbiztos vagy változtathatatlan gyűjteménytípusok
Elemek tárolása kulcs/érték párként a kulcsok gyors kereséséhez Dictionary<TKey,TValue> Hashtable

(Kulcs/érték párok gyűjteménye, amelyek a kulcs kivonatkódja alapján vannak rendszerezve.)		 ConcurrentDictionary<TKey,TValue>

ReadOnlyDictionary<TKey,TValue>

ImmutableDictionary<TKey,TValue>
Elemek elérése index szerint List<T> Array

ArrayList		 ImmutableList<T>

ImmutableArray
Az elemek használata a beérkezés sorrendjében (FIFO) Queue<T> Queue ConcurrentQueue<T>

ImmutableQueue<T>
Adatok utolsóFirst-Out (LIFO) használata Stack<T> Stack ConcurrentStack<T>

ImmutableStack<T>
Elemek egymás utáni elérése LinkedList<T> Nincs javaslat Nincs javaslat
Értesítéseket kaphat az elemek eltávolításáról vagy a gyűjteményhez való hozzáadásáról. (implementálja INotifyPropertyChanged és INotifyCollectionChanged) ObservableCollection<T> Nincs javaslat Nincs javaslat
Rendezett gyűjtemény SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

ImmutableSortedSet<T>
Matematikai függvények készlete HashSet<T>

SortedSet<T>		 Nincs javaslat ImmutableHashSet<T>

ImmutableSortedSet<T>

Gyűjtemények algoritmikus összetettsége

Gyűjteményosztály kiválasztásakor érdemes megfontolni a teljesítmény potenciális kompromisszumoit. Az alábbi táblázatból megtudhatja, hogyan hasonlíthatók össze a különböző mutable gyűjteménytípusok az algoritmikus összetettségben a hozzájuk tartozó nem módosítható megfelelőkkel. A nem módosítható gyűjteménytípusok teljesítménye gyakran gyengébb, de biztosítják a változtathatatlanságot – ami gyakran érvként érvényesül egy összehasonlítás során.

Változtatható Amortizált Legrosszabb eset Megváltoztathatatlan Összetettség
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>.AddKeresési 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> Keresés O(1) O(1) – vagy szigorúan O(n) ImmutableDictionary<T> Keresés O(log n)
SortedDictionary<T>.Add O(log n) O(n log n) ImmutableSortedDictionary<T>.Add O(log n)

A List<T> hatékonyan felsorolható egy for ciklus vagy egy foreach ciklus használatával. Azonban egy ImmutableList<T> nem teljesít jól egy for cikluson belül, mivel az indexelője O(log n) időt igényel. Az ImmutableList<T> felsorolása foreach ciklus használatával hatékony, mert a ImmutableList<T> bináris fát használ az adatok tárolására, ahelyett, hogy tömböt használna, mint ahogy azt a List<T> teszi. A tömbök gyorsan indexelhetők, míg a bináris fát le kell járni, amíg meg nem találja a kívánt indexet tartalmazó csomópontot.

Ráadásul a SortedSet<T> ugyanolyan összetettségű, mint a ImmutableSortedSet<T>, mivel mindketten bináris fákat használnak. A jelentős különbség az, hogy ImmutableSortedSet<T> egy nem módosítható bináris fát használ. Mivel a ImmutableSortedSet<T> egy olyan osztályt is kínál System.Collections.Immutable.ImmutableSortedSet<T>.Builder, amely lehetővé teszi a mutációt, így egyszerre élvezheti a megváltoztathatatlanságot és a teljesítményt.

Cím Leírás
Gyűjteményosztály kiválasztása Ismerteti a különböző gyűjteményeket, és segít kiválasztani egyet a forgatókönyvéhez.
Gyakran használt gyűjteménytípusok A gyakran használt általános és nem általános gyűjteménytípusokat ismerteti, például System.Array: , System.Collections.Generic.List<T>és System.Collections.Generic.Dictionary<TKey,TValue>.
Mikor érdemes használni az általános gyűjteményeket Az általános gyűjteménytípusok használatát ismerteti.
Összehasonlítások és rendezés gyűjteményeken belül Az egyenlőségi összehasonlítások és a rendezési összehasonlítások gyűjteményekben való használatát ismerteti.
Rendezett gyűjteménytípusok A rendezett gyűjtemények teljesítményét és jellemzőit ismerteti.
Hasítótábla és szótár gyűjteménytípusok Az általános és nem általános kivonatalapú szótártípusok funkcióit ismerteti.
Thread-Safe gyűjtemények Olyan gyűjteménytípusokat ismertet, mint például System.Collections.Concurrent.BlockingCollection<T>System.Collections.Concurrent.ConcurrentBag<T> a több szálból származó biztonságos és hatékony egyidejű hozzáférést támogató gyűjteménytípusok.
System.Collections.Immutable Bemutatja a nem módosítható gyűjteményeket, és hivatkozásokat biztosít a gyűjteménytípusokra.

Referenciák

  • Last updated on