Dictionary.Add (Key, Value) giderek yavaşlatmak için alternatif mi?

Question

"Artarak" demek istediğim, düşük sayıda tuş olduğunda, Add'un başlangıçta hızlı olmasıdır. Tuşların% 20'sini girdikten sonra, çok yavaş olur. 50% sonra katlanılmaz derecede yavaş olur.

Anahtarın sayısı ne kadar düşük olursa, sözlüğe yeni öğeler eklerken "anahtar çarpışma araması" o kadar hızlı olur. Ancak Dictionary'u korurken bu olumsuzluğu atlamanın herhangi bir yolu var mı? Anahtarların çarpışmamasını önceden bildiğimden, herhangi bir kontrol gerekmez, ancak bu bilgiyi kodda başarıyla kullanmanın bir yolu olup olmadığını bilmiyorum.

BTW Mimarlık yapısından dolayı sözlük yapısını kullanmak zorundayım (bu yapı daha sonra bir db ihracatçısı tarafından yutulur).

---

kodum işe yarar:

var keyList = GetKeyList(); 
var resultDict = new Dictionary<T,T>(); 
foreach (var key in keyList) 
{ 
    resultDict.Add(key,someResult); 
} 

---

Düzenleme: insanlar hash kodu nasıl üretildiğini soruyor beri, bu açıklığa kavuşturmak için çalışacağız.

Teorik olarak, hash kodu oluşturma üzerinde herhangi bir kontrole sahip değilim, çünkü maalesef aynı db'ye bağlı birden fazla sistem arasında bir sözleşme kullanıyor. Pratikte, karma kodu üreten kod parçası gerçekten benim kodumdur (yasal uyarı: bu, jenerasyonda kullanılan konvansiyonu seçmemek değildi).

anahtar nesil daha yolu daha karmaşıktır, ama hepsi bu kadar aşağı kaynar:

private List<ResultKey> GetKeyList(string prefix, List<float> xCoordList, List<float> yCoordList) 
{ 
    var keyList = new List<ResultKey>(); 
    var constantSensorName = "xxx"; 
    foreach (float xCoord in xCoordList) 
    { 
     foreach (float yCoord in yCoordList) 
     { 
      string stationName = string.Format("{0}_E{1}N{2}", prefix, xCoord, yCoord); 
      keyList.Add(new ResultKey(constantSensorName, stationName)); 
     } 
    } 
    return keyList; 
} 

public struct ResultKey 
{ 
    public string SensorName { get; set; } 
    public string StationName { get; set; } 

    public ResultKey(string sensorName, string stationName) 
    { 
     this.SensorName = sensorName; 
     this.StationName = stationName; 
    } 
} 

Answer 1

:

public class FakeFastDictionary<TKey, TValue> : Dictionary<TKey, TValue> 
{ 
    protected IList<KeyValuePair<TKey, TValue>> _list 
     = new List<KeyValuePair<TKey, TValue>>(); 

    public new void Add(TKey key, TValue value) 
    { 
     _list.Add(new KeyValuePair<TKey, TValue>(key, value)); 
    } 

    public new ICollection<TValue> Values 
    { 

     get 
     { 
      // there may be faster ways to to it: 
      return _list.Select(x => x.Value).ToArray(); 
     } 
    } 

    public new ICollection<TKey> Keys 
    { 
     get 
     { 
      // there may be faster ways to to it: 
      return _list.Select(x => x.Key).ToArray(); 
     } 
    } 
} 

Bu

çalışan bir örneğidir. The default hash code generation for structs is disappointingly bad. Burada yapmanıza güvenemezsiniz çünkü yapınız kötü bir durumu tetikleyen iki dizeyi içerir (bağlantılı cevaba bakın). Aslında, sadece SensorName alanınız onu karma kod haline getiriyor, başka bir şey değil. Bu, tüm SensorName numaralı anahtarların çarpışmasına neden olur.

Kendi fonksiyonunuzu yazın. Çabuk birini kullanarak Resharper üretilen:

public struct ResultKey : IEquatable<ResultKey> 
{ 
    public string SensorName { get; set; } 
    public string StationName { get; set; } 

    public ResultKey(string sensorName, string stationName) 
    { 
     this.SensorName = sensorName; 
     this.StationName = stationName; 
    } 

    public bool Equals(ResultKey other) 
    { 
     return string.Equals(SensorName, other.SensorName) && string.Equals(StationName, other.StationName); 
    } 

    public override bool Equals(object obj) 
    { 
     if (ReferenceEquals(null, obj)) return false; 
     return obj is ResultKey && Equals((ResultKey)obj); 
    } 

    public override int GetHashCode() 
    { 
     unchecked 
     { 
      return ((SensorName != null ? SensorName.GetHashCode() : 0)*397)^(StationName != null ? StationName.GetHashCode() : 0); 
     } 
    } 

    public static bool operator ==(ResultKey left, ResultKey right) 
    { 
     return left.Equals(right); 
    } 

    public static bool operator !=(ResultKey left, ResultKey right) 
    { 
     return !left.Equals(right); 
    } 
} 

Answer 2

akla gelen ilk şey, kendi karma işlevi yaratmaktır. Sözlüğe Ekleme yöntemi, yapıya eklemek için gittiğinde getHashCode() yönteminin varsayılan uygulamasını çağırır. Anahtarlarınızın etrafına bir sarıcı sınıf koyarsanız ve getHashCode() yönteminin üzerine yazdıysanız, muhtemelen daha az çarpışma eğilimli bir hash işlevi uygulayabilecek kendi karma işlevinizi yazabilirsiniz.

Answer 3

Yalnızca API gereksinimlerini karşılamak ve kirli bir çözüme ihtiyacınız varsa, kendi sözlüğünüzü uygulayabilirsiniz. Eğer yapı ResultKey için varsayılan hash kodu nesil kullanıyorsunuz https://dotnetfiddle.net/BDyks0

Answer 4

Kişisel ResultKey iki dizeleri içeren, böylece onları birleştiren bir hashcode gerekir.

"How do I calculate a good hash code for a list of strings?" bunun nasıl yapılacağını gösteren bazı yanıtlar içerir.

Ancak

public override int GetHashCode() 
{ 
    return (SensorName + StationName).GetHashCode(); 
}