Nel progetto (Web) a cui sto lavorando è stata richiesta la visualizzazione di una lista di elementi con le seguenti caratteristiche:
- i nuovi elementi devono essere inseriti all'inizio dell'elenco (i più recenti verranno visualizzati per primi)
- la lista deve contenere al massimo n elementi: l'inserimento di un nuovo elemento, raggiunto il limite n, deve prevedere la rimozione dell'elemento più vecchio presente nella lista (ovvero quello inserito da più tempo)
- l'aggiunta di nuovi elementi è corposa (centinaia di insert al secondo per tutto il ciclo di vita dell'applicazione)
- il limite del numero massimo di elementi che devono essere mantenuti nella lista (n) è relativamente basso (< 10.000)
In pratica, definito un limite di 3 elementi e immaginando l'accodamento dei primi 5 interi in ordine crescente (1, 2, 3, 4 e 5) il risultato atteso è:
12 1
3 2 1
4 3 2
5 4 3
Ho pensato che sia una cosa semplicissima da realizzare in .NET sfruttando le classi in System.Collection.Generic ma... quale usare? Il framework prevede infatti:
List<T>
Lista generica, non utilizzabile allo scopo in quanto non è possibile inserire elementi in posizioni specifiche ma solo "to the end of the List(T)".
In realtà sarebbe possibile effettuare l'inserimento all'inizio della lista effettuando uno shift di tutti gli elementi ma le performance sarebbero improponibili!
Stack<T>
È letteralmente un insieme di elementi "impilati"; possiamo vederlo come una vaschetta portadocumenti sulla scrivania in cui vengono aggiunte delle pratiche (Push) semplicemente appoggiandole sopra e con l'impiegato che le processa che prende (Pop) il primo foglio che trova in cima alla pigna. Non assolve dunque allo scopo in quanto rimuove gli elementi più "nuovi" anziché quelli più "vecchi".
In pratica il seguente codice:
int capacity = 3;
int max = 5;
Stack<int> list = new Stack<int>(capacity);
for (int i = 1; i <= max; i++)
{
if (list.Count >= capacity)
list.Pop();
list.Push(i);
foreach (var item in list)
Console.Write("{0} ", item);
Console.WriteLine();
}Produce:
1
2 1
3 2 1
4 2 1
5 2 1
Non ci siamo.
Queue<T>
È appunto una "coda" dove il primo elemento inserito (Enqueue) è anche il primo a venire rimosso (Dequeue); l'analogia che mi viene in mente è quella delle macchine ferme al casello dell'autostrada: il primo arrivato sarà anche il primo a superare la barriera. Questa collection assolve per metà allo scopo garantendo il corretto meccanismo di in/out ma ha il contro di presentare l'enumerazione degli elementi in ordine inverso rispetto a quanto richiesto (scorrendo la collection ottengo prima gli elementi più "vecchi" e poi quelli più "nuovi")
In pratica il seguente codice:
int capacity = 3;
int max = 5;
Queue<int> list = new Queue<int>(capacity);
for (int i = 1; i <= max; i++)
{
if (list.Count >= capacity)
list.Dequeue();
list.Enqueue(i);
foreach (var item in list)
Console.Write("{0} ", item);
Console.WriteLine();
}Produce:
1
1 2
1 2 3
2 3 4
3 4 5
Non ci siamo ancora ma manca poco :-)
LinkedList<T>
Si tratta di un elenco con doppio collegamento; espone metodi per l'inserimento di nuovi elementi sia all'inizio dell'elenco (AddFirst) che alla fine (AddLast) che in posizioni intermedie (AddAfter e AddBefore), sia per la rimozione (RemoveFirst, RemoveLast, Remove), dandoci la massima flessibilità possibile. In pratica possiamo immaginare questa collection come un trenino giocattolo: possiamo aggiungere o togliere vagoni da entrambe le estremità del convoglio in modo del tutto indifferente.
In pratica il seguente codice:
int capacity = 3;
int max = 5;
LinkedList<int> list = new LinkedList<int>();
for (int i = 1; i <= max; i++)
{
if (list.Count >= capacity)
list.RemoveLast();
list.AddFirst(i);
foreach (var item in list)
Console.Write("{0} ", item);
Console.WriteLine();
}Produce:
1
2 1
3 2 1
4 3 2
5 4 3
Missione compiuta? Sembrerebbe di sì.
Per scrupolo ho fatto un piccolo test di performance, aspettandomi prestazioni simili per Queue e LinkedList:
//
// Performance test configuration
//
DateTime start;
int[] results;
int capacity = 10000;
int max = 1000000000;
//
// LinkedList performance test
//
start = DateTime.Now;
LinkedList<int> list = new LinkedList<int>();
for (int i = 1; i <= max; i++)
{
if (list.Count >= capacity)
list.RemoveLast();
list.AddFirst(i);
}
results = new int[list.Count];
list.CopyTo(results, 0);
foreach (int item in results)
{
// do something with "item"
}
Console.WriteLine("LinkedList: max={0} -> {1}",
max.ToString("#,###"),
DateTime.Now.Subtract(start));
//
// Queue performance test
//
start = DateTime.Now;
results = null;
Queue<int> queue = new Queue<int>(capacity);
for (int i = 1; i <= max; i++)
{
if (queue.Count >= capacity)
queue.Dequeue();
queue.Enqueue(i);
}
results = queue.ToArray();
foreach (int item in results)
{
// do something with "item"
}
Console.WriteLine("Queue: max={0} -> {1}",
max.ToString("#,###"),
DateTime.Now.Subtract(start));Sebbene questo tipo di misurazione sia piuttosto "spannometrico", il risultato (per un miliardo di inserimenti a fronte di una lista con al più 10.000 items) mi ha lasciato basito:
LinkedList: max=1.000.000.000 -> 00:01:17.6770000
Queue: max=1.000.000.000 -> 00:00:30.4030000
Ovvero LinkedList richiede circa 2.5 volte il tempo necessario a Queue!
Conclusioni
Sebbene LinkedList<T> faccia il suo "sporco lavoro" lo fa... troppo lentamente!
Alla fine ho dunque optato per l'utilizzo di Queue<T> con l'aggiunta di poche righe di codice per leggere in modo inverso il contenuto enumerato della lista:
Queue<int> queue = new Queue<int>(capacity);
// (codice omesso)
List<int> temp = new List<int>(queue.ToArray());
temp.Reverse();
results = temp.ToArray();
foreach (int item in results)
{
// do something with "item"
}Infatti il numero di elementi mantenuti nella coda è decisamente troppo basso - meno di 10.000 - per risultare influenti le operazioni di copia in una List e di reverse della lista, anche se molto probabilmente questa porzione di codice potrebbe essere migliorata :-)
PS 1: qualcuno avrà notato l'assenza di acronimi come FIFO (first-in, first-out), LIFO (last-in, first-out), ecc.
Sono stati volutamente omessi perché il significato di "primo" e "ultimo" mi è risultato, leggendo qua e là sul Web, interpretato in modo non del tutto univoco (si riferisce all'ordine di inserimento? alla posizione che assume l'elemento nella collection? ad altro?)
PS 2: un doveroso grazie a Cristian e a Marco che mi hanno supportato sopportato in questa ricerca
rsaccav ha scritto:
Implementare una LIFO che assolva il compito descritto non è assolutamente complesso e certamente più performante rispetto all'utilizzo delle classi standard.
Concordo e ti ringrazio per il suggerimento.
La mia decisione di appoggiarmi a classi già esistenti nasce dalla necessità di avere a disposizioni un po' di interfacce come ad esempio ICollection e ICollection<T> (quindi IEnumerable e IEnumerable<T>) che da riscrivere non sono poi così banali.
Per un'implementazione molto verticale il tuo codice è perfetto ma, se vogliamo avere qualcosa di più... "Generics"
c'è da lavorarci sopra un bel po'. Ad ogni modo la misurazione delle performance che mi dai mi fa venir voglia di sbatterci la testa: appena creo qualcosa di utilizzabile aggiorno il post nel blog.
Grazie ancora per il tip.
Uno dei più interessanti articoli degli ultimi tempi :P
Mi chiedo però se non sarebbe stato interessante eseguire un test anche per verificare la velocità del riordino con l'uso della queue list, tanto per verificare lo scarto finale.
Ma questo magari è dato per scontato e io essendo ignorante come una prugna secca mi faccio il dubbio se è un carino oneroso il riordino di 10.000 elementi ;)
Ancora grazie!!!
padovaboy ha scritto:
Mi chiedo però se non sarebbe stato interessante eseguire un test anche per verificare la velocità del riordino con l'uso della queue list, tanto per verificare lo scarto finale.
L'ho fatto ma non l'ho pubblicato perché risultava immisurabile usando del codice così approssimativo (1) su così pochi elementi (a volte ci metteva meno ad eseguire l'intera operazione di fill della coda + reverse che non senza il riordino...).
Ad ogni modo puoi fare tu stesso un test sulle performance di riordino di una lista riempiendo una List<int> con *molti* elementi (partirei dal milione) ed invocando il metodo Reverse
(1) - i tempi segnalati nel post sono riferiti al mio portatile (Windows Vista Business SP1 32-bit su un Intel Core 2 CPU da 2 GHz con un 2 GB di RAM) e con po' di roba aperta (un paio di VS2008, Outlook, Windows Media Player, ecc.), quindi non hanno la pretesa di essere una misurazione affidabile ma puramente indicativa (comparazione). Le misurazioni sono state ripetute una decina di volta con risultati sempre analoghi.
padovaboy ha scritto:
Uno dei più interessanti articoli degli ultimi tempi
Grazie, troppo buono
Prego. Ma hai davvero avuto la pazienza di leggerlo tutto?
Sì, l'ho trovato esposto molto bene l'argomento, e mi interessa proprio in questi giorni la cosa
m.casati [Staff] wrote:
Prego. Ma hai davvero avuto la pazienza di leggerlo tutto?
uhm, un articolo per winfxitalia sull'uso delle collection?
Daniele Bochicchio ha scritto:
uhm, un articolo per winfxitalia sull'uso delle collection?
Si può fare
Di cosa vuoi che parli di preciso? Descrizione dei vari tipi, performance, casi d'uso pratici, altro?
...e non dirmi "di tutto"!!!!
m.casati [Staff] wrote:
Di cosa vuoi che parli di preciso? Descrizione dei vari tipi, performance, casi d'uso pratici, altro?
sì, una cosa pratica per far capire quale scegliere in base alle esigenze. a cristian credo non dispiacerà se per un attimo prendo il suo posto
..e non dirmi "di tutto"!!!!
no, di tutto non si può
dopo FIFO e LIFO ci manca solo la LIPO, che visto la panza che ho mi farebbe pure comodo
ciao marco
Aggiungi un nuovo commento »»»
Per inserire un commento, devi registrarti alla nostra community.
Stampa 
Download 
10annidi.ASPItalia.com: iscriviti alla competizione e vinci fantastici premi ogni mese!
Implementare una LIFO che assolva il compito descritto non è assolutamente complesso e certamente più performante rispetto all'utilizzo delle classi standard.
Si può certamente migliorare rendendola più performante e utilizzando i generics ma già così com'è è una decina di volte più performante della LinkedList e 2 volte più dello Stack (ma con risultato corretto)
Ecco i risultati sulla mia macchina:
TestLIFOList: 00:00:01.2094512
TestStack: 00:00:02.5131372
TestQueue: 00:00:08.3832176
TestLinkedList: 00:00:14.6959524
public class LIFOList
{
int capacity;
int[] values;
int cursor;
int size;
public LIFOList(int capacity)
{
this.capacity = capacity;
this.values = new int[capacity];
cursor = capacity-1;
size = 0;
}
public void Add(int value)
{
values[cursor--] = value;
if (size < capacity) size++;
if (cursor < 0) cursor = capacity-1;
}
public int[] Values()
{
int[] resValues = new int[size];
int curpos = cursor + 1 == capacity ? 0 : cursor + 1;
Array.Copy(values, curpos, resValues, 0, capacity - curpos);
if (size == capacity && curpos > 0)
{
Array.Copy(values, 0, resValues, capacity - curpos, curpos);
}
return resValues;
}
}
Continua »»» | Rispondi »»»