Suggerimenti per l'utilizzo delle raccolte

1. Elenco delle collezioni

Come forse ricorderete, Java ha raccolte, uno strumento utile per archiviare oggetti dello stesso tipo.

Proviamo a richiamare le principali interfacce relative alla collezione:

Elenco , Imposta , Mappa e Coda .

Come al solito, gli strumenti non sono necessariamente buoni o cattivi: ciò che conta è se li stai usando per lo scopo previsto. E per farlo, dobbiamo conoscerne a fondo le caratteristiche specifiche per sapere quale collezione utilizzare e quando.

1. Elenco

Iniziamo con la collezione più utilizzata.

Elenca il più vicino possibile a un semplice vecchio array.

Questa raccolta ci consente di archiviare comodamente un elenco di oggetti dello stesso tipo senza preoccuparci della dimensione della raccolta stessa, come dovremmo fare se stessimo utilizzando un array. Gli elementi della raccolta sono accessibili tramite indice. Se sappiamo esattamente dove si trova un oggetto e abbiamo bisogno di accedervi frequentemente senza dover spesso aggiungere o rimuovere elementi, un elenco è l'ideale.

2. Impostare

Set ha una struttura completamente diversa.

Il set è più adatto quando abbiamo bisogno di conservare oggetti unici. Ad esempio, un insieme di autori in una libreria in cui ogni autore è unico. Ma non possiamo limitarci a prenderne uno specifico autore. Set ci permette di verificare velocemente se un particolare autore è presente nella nostra libreria, cioè possiamo controllare se un oggetto univoco è presente in un Set . Possiamo anche iterare sull'intera raccolta, accedendo a ogni elemento, ma farlo non è ottimale.

In altre parole, per la nostra libreria, un Set può rappresentare la raccolta di tutti gli autori univoci per verificare rapidamente se è presente qualche autore in particolare.

3. Mappa

Map è più simile a uno schedario, dove ogni file è firmato e può contenere singoli oggetti o intere strutture. Map dovrebbe essere utilizzato nei casi in cui è necessario mantenere una mappatura da un valore a un altro.

Per Map , queste relazioni sono chiamate coppie chiave-valore.

Potremmo usare questa struttura nella nostra libreria usando gli oggetti autore come chiavi e le liste ( Oggetti lista ) dei libri come valori. Quindi, dopo aver controllato un Set per vedere se esiste un oggetto autore nella libreria, possiamo utilizzare lo stesso oggetto autore per ottenere un Elenco dei suoi libri da una Mappa .

4. Coda

Queue è una collezione che — sorpresa! — implementa il comportamento di una coda. E la coda può essere LIFO (Last In, First Out) o FIFO (First In, First Out). Inoltre, la coda può essere bidirezionale o "a doppia estremità".

Questa struttura è utile quando gli oggetti aggiunti alla classe devono essere utilizzati nell'ordine in cui vengono ricevuti. Ad esempio, prendi la nostra biblioteca.

Possiamo aggiungere i visitatori appena arrivati ​​a una coda e servirli a turno, consegnando i libri per cui vengono.

Come possiamo vedere, ciascuna di queste strutture è buona se utilizzata per lo scopo previsto. E abbiamo trovato buoni usi per tutti e quattro i tipi di raccolte in un singolo esempio di libreria.

2. Complessità

Come già notato, le raccolte che abbiamo considerato sopra sono interfacce, il che significa che devono avere implementazioni per poterle utilizzare.

Così come martellare chiodi con un microscopio non è l'idea migliore, non tutte le realizzazioni di una collezione sono adatte a ogni situazione.

Quando si sceglie lo strumento giusto per un lavoro, in genere guardiamo a 2 caratteristiche:

• Quanto bene lo strumento si adatta al lavoro?
• Quanto velocemente porterà a termine il lavoro?

Abbiamo passato del tempo a capire come scegliere uno strumento adatto per un lavoro, ma la sua velocità è qualcosa di nuovo.

In informatica, la velocità di uno strumento è spesso espressa in termini di complessità temporale e indicata con la lettera maiuscola O.

Cos'è nel mondo la complessità del tempo?

In termini semplici, la complessità temporale indica il tempo necessario a un algoritmo nella raccolta per eseguire una particolare azione (aggiunta/rimozione di un elemento, ricerca di un elemento).

ArrayList vs LinkedList

Diamo un'occhiata a questo utilizzando due implementazioni dell'interfaccia List : ArrayList e LinkedList .

Per quanto riguarda l'aspetto esteriore, lavorare con queste raccolte è simile:

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);
    

Come puoi vedere, per entrambi i tipi di raccolta, aggiungere, ottenere e rimuovere elementi ha lo stesso aspetto. Questo perché si tratta di implementazioni sulla stessa interfaccia. Ma è qui che finiscono le somiglianze.

A causa delle diverse implementazioni dell'interfaccia List , queste due strutture eseguono azioni diverse in modo più efficiente rispetto ad altre.

Prendere in considerazione la rimozione e l'aggiunta di un elemento.

Se dobbiamo rimuovere un elemento dal centro di un ArrayList , dobbiamo sovrascrivere qualunque parte dell'elenco segua l'elemento che rimuoviamo.

Supponiamo di avere una lista di 5 elementi e di voler rimuovere il 3°.

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

In questo caso, la rimozione libera una cella, quindi dobbiamo scrivere il 4° elemento dove era il 3°, e il 5° dove era il 4°.

Questo è altamente inefficiente.

Lo stesso accade quando si aggiunge un elemento al centro dell'elenco.

LinkedList è strutturato in modo diverso. L'aggiunta o la rimozione di elementi è veloce, poiché dobbiamo solo modificare i riferimenti negli elementi precedenti e successivi, escludendo così l'oggetto che stiamo rimuovendo dalla catena di elementi.

Tornando all'esempio della stessa lista di 5 elementi, dopo aver rimosso il 3° elemento, basterà semplicemente cambiare il riferimento del 2° elemento all'elemento successivo e il riferimento del 4° elemento al precedente.

Quando un elemento viene aggiunto all'elenco, avviene lo stesso processo, ma al contrario.

Nota quanto meno lavoro dobbiamo fare in un LinkedList rispetto a un ArrayList . E sono solo 5 elementi. Se la nostra lista avesse 100 o più elementi, la superiorità di LinkedList diventerebbe ancora più evidente.

Ma come cambia la situazione se accediamo a un elemento per indice?

Qui è tutto esattamente l'opposto.

Poiché ArrayList è strutturato come un normale array, ottenere qualsiasi elemento in base al suo indice sarà molto semplice per noi. Spostiamo semplicemente il puntatore in un determinato punto e otteniamo l'elemento dalla cella corrispondente.

Ma una LinkedList semplicemente non funziona in questo modo. Dobbiamo esaminare tutti gli elementi dell'elenco per trovare l'elemento con un certo indice.

Proviamo a esprimere tutto questo in termini di grande O?

Iniziamo accedendo a un elemento per indice.

In un ArrayList , ciò avviene in un unico passaggio, indipendentemente dalla posizione dell'elemento nell'elenco. Che sia alla fine o all'inizio.

In questo caso, la complessità temporale sarà O(1) .

In un LinkedList , dobbiamo iterare su un numero di elementi pari al valore dell'indice di cui abbiamo bisogno.

La complessità temporale per tale azione è O(n) , dove n è l'indice dell'elemento di cui abbiamo bisogno.

Qui puoi vedere che il numero che mettiamo tra le parentesi con O grande corrisponde al numero di azioni eseguite.

Conchiglia torniamo a togliere e ad aggiungere?

Iniziamo con LinkedList.

Poiché non è necessario eseguire un gran numero di azioni per aggiungere o rimuovere un elemento e la velocità di questa operazione non dipende in alcun modo da dove si trova l'elemento, la sua complessità è espressa come O(1) e si dice essere costante.

Anche la complessità temporale di questa operazione per ArrayList è O(n) , che chiamiamo complessità lineare.

Negli algoritmi con complessità lineare, il tempo di esecuzione dipende direttamente dal numero di elementi da elaborare. Può anche dipendere dalla posizione dell'elemento, se si trova all'inizio dell'elenco o verso la fine.

La complessità temporale può anche essere logaritmica. Questo è espresso come O(log n) .

Ad esempio, considera un TreeSet ordinato composto da 10 numeri. Vogliamo trovare il numero 2.

Poiché l'elenco è ordinato e non contiene duplicati, possiamo dividerlo a metà e verificare quale metà conterrà il numero desiderato, scartare la parte irrilevante e quindi ripetere questo processo fino a raggiungere l'elemento desiderato. Alla fine, troveremo (o non troveremo) il numero dopo aver elaborato log(n) numero di elementi.

Ecco una tabella che riassume la complessità temporale del resto delle collezioni.

Ora che disponiamo di una tabella che mostra la complessità temporale delle raccolte popolari, possiamo rispondere alla domanda sul perché, tra così tante raccolte, utilizziamo più spesso ArrayList , HashSet e HashMap .

È semplicemente che sono i più efficienti per la maggior parte delle attività :)