RollingList
Nel post precedente ho parlato di come utilizzare le classi di base del framework per realizzare una collection con le seguenti caratteristiche:
- all'inserimento di un nuovo elemento questo viene posizionato all'inizio della lista (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)
- garantire ottime performance
Il commento di rsaccav mi ha fatto convinto ad implementare una collezione generica "from scratch", così da colmare il vuoto lasciato in System.Collection.Generic.
Con estrema fantasia l'ho battezzata RollingList<T>
Il principio è piuttosto semplice: la lista si basa su un array con dimensione fissa pari al limite di elementi da conservare (Capacity; la proprietà deve essere impostata nel costruttore o comunque *prima* dell'inserimento del primo elemento) associato ad un cursore (backward) che definisce la posizione di inserimento/sostituzione e che consente di enumerare gli elementi nell'ordine corretto.
Il codice completo della classe:
using System;
using System.Collections;
using System.Threading;
public class RollingList<T> : ICollection
{
private int _cursor;
private int _size;
private int _capacity;
private T[] _items;
private object _syncRoot;
public RollingList(int capacity)
{
Capacity = capacity;
}
public int Capacity
{
get { return _capacity; }
set
{
if (value <= 0)
throw new ArgumentOutOfRangeException("value", "Capacity must be greater than zero");
if (_capacity > 0)
throw new ArgumentException("Capacity has just been defined", "value");
_capacity = value;
_items = new T[_capacity];
_cursor = (_capacity - 1);
}
}
public void Add(T item)
{
if (_capacity <= 0)
throw new NotSupportedException("Capacity is not greater than zero");
_items[_cursor--] = item;
if (_size < _capacity)
_size++;
if (_cursor < 0)
_cursor = (_capacity - 1);
}
public void Clear()
{
Array.Clear(_items, 0, _size);
_size = 0;
_cursor = (_capacity - 1);
}
public T[] ToArray()
{
T[] destinationArray = new T[_size];
if (_size == 0)
return destinationArray;
int cursorPosition = (_cursor + 1 == _capacity) ? 0 : _cursor + 1;
Array.Copy(_items, cursorPosition, destinationArray, 0, (_capacity - cursorPosition));
if (_size == _capacity && cursorPosition > 0)
Array.Copy(_items, 0, destinationArray, (_capacity - cursorPosition), cursorPosition);
return destinationArray;
}
public void CopyTo(Array array, int index)
{
Array.Copy(ToArray(), 0, array, index, _size);
}
public int Count
{
get { return _size; }
}
public bool IsSynchronized
{
get { return false; }
}
public object SyncRoot
{
get
{
if (_syncRoot == null)
{
Interlocked.CompareExchange(ref _syncRoot, new object(), null);
}
return _syncRoot;
}
}
public IEnumerator GetEnumerator()
{
return ToArray().GetEnumerator();
}
}Questa implementazione è sicuramente migliorabile (ad esempio, oltre a ICollection potrebbe essere utile implementare l'interfaccia ICollection<T>, supportare la serializzazione, ecc.) ma è decisamente preferibile rispetto all'uso di Stack<T>, Queue<T> o LinkedList<T> in quanto:
- semplifica il codice di inserimento di elementi (le operazioni di IN/OUT al raggiungimento della capacità massima definita sono gestite dalla collection stessa, quindi non richiedono codice di controllo aggiuntivo)
- semplifica la lettura grazie ad una corretta enumerazione nativa degli elementi
- permette di avere performance notevolmente più elevate:
//
// RollingList performance test
//
int capacity = 10000;
int max = 1000000000;
DateTime start = DateTime.Now;
RollingList<int> list = new RollingList<int>(capacity);
for (int i = 1; i <= max; i++)
{
list.Add(i);
}
foreach (int item in list)
{
// do something with "item"
}
Console.WriteLine("RollingList: max={0} -> {1}",
max.ToString("#,###"),
DateTime.Now.Subtract(start)); Produce:
RollingList: max=1.000.000.000 -> 00:00:11.5610000
Ovvero un tempo di esecuzione che è circa un terzo rispetto a Queue<T>!!!
HTH
Per inserire un commento, devi avere un account.
Fai il login e torna a questa pagina, oppure registrati alla nostra community.
- Enumeratori: flags and extensions, il 17 febbraio 2010 alle 23:38
- .NET Framework 4.0 beta 2: Visual Studio 2010, il 19 ottobre 2009 alle 21:23
- .NET Framework 4.0 beta 1: Visual Studio 2010 e Training Kit disponibili per tutti, il 21 maggio 2009 alle 09:25
- .NET Framework 4.0 beta 1: Visual Studio 2010, il 18 maggio 2009 alle 16:39
- L'ordine dei parametri in alcune classi del framework, il 21 agosto 2008 alle 18:47
- The Developer Highway Code, il 19 agosto 2008 alle 14:19