Sfaturi despre utilizarea colecțiilor

1. Lista colecțiilor

După cum vă amintiți, Java are colecții - un instrument la îndemână pentru stocarea obiectelor de același tip.

Să încercăm să ne amintim principalele interfețe legate de colecție:

List , Set , Map and Queue .

Ca de obicei, instrumentele nu sunt neapărat bune sau rele – ceea ce contează este dacă le utilizați în scopul pentru care sunt destinate. Și pentru a face asta, trebuie să înțelegem temeinic caracteristicile lor specifice pentru a ști ce colecție să folosim și când.

1. Lista

Să începem cu cea mai folosită colecție.

Listați cât mai aproape posibil de un tablou vechi simplu.

Această colecție ne permite să stocăm în mod convenabil o listă de obiecte de același tip, fără a ne face griji cu privire la dimensiunea colecției în sine, așa cum ar trebui să facem dacă am folosi o matrice. Elementele colecției sunt accesate prin index. Dacă știm exact unde se află un obiect și trebuie să-l accesăm frecvent fără a fi nevoie să adăugăm sau să eliminăm elemente, o listă este ideală.

2. Setați

Setul are o structură complet diferită.

Setul este cel mai potrivit atunci când trebuie să depozităm obiecte unice. De exemplu, un set de autori dintr-o bibliotecă în care fiecare autor este unic. Dar nu putem pur și simplu să luăm orice autor anume din el. Set ne permite să verificăm rapid dacă un anumit autor este prezent în biblioteca noastră, adică putem verifica dacă un obiect unic este prezent într-un Set . De asemenea, putem itera întreaga colecție, accesând fiecare element, dar a face asta nu este optim.

Cu alte cuvinte, pentru biblioteca noastră, un set poate reprezenta colecția tuturor autorilor unici pentru a verifica rapid dacă este prezent un anumit autor.

3. Harta

Harta este mai mult ca un dulap de dosare, unde fiecare fișier este semnat și poate stoca obiecte individuale sau structuri întregi. Harta ar trebui să fie utilizată în cazurile în care trebuie să menținem o mapare de la o valoare la alta.

Pentru Map , aceste relații sunt numite perechi cheie-valoare.

Am putea folosi această structură în biblioteca noastră utilizând obiecte de autor ca chei și liste ( obiecte Listă ) de cărți ca valori. Astfel, după verificarea unui set pentru a vedea dacă un obiect autor există în bibliotecă, putem folosi același obiect autor pentru a obține o listă a cărților sale dintr-o hartă .

4. Coadă

Queue este o colecție care — surprinde! — implementează comportamentul unei cozi. Și coada poate fi fie LIFO (Last In, First Out) fie FIFO (First In, First Out). În plus, coada poate fi bidirecțională sau „dublată”.

Această structură este utilă atunci când obiectele adăugate la clasă trebuie utilizate în ordinea în care sunt primite. De exemplu, luați biblioteca noastră.

Putem adăuga vizitatori nou sosiți la o coadă și îi putem servi pe rând, eliberând cărțile pentru care vin.

După cum putem vedea, fiecare dintre aceste structuri este bună dacă este utilizată în scopul propus. Și am găsit utilizări bune pentru toate cele patru tipuri de colecții într-un singur exemplu de bibliotecă.

2. Complexitatea

După cum am menționat deja, colecțiile pe care le-am considerat mai sus sunt interfețe, ceea ce înseamnă că trebuie să aibă implementări pentru ca noi să le folosim.

Așa cum ciocanul cuielor cu un microscop nu este cea mai bună idee, nu fiecare implementare a unei colecții este potrivită fiecărei situații.

Atunci când alegem instrumentul potrivit pentru o lucrare, ne uităm de obicei la două caracteristici:

• Cât de bine se potrivește unealta la locul de muncă?
• Cât de repede va termina treaba?

Am petrecut ceva timp să ne dăm seama cum să alegem un instrument potrivit pentru o lucrare, dar viteza acestuia este ceva nou.

În calcul, viteza unui instrument este adesea exprimată în termeni de complexitate a timpului și notată cu litera O majusculă.

Ce naiba este complexitatea timpului?

În termeni simpli, complexitatea timpului indică timpul necesar unui algoritm din colecție pentru a efectua o anumită acțiune (adăugarea/eliminarea unui element, căutarea unui element).

ArrayList vs LinkedList

Să ne uităm la asta folosind două implementări ale interfeței List - ArrayList și LinkedList .

Pentru apariția exterioară, lucrul cu aceste colecții este similar:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

După cum puteți vedea, pentru ambele tipuri de colecție, adăugarea, obținerea și eliminarea elementelor arată la fel. Acest lucru se datorează faptului că acestea sunt implementări pe aceeași interfață. Dar aici se termină asemănările.

Datorită implementărilor diferite ale interfeței Listă , aceste două structuri efectuează acțiuni diferite mai eficient decât altele.

Luați în considerare eliminarea și adăugarea unui element.

Dacă trebuie să eliminam un element din mijlocul unui ArrayList , trebuie să suprascriem orice parte a listei urmează elementului pe care îl eliminam.

Să presupunem că avem o listă de 5 elemente și dorim să-l eliminăm pe al treilea.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

În acest caz, eliminarea eliberează o celulă, așa că trebuie să scriem al 4-lea element unde a fost al 3-lea și al 5-lea unde a fost al 4-lea.

Acest lucru este extrem de ineficient.

Același lucru se întâmplă atunci când adăugați un element la mijlocul listei.

LinkedList este structurat diferit. Adăugarea sau eliminarea elementelor este rapidă, deoarece trebuie doar să schimbăm referințele din elementele precedente și următoare, excluzând astfel obiectul pe care îl scoatem din lanțul de elemente.

Revenind la exemplul aceleiași liste de 5 elemente, după eliminarea celui de-al 3-lea element, tot ce trebuie să facem este să schimbăm pur și simplu referința celui de-al 2-lea element la următorul element și referința celui de-al 4-lea element la cel anterior.

Când un element este adăugat în listă, se întâmplă același proces, dar invers.

Observați cât de mult mai puțină muncă trebuie să facem într-un LinkedList în comparație cu un ArrayList . Și acestea sunt doar 5 elemente. Dacă lista noastră ar avea 100 sau mai multe elemente, superioritatea LinkedList ar deveni și mai vizibilă.

Dar cum se schimbă situația dacă accesăm un element prin index?

Totul este exact opusul aici.

Deoarece ArrayList este structurat ca o matrice obișnuită, obținerea oricărui element prin indexul său va fi foarte ușor pentru noi. Pur și simplu mutăm indicatorul într-un anumit loc și obținem elementul din celula corespunzătoare.

Dar un LinkedList pur și simplu nu funcționează așa. Trebuie să parcurgem toate elementele listei pentru a găsi elementul cu un anumit indice.

Să încercăm să exprimăm toate acestea în termeni de O mare?

Să începem prin a accesa un element după index.

Într-o ArrayList , acest lucru se întâmplă într-un singur pas, indiferent de locul în care se află elementul în listă. Fie la sfârșit, fie la început.

În acest caz, complexitatea timpului va fi O(1) .

Într-un LinkedList , trebuie să iterăm peste un număr de elemente egal cu valoarea indexului de care avem nevoie.

Complexitatea timpului pentru o astfel de acțiune este O(n) , unde n este indicele elementului de care avem nevoie.

Aici vedeți că numărul pe care îl punem în parantezele cu O mare corespunde numărului de acțiuni efectuate.

Shell ne întoarcem la eliminarea și adăugarea?

Să începem cu LinkedList.

Deoarece nu trebuie să facem un număr mare de acțiuni pentru a adăuga sau elimina un element, iar viteza acestei operații nu depinde în niciun fel de locul în care se află elementul, complexitatea este exprimată ca O(1) și se spune să fie constantă.

Complexitatea de timp a acestei operații pentru ArrayList este, de asemenea , O(n) , pe care o numim complexitate liniară.

În algoritmii cu complexitate liniară, timpul de rulare depinde direct de numărul de elemente care trebuie procesate. Poate depinde și de poziția elementului, indiferent dacă este la începutul listei sau spre sfârșit.

Complexitatea timpului poate fi, de asemenea, logaritmică. Aceasta este exprimată ca O(log n) .

Ca exemplu, luați în considerare un TreeSet sortat format din 10 numere. Vrem să găsim numărul 2.

Deoarece lista este sortată și nu conține duplicate, o putem împărți în jumătate și putem verifica care jumătate ar conține numărul dorit, aruncăm partea irelevantă și apoi repetam acest proces până ajungem la elementul dorit. În cele din urmă, vom găsi (sau nu vom găsi) numărul după procesarea log(n) număr de elemente.

Iată un tabel care rezumă complexitatea timpului din restul colecțiilor.

Acum că avem un tabel care arată complexitatea în timp a colecțiilor populare, putem răspunde la întrebarea de ce, din atâtea colecții, folosim cel mai adesea ArrayList , HashSet și HashMap .

Pur și simplu, sunt cele mai eficiente pentru majoritatea sarcinilor :)