martedì 8 febbraio 2011

Dizionari, Lookup e Dizionari Ordinati di oggetti in C#

Il linguaggio C# supporta una vasta gamma di collezioni di oggetti. Alcune di queste strutture dati sono funzionano come delle mappe hash con chiave valore, ad accesso rapido:

- Dictionary: struttura del tipo<chiave, valore>, a ciascuna chiave corrisponde un singolo valore
- Dictionary Lookup: come il Dictionary, ma a ciascuna chiave possono corrispondere più valori
- Sorted Dictionary: come il Dictionary, ma è ordinato.

Quando usare un Dictionary? In pratica è conveniente usarlo in tutti in quei casi che si hanno dati nella forma chiave - valore e si vuole un accesso veloce. In pratica a ciascuna chiave viene fatto corrispondere un valore
univoco (hash), a valori simili corrispondono valori hash molto diversi e la distribuzione dei valori hash deve essere uniforme.

Non abbiamo particolari restrizioni sugli oggetti usabili come valori di un Dictionary, ma le si hanno invece per gli oggetti che dobbiamo usare come chiavi. Una chiave di un Dictionary deve essere comparabile, o meglio deve derivare dalla interfaccia IEquatable e implementare il metodo
Equals.

Questo perchè altrimenti verrebbe usato il metodo Equals della classe Object che restituisce true solo se l'oggetto da comparare è l'oggetto stesso. Un altro metodo fondamentale che si deve implementare per l'oggetto da usare per la chiave è
GetHashCode() che restituisce il codice hash che come detto deve far corrispondere valori diversi per chiavi diverse.

Si noti che se usiamo come chiave un oggetto String, non abbiamo bisogno di reimplementare alcun metodo poichè questi sono già implementati nella classe. Anche la classe Int32 sovrascrive Equals() e
GetHashCode() implementando IEquatable, ma quest'ultimo non soddisfa la proprietà di distribuire uniformemente i valori di hash poichè restituisce il valore stesso (ad es. se Int32 key = 10, key.GetHashCode() restituisce 10).

Vediamo un esempio d'uso di Dictionary:

var employees = new Dictionary<EmployeeId,Employee>(100); //Dictionary iniziale di 100 elementi

dove
EmployeeId è definita come

public struct EmployeeId : IEquatable<EmployeeId>{
  ...
  private readonly int number;
  public EmployeeId(string id)
  {
    if (id == null) throw new ArgumentNullException("id");
    number = int.Parse(id);
    ...
  }

  public bool Equals(EmployeeId other) 
 
  {         
     //i due Employee sono uguali se il campo number è uguale
     if (other == null) return false;
       return (number == other.number);
  }
    


  public override int GetHashCode()     
  {        
    //questa funzione è arbitraria ma deve essere di tipo hash
    return ((int)number ^ (int)(number >> 32)); 
  } 

 ...  
}

Per aggiungere elementi al Dictionary si può usare il metodo Add(chiave,valore), mentre per cercare un valore si può usare il metodo TryGetValue(chiave, out valore)) che restituisce false se l'elemento non
è presente, oppure si usa Contains(chiave) (senza farsi restuire il valore). Il metodo
Remove(chiave) serve invece per eliminare degli elementi.

Un Dictionary Lookup è simile al Dictionary, ma supporta più valori con la stessa chiave. A differenza del Dictionary non c'è una classe "contenitore ad hoc" ma ne viene sfruttata una già esistente, inoltre gli elementi vengono aggiunti mediante il metodo
ToLookup()che restituisce un oggetto Lookup < TKey, TElement >. Il metodo ToLookup accetta un delegato che serve per selezionare la chiave.
Per esempio:

var racers = new List <Racer > ();
racers.Add(new Racer("Jacques", "Villeneuve","Canada", 11));
racers.Add(new Racer("Alan", "Jones","Australia", 12));
racers.Add(new Racer("Jackie", "Stewart", "United Kingdom", 27));
racers.Add(new Racer("James", "Hunt", "United Kingdom", 10));
racers.Add(new Racer("Jack", "Brabham", "Australia", 14));
var lookupRacers = racers.ToLookup(r = > r.Country);

Crea una Lookup in cui la chiave risulta il campo Country della classe Racer.
Si noti come ToLookup venga chiamato come un metodo di List.

Per selezionare gli elementi usiamo l' accesso alla lista per mezzo della chiave:

foreach (Racer r in lookupRacers["Australia"])
{
  Console.WriteLine(r);
}
  
Si noti che l'accesso alla lista è di tipo hash! Il metodo ToLookup è disponibile in tutte le classi C# che implementano l'interfaccia
IEnumerable < T >.

Infine il
SortedDictionary < TKey, TValue > non è altro che un albero binario ordinato in cui ciascuna chiave deve implementare IComparable < TKey >.
SortedDictionary<string, string> dic = 
new SortedDictionary<string, string>();
...
 

Per approfondimenti vedi:

Dictionary (classe) : http://msdn.microsoft.com/it-it/library/xfhwa508(v=vs.80).aspx
Lookup: http://msdn.microsoft.com/en-us/library/bb460184.aspx
SortedDictionary: http://msdn.microsoft.com/it-it/library/f7fta44c.aspx

0 commenti:

Posta un commento

Recent Posts

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | cna certification