Există multe tipuri de colecții, bine cunoscute în domeniul informaticii, dar care nu sunt incluse în .NET Framework. Unele dintre ele au devenit foarte răspândite, iar aplicațiile dvs. ar putea beneficia de anumite beneficii din utilizarea lor. În plus, cele mai multe dintre ele pot fi implementate într-un timp destul de scurt. În ciuda faptului că nu ne-am stabilit obiectivul de cercetare pentru a face diferite tipuri de colecții, cu toate acestea, dau două exemple de colecții, care sunt semnificativ diferite de colecții în .NET, și oferă să ia în considerare o situație în care utilizarea propriilor lor colecții pot fi utile.
Un sistem de seturi disjuncte
Un sistem de seturi disjuncte este o colecție a cărei elemente sunt stocate sub formă de seturi disjuncte. Aceasta diferă de colecțiile .NET prin faptul că nu permite salvarea elementelor în ea. În schimb, se formează un domeniu de elemente, în care fiecare element formează un singur set și se determină o secvență de operații pentru a fuziona în seturi mai mari. Această structură de date asigură o eficiență ridicată a două operații:
unirea a două subseturi cu scopul de a obține un subset comun;
căutarea, determină subsetul de care aparține elementul (adesea folosit pentru a determina dacă cele două elemente aparțin aceluiași subset).
De obicei, operațiunile cu seturi sunt efectuate la nivelul reprezentanților membri - cu un singur reprezentant din fiecare set. Operațiile de aderare și de căutare acceptă și se întorc pe reprezentanți, nu pe seturi întregi.
O implementare naivă a unui sistem de seturi disjuncte implică utilizarea colecției pentru a reprezenta fiecare set și îmbinarea colecțiilor după cum este necesar. De exemplu, dacă utilizați o listă asociată pentru stocarea fiecărui set, timpul pentru îmbinarea acestora este direct proporțional cu numărul de seturi, iar operația de căutare poate dura un timp constant dacă fiecare element are un indicator pentru reprezentantul setului.
Implementarea algoritmului Galler-Fischer are o complexitate mult mai mare. Seturile sunt stocate ca o "pădure" (un set de copaci); fiecare nod al fiecărui arbore stochează un pointer în nodul său părinte, iar rădăcina copacului este un reprezentant al setului. Pentru a asigura echilibrul arborilor care rezultă, atunci când se amestecă copacii, un copac mai mic intră mereu în rădăcina unui copac mai mare (acest lucru necesită monitorizarea adâncimii copacului). În plus, operația de căutare comprimă calea de la elementul dorit la reprezentantul său. Mai jos este o implementare schematică a acestui algoritm:
Măsurarea exactă a performanței acestei structuri de date este o sarcină foarte dificilă. In cel mai simplu caz limita superioară amortizată funcționare timp în pădurea de n elemente este O (log * n), unde log * n (calcul iterativ de logaritm) - numărul funcției de calcul logaritm folosește pentru a produce un rezultat mai mic decât unul, adică, numărul minim de apariții «log "În jurnalul de logare inegalitatea log. log n. care stochează pur și simplu matricea sortată. O abordare tipică pentru rezolvarea acestei probleme este de a lista de randomizare ierarhie (prezentată mai jos), care vă permite să obțineți timp logaritmică de așteptat pentru a insera, șterge și căuta elemente:
Se poate întâmpla, de asemenea, să vă aflați într-o situație unică, atunci când puteți rezolva sarcina pusă doar cu utilizarea colecției proprii. Le numim colecții unice. deoarece sunt invenții complet noi, potrivite pentru o sarcină specifică. Cu timpul, puteți constata că una dintre colecțiile dvs. unice poate fi reutilizată. Și în această secțiune vom cunoaște o astfel de colecție.
Imaginați-vă această situație: ați creat un sistem de informații de schimb care oferă vânzătorilor de bare de ciocolată informații cu privire la prețurile pentru barele diferite. Tabelul principal de date este stocat în memorie și conține un rând pentru fiecare tip de bare care conține prețul curent pentru o bară dată. Tabelul de mai jos prezintă un exemplu al acestui tabel cu date la un moment dat:
Exemplu de tabel cu date în sistemul de informații pentru vânzătorii de bare
Vânzătorii de bare sunt conectați la sistem printr-o priză TCP și solicită periodic informații proaspete despre un anumit tip de bare. O solicitare tipică din partea vânzătorului arată: "Care este prețul pentru Twix?". Iar răspunsul tipic este "$ 0.93". Fiecare al doilea zeci de mii de astfel de cereri intră în sistem.
Producătorii de bare sunt conectați la sistem prin mufa UDP și stabilesc periodic un nou preț pentru barele lor. Solicitările producătorilor sunt împărțite în două subtipuri:
"Setați prețul pentru Marte la 0,91 $." Nu este nevoie să răspundeți la o astfel de solicitare. În fiecare secundă, sistemul primește mii de astfel de cereri.
"Adăugați un nou bar Snowflakes cu un preț inițial de 0,49 $." Nu este nevoie să răspundeți la o astfel de solicitare. Astfel de solicitări nu intră în sistem mai mult de câteva zeci pe zi.
De asemenea, este cunoscut faptul că 99,9% din operațiunile de citire sau actualizare sunt efectuate pentru tipurile de bare existente la momentul inițierii tranzacționării, iar doar 0,1% din operațiuni se încadrează în ponderea barelor noi adăugate.
Înarmat cu aceste informații, ați decis să proiectați o structură de date - o colecție - pentru a stoca un tabel cu date în memorie. Această structură ar trebui să susțină capacitatea de a folosi într-un mediu multi-threaded, deoarece sute de fire de execuție pot încerca simultan să acceseze. Nu trebuie să vă faceți griji cu privire la salvarea datelor în unele stocări persistente - vom examina caracteristicile de performanță numai în cazul în care găsiți colecția în memorie.
Formularul de date și tipurile de interogări dictează necesitatea utilizării unei tabele de tip hash. Sincronizarea accesului la masa de tip hash este o sarcină dificilă, care ar trebui mutată la umerii ConcurrentDictionary
O posibilă soluție este o memorie cache sigură. Această colecție este un set de două tabele hash, un tabel sigur și o tabelă nesigură. O masă securizată este plină de informații despre tipurile de bare existente la momentul începuturilor; Tabelul nesigur este inițial gol. Operațiile cu masa de siguranță sunt executate fără blocare, deoarece nu se schimbă; Noi tipuri de bare sunt adăugate la masa nesigură. Mai jos este o posibilă implementare a acestei structuri de date folosind Dictiornary
Următorul pas în dezvoltarea acestei structuri de date ar putea fi suspendarea periodică a operațiunilor de tranzacționare și combinarea tabelelor sigure și nesigure. Acest lucru ar reduce în continuare necesitatea ca sincronizarea să aibă acces la date.
Implementarea IEnumerabile și alte interfețe
Aproape orice colecție în cele din urmă implementează interfața IEnumerable
Din nefericire, implementarea simplă a interfeței IEnumerabile
În fiecare iterație, în acest exemplu, se cheamă două metode de interfață, care implică cheltuieli inutile atunci când încercați să ocoliți lista și să calculați produsul elementelor sale. Metodele de încorporare a interfețelor nu sunt o sarcină simplă și dacă compilatorul JIT nu o poate rezolva, costul apelurilor lor va fi foarte mare.
Există mai multe soluții care pot ajuta la evitarea cheltuielilor inutile atunci când apelează metode. Atunci când metodele de interfață sunt aplicate direct la o variabilă de tip de valoare, ele sunt apelate direct. Aceasta este, dacă variabila enumerator din exemplul de mai sus are un tip de valoare (și nu IEnumerator
Pentru aceasta, de exemplu, lista de clase
Aceasta vă permite să scrieți acest cod:
eliminarea apelurilor prin metoda interfeței.
O soluție alternativă este crearea unui iterator cu un tip de referință, dar folosind același truc cu o implementare explicită a interfeței - metoda MoveNext () și proprietatea curentă. De asemenea, va permite programului de apel să folosească metoda și proprietatea clasei în mod direct, evitând astfel costurile aferente metodelor de interfață de apelare.