Sempre riguardo alla famigerata collection v2.0, una delle scelte a cui mi sono trovato davanti è stata quella del container: array o lista dinamica. Le collection del framework come List<T> e derivati usano tutte l'array come container.
La scelta è tutt'altro che ovvia perché naturalmente ciascuna delle due ha i suoi pro e i suoi contro.
Array
- accesso random e sequenziale super-performante
- l'aggiunta di elementi richiede la riallocazione dell'array e il loro travaso (tipo redim tanto per capirci) e quindi molto penalizzante
- la cancellazione elementi richiede di far scalare gli elementi nell'array a meno di non gestirli a macchia di leopardo ma con la necessità prima o poi di ricompattarli (tipo garbage collector)
- Array.Sort provvede già a performanti algoritmi di sorting che uniti a IComparer e/o IComparable permettono il sorting di qualsiasi cosa
Lista dinamica (single/double linked list)
- l'accesso random richiede la navigazione di tutta la lista; quello sequenziale è molto performante
- l'aggiunta di elementi è molto performante
- la cancellazione è molto performante
- non ci sono classi pronte per il sorting ma esistono algoritmi molto performanti anche per le double linked list
Mi sono detto: ok, voglio il meglio e quindi implemento il 90% dei metodi con entrambi i contenitori. Poi quando mi serve una caratteristica per la quale uno dei due container è più performante in assoluto, travaso la lista e la uso. E così ho fatto.
Un giorno (ieri) arrivò il tempo dei benchmark di memoria/performance. E arrivarono pure i dolori. Con l'aiuto di Ants e il Performance explorer di VS2005 mi accorgo che il gioco non vale la candela.
Nelle Add la LinkedList richiede ovviamente l'allocazione anche del LinkedListNode e questo fa crescere a dismisura i tempi rispetto anche al travaso dell'array. Si, perché l'array ovviamente non lo si incrementa di solo un elemento ma di un 30-40% rispetto alla sua dimensione attuale.
Alcune operazioni effettivamente sono performanti con le linked list ma come dicevo prima il gioco non vale la candela.
Nelle Remove il lavoro del GC è superiore e questo penalizza nuovamente. Se anche non ci fosse il GC e fossimo con codice unmanaged ci potremmo trovare con memoria super-frammentata, un problema ben peggiore della perdita di performance.
In conclusione, nonostante tutto quello che si dica sulla bellezza delle linked list, in praticalandia è meglio affidarsi al caro vecchio array. Ovviamente parlo del container di una collection, certamente non di usare un array di Order o altro. Il wrapping fatto da una classe di collection è realmente indispensabile per costruire un object model decente.
Se ripenso all'esame di introduzione ai calcolatori digitali in cui il pezzo forte erano proprio le liste dinamiche ... 