Wydajne aktualizowanie powiązań w słowniku .NET

Question

Używam słownika do gromadzenia liczby wystąpień kluczy, a zatem podstawowa operacja polega na zapisaniu pary klucz-wartość, w której wartość jest poprzednią wartością plus jeden lub tylko jeden, jeśli nie było poprzedniej wartości. Wymaga to jednak dwóch oddzielnych operacji słownikowych (odczyt i zapis), kiedy mógłbym po prostu wykonywać jedną operację (AddOrUpdate).

Zauważam, że słownik współbieżny obsługuje AddOrUpdate, ale zwykły rodzajowy Dictionary nie jest wyświetlany.

W związku z tym słownik odniesień do zmiennych int jest szybszy. Wprowadza to jednak niepotrzebne odniesienia, które oznaczają alokacje sterty i bariery zapisu. Zgaduję, że można zrobić znacznie lepiej, ale nie widzę, jak to zrobić bez przepisywania od podstaw Dictionary. Czy mam rację?

Answer 1

Słownik aktualizacja nie wymaga wiele wyszukiwań jeśli używasz typów referencyjnych:

że masz Dictionary<string, Foo>, gdzie Foo jest typem odniesienia i obejmuje Count właściwość:

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

If twoje wartości są typami wartości ... cóż, wtedy musisz zajmować się semantyką typu wartości. A to obejmuje wykonanie dwóch wyszukiwań.

To powiedziawszy, wyszukiwanie w słowniku jest dość szybkie. Jeśli to powoduje problem, musisz liczyć się z wieloma wystąpieniami.

Answer 2

Jak wspomniał Jim Mischel - nie można wykonać pojedynczego wyszukiwania w celu zmiany wartości elementu słownika. ConcurrentDictionary.AddOrUpdate sposób zrobić więcej niż jedną operację odnośnika (odbicie źródła):

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; 
} 

zrobiłem testu wydajności przy jednoczesnym słownika i prosty ditcionary:

przedłużenie AddOrUpdate dla 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())); 
} 

Wyniki badań moim otoczeniu (MS):

ConcurrentDictionary: 2504 
Dictionary: 1351 

Answer 3

można zrobić coś takiego:

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 ; 

Jeśli to nie jest wystarczająco dobre, to dlaczego napisać własny? Użyj wysokiej wydajności C5 Collections Library. Jest darmowy (początkowo finansowany przez Microsoft), bazuje na interfejsach Microsoft System.Collections.Generic, a ich słowniki, zestawy i torby obsługują semantykę FindOrAdd().

• Nuget: http://www.nuget.org/packages/C5/
• Project Home Page: http://www.itu.dk/research/c5/
• Dokumentacja jest ITU-TR-2006-76 — The C5 Generic Collection Library for C# and CLI: Version 1.1.0 of 2008-02-10. Jest nieco przestarzały, ponieważ odzwierciedla wersję 1.1, a nie aktualną wersję (v2.2 od 27 sierpnia 2013 r.). Podstawy się nie zmieniły.