Aggiornamento efficiente dei binding in un dizionario .NET

Question

Sto utilizzando un dizionario per accumulare il numero di occorrenze di chiavi e, di conseguenza, l'operazione di base è la scrittura di una coppia valore-chiave in cui il valore è il valore precedente più uno o solo uno se non ci fosse alcun valore precedente. Tuttavia, ciò richiede due operazioni di dizionario separate (lettura e scrittura) quando potrei semplicemente farne una (AddOrUpdate).

Ho notato che il dizionario simultaneo supporta AddOrUpdate ma il normale generico non sembra.

Di conseguenza, un dizionario di riferimenti ad intersezioni mutabili è più veloce. Tuttavia, questo introduce riferimenti non necessari che significano allocazioni di heap e ostacoli di scrittura. Quindi immagino che sia possibile fare molto meglio ma non riesco a vedere come senza riscrivere Dictionary da zero. Ho ragione?

Answer 1

Un aggiornamento dizionario non richiede più ricerche se si sta utilizzando tipi di riferimento:

Diciamo che avete un Dictionary<string, Foo>, dove Foo è un tipo di riferimento e include una proprietà Count:

void UpdateCount(string key) 
{ 
    Foo f; 
    if (dict.TryGetValue(key, out f)) 
    { 
     // do the update 
     ++f.Count; 
    } 
    else 
    { 
     dict[key] = 1; 
    } 
} 

Se i tuoi valori sono tipi di valore ... beh, allora devi occuparti della semantica del tipo di valore. E questo include dover fare due ricerche.

Detto questo, la ricerca del dizionario è abbastanza veloce. Se questo ti sta causando un problema, devi avere un sacco di occorrenze da contare.

Answer 2

Come menzionato da Jim Mischel, è impossibile eseguire una singola ricerca per modificare il valore dell'articolo del dizionario. ConcurrentDictionary.AddOrUpdate metodo di fare più di un'operazione di ricerca (fonti riflesse):

public TValue AddOrUpdate(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory) 
{ 
    TValue local2; 
    if (key == null) 
    { 
     throw new ArgumentNullException("key"); 
    } 
    if (updateValueFactory == null) 
    { 
     throw new ArgumentNullException("updateValueFactory"); 
    } 
    do 
    { 
     TValue local3; 
     while (this.TryGetValue(key, out local3)) 
     { 
      TValue newValue = updateValueFactory(key, local3); 
      if (this.TryUpdate(key, newValue, local3)) 
      { 
       return newValue; 
      } 
     } 
    } 
    while (!this.TryAddInternal(key, addValue, false, true, out local2)); 
    return local2; 
} 

Ho fatto test delle prestazioni con il dizionario simultaneo e semplice ditcionary:

estensione AddOrUpdate per IDictionary:

public static class DictionaryExtensions 
{ 
    public static void AddOrUpdate<TKey, TValue>(this IDictionary<TKey, TValue> dict, TKey key, TValue initValue, Func<TKey, TValue, TValue> updateFunc) 
    { 
     TValue value; 
     value = dict.TryGetValue(key, out value) ? updateFunc(key, value) : initValue; 

     dict[key] = value; 
    } 
} 

Test:

static void Main(string[] args) 
{ 
    const int dictLength = 100000; 
    const int testCount = 1000000; 

    var cdict = new ConcurrentDictionary<string, int>(GetRandomData(dictLength)); 
    var dict = GetRandomData(dictLength).ToDictionary(x => x.Key, x => x.Value); 

    var stopwatch = new Stopwatch(); 
    stopwatch.Start(); 
    foreach (var pair in GetRandomData(testCount)) 
     cdict.AddOrUpdate(pair.Key, 1, (x, y) => y+1);   

    stopwatch.Stop(); 
    Console.WriteLine("Concurrent dictionary: {0}", stopwatch.ElapsedMilliseconds); 

    stopwatch.Reset(); 
    stopwatch.Start(); 

    foreach (var pair in GetRandomData(testCount)) 
     dict.AddOrUpdate(pair.Key, 1, (x, y) => y+1); 

    stopwatch.Stop(); 
    Console.WriteLine("Dictionary: {0}", stopwatch.ElapsedMilliseconds); 
    Console.ReadLine(); 
} 

static IEnumerable<KeyValuePair<string, int>> GetRandomData(int count) 
{ 
    const int constSeed = 100; 
    var randGenerator = new Random(constSeed); 
    return Enumerable.Range(0, count).Select((x, ind) => new KeyValuePair<string, int>(randGenerator.Next().ToString() + "_" + ind, randGenerator.Next())); 
} 

Risultati di analisi su mio ambiente (ms):

ConcurrentDictionary: 2504 
Dictionary: 1351 

Answer 3

si può fare qualcosa di simile:

private class Counter 
{ 
    public string Key  { get ; set ; } 
    public int Frequency { get ; set ; } 
} 

... 

Dictionary<string,Counter> frequencyTable = new Dictionary<string,Counter>() ; 

... 

string someKey = GetKeyToLookup() ; 
Counter item = null ; 
bool hit = frequencyTable.TryGetValue(someKey,out item) ; 
if (!hit) 
{ 
    item = new Counter{ Key=someKey,Frequency=0 } ; 
} 
++ item.Frequency ; 

Se questo non è abbastanza buono, perché scrivere il proprio? Usa le prestazioni elevate C5 Collections Library. È gratuito (originariamente finanziato da Microsoft, infatti), basato sulle interfacce Microsoft System.Collections.Generic e i cui dizionari, set e borse supportano la semantica FindOrAdd().

• Nuget: http://www.nuget.org/packages/C5/
• Progetto pagina: http://www.itu.dk/research/c5/
• La documentazione è ITU-TR-2006-76 — The C5 Generic Collection Library for C# and CLI: Version 1.1.0 of 2008-02-10. È un po 'obsoleto, poiché riflette la versione 1.1 anziché la versione corrente (v2.2 al 27 agosto 2013). Le basi non sono cambiate, però.