Come tutti sapete Granville Barnett e Luca del Tongo stanno lavorando alla realizzazione di una libreria open-source di strutture dati e algoritmi (DSA) con lo scopo di arricchire le funzionalità offerte dalla libreria di base del framework 3.5 (BCL). Sono molto interessato all'evoluzione del progetto, per questo ho scaricato l'attuale release 0.6 ed ho iniziato a studiarla attentamente (segnalo anche la presenza di un eBook scritto dagli stessi autori per meglio comprendere gli algoritmi implementati). Sono rimasto piacevolmente colpito dalla pulizia e chiarezza del codice di implementazione e soprattutto dallo sforzo impiegato a mantenere intuitivo l'utilizzo della libreria (molti metodi e proprietà infatti hanno nomi analoghi a quelli implementati da Microsoft ma non è certo solo in questo lo sforzo).
Come sottolineano gli stessi autori l'aspetto più critico quando le performance sono importanti è saper scegliere le strutture dati e gli algoritmi migliori nel particolare contesto applicativo. In questo post voglio mostrarvi i risultati che ho ottenuto dalla mia analisi delle strutture dati di tipo lista non ordinata presenti nella BCL e nella libreria DSA.
Le strutture dati presenti nella BCL che ho coinvolto sono:
- List
- LinkedList
- Stack
- Queue
Le strutture dati presenti nella libreria DSA che ho coinvolto sono:
- SinglyLinkedList
- DoublyLinkedList
- Deque
Prima di mostrare i risultati ottenuti è bene sottolineare quando è opportuno scegliere il tipo di dati lista non ordinata all'interno di una applicazione. Generalmente si sceglie una lista non ordinata quando si desiderano effettuare le seguenti operazioni:
- Inserimento di elementi (senza un ordinamento particolare)
- Rimozione di elementi
- Enumerazione degli elementi
Ho voluto quindi testare la velocità di esecuzione dei seguenti metodi:
- AddLast() : inserimento di un elemento in coda alla lista
- AddFirst() : inserimento di un elemento in testa alla lista
- RemoveLast() : rimozione dell'elemento in coda alla lista
- RemoveFirst() : rimozione dell'elemento in testa alla lista
- Remove() : rimozione di un elemento con un certo valore
Di seguito riporto i risultati ottenuti considerando che ogni metodo è stato eseguito 100 Mila volte:
Considerazioni su AddLast():
- List è sicuramente la struttura dati più veloce; Il motivo è certamente dovuto al fatto che la sua implementazione interna sfrutta un vettore a crescita dinamica; Questo vettore di appoggio viene rilocato con dimensioni doppie nel momento in cui non è più disponibile spazio al suo interno; Anche Stack e Queue utilizzano al loro interno un meccanismo analogo.
- SinglyLinkedList e DoublyLinkedList hanno più o meno prestazioni analoghe fra loro e sono migliori della LinkedList del framework; E' importante precisare che la classe LinkedList del framework è implementata come una coda doppia, allo stesso modo di DoublyLinkedList, però in ogni nodo viene memorizzato anche un riferimento alla lista. L'aggiornamento di questo valore per ogni nodo è probabilmente la causa di tale perdita di performance. Qualcuno sa perchè hanno messo questo riferimento in ogni nodo ?
- Deque infine è semplicemente un Facade sulla classe DoublyLinkedList. Mi sembra molto strano che le sue prestazioni siano leggermente migliori a DoublyLinkedList considerando il fatto che al suo interno la classe Deque è costretta ad aggiornare il valore di un altro contatore.
Considerazioni su AddFirst():
- Sicuramente nel caso in cui si devono fare frequentemente operazioni di questo tipo la scelta migliore risiede in SinglyLinkedList, DoublyLinkedList o Deque.
- LinkedList del framework (per il motivo detto prima) ha prestazioni inferiori
- List è inefficiente negli inserimenti in testa (e in generale in quelli interni) proprio perchè ciascuna operazione forza uno spostamento di tutti gli elementi successivi
Considerazioni su RemoveLast():
- SinglyLinkedList è inefficiente per costruzione. Infatti la monodirezionalità obbliga a scorrere tutta la lista per rimuovere l'ultimo elemento.
Considerazioni su RemoveFirst():
- SinglyLinkedList e DoublyLinkedList hanno più o meno prestazioni analoghe sempre migliori della controparte LinkedList del framework.
Considerazioni su Remove():
- List per questo tipo di operazione è efficiente proprio perchè sfrutta la memorizzazione tramite array.
- Le altre implementazioni infatti richiedono lo scorrimento dell'intera lista ad ogni operazione.
In generale mi sento di tirare queste conclusioni:
- Utilizzare Stack quando si ha bisogno di una struttura dati di tipo LIFO
- Utilizzare Queue quando si ha bisogno di una struttura dati di tipo FIFO
- Utilizzare SinglyLinkedList se si preferisce una struttura dati Queue implementata tramite coda. Le prestazioni sono di poco inferiori a Queue ma in caso di grossi elementi può portare ad una maggiore efficienza in termini di memoria occupata (si consideri il costo di raddoppiare il vettore nell'implementazione di Queue). Probabilmente questa mia considerazione andrebbe in qualche modo provata, sicuramente ci sarà un motivo per cui è stata rimossa l'implementazione di Queue nelle ultime release di DSA (Forse per non creare ulteriore confusione).
- SinglyLinkedList in generale conviene usarla quando si ha necessità di scorrere gli elementi in una sola direzione.
- DoublyLinkedList si deve utilizzare quando si ha necessità di scorrere gli elementi in entrambe le direzioni.
- A mio parere Deque non ha molto senso di esistere perchè le funzionalità offerte sono tutte ottenibili sfruttando una DoublyLinkedList. In pratica utilizzare direttamente DoublyLinkedList dovrebbe anche essere più efficiente (anche se i dati non sembrano dimostrarlo).
- LinkedList del framework sembra uscire perdente da questa mia analisi. Bisogna capire perchè ha senso inserire il riferimento alla lista in ciasun nodo !
- List è senz'altro la soluzione migliore quando si devono inserire tanti elementi uno in coda all'altro, effettuare delle rimozioni per valore e quindi delle enumerazioni sugli elementi