Cập nhật ràng buộc hiệu quả trong từ điển .NET

Question

Tôi đang sử dụng từ điển để tích lũy số lần xuất hiện của khóa và do đó, hoạt động chính là viết cặp khóa-giá trị trong đó giá trị là giá trị trước đó cộng với một hoặc chỉ nếu không có giá trị trước đó. Tuy nhiên, điều này đòi hỏi hai hoạt động từ điển riêng biệt (đọc và ghi) khi tôi chỉ có thể làm một (AddOrUpdate).

Tôi nhận thấy rằng từ điển đồng thời hỗ trợ AddOrUpdate nhưng thông thường chung chung Dictionary không xuất hiện.

Do đó, từ điển tham chiếu đến int có thể thay đổi sẽ nhanh hơn. Tuy nhiên, điều này giới thiệu tài liệu tham khảo không cần thiết có nghĩa là phân bổ đống và viết các rào cản. Vì vậy, tôi đoán nó có thể làm tốt hơn đáng kể nhưng tôi không thể nhìn thấy như thế nào mà không cần viết lại Dictionary từ đầu. Tôi có đúng không?

Answer 1

Một cập nhật từ điển không đòi hỏi nhiều tra cứu nếu bạn đang sử dụng các loại tài liệu tham khảo:

Giả sử bạn có một Dictionary<string, Foo>, nơi Foo là một loại tài liệu tham khảo và bao gồm một tài sản Count:

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

Nếu giá trị của bạn là các loại giá trị ... tốt, sau đó bạn phải đối phó với ngữ nghĩa loại giá trị. Và điều đó bao gồm việc phải thực hiện hai lần tra cứu.

Điều đó nói rằng tra cứu từ điển khá nhanh chóng. Nếu điều này gây ra cho bạn một vấn đề, bạn phải có rất nhiều lần xuất hiện để đếm.

Answer 2

Như Jim Mischel đã đề cập - không thể thực hiện tra cứu đơn lẻ để thay đổi giá trị mặt hàng của từ điển. ConcurrentDictionary.AddOrUpdate phương pháp làm nhiều hơn là một hoạt động tra cứu (nguồn phản ánh):

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

Tôi đã thực hiện thử nghiệm hiệu suất với từ điển đồng thời và ditcionary đơn giản: mở rộng AddOrUpdate

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

Kiểm tra:

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

Kết quả thử nghiệm trên môi trường của tôi (mili giây):

ConcurrentDictionary: 2504 
Dictionary: 1351 

Answer 3

Bạn có thể làm một cái gì đó như thế này:

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 ; 

Nếu đó là không đủ tốt, tại sao viết của riêng bạn? Sử dụng hiệu suất cao C5 Collections Library. Nó hoàn toàn miễn phí (ban đầu được Microsoft tài trợ, trên thực tế), được xây dựng trên các giao diện System.Collections.Generic của Microsoft và có các bộ từ điển, bộ và túi hỗ trợ FindOrAdd() ngữ nghĩa.

• NuGet: http://www.nuget.org/packages/C5/
• Project Home Page: http://www.itu.dk/research/c5/
• Các tài liệu là ITU-TR-2006-76 — The C5 Generic Collection Library for C# and CLI: Version 1.1.0 of 2008-02-10. Đó là một chút lỗi thời, vì nó phản ánh v1.1.1 chứ không phải phiên bản hiện tại (phiên bản v2.2 kể từ ngày 27 tháng 8 năm 2013). Tuy nhiên, cơ bản vẫn chưa thay đổi.