當試圖更新一個類型的字典時，防止雙重哈希操作Dictionary <IComparable，int>

我正在研究與化學公式密切相關的科學研究軟件。我使用內部的Dictionary<Isotope, int>跟蹤化學式的內容，其中Isotope是「碳-13」，「氮-14」之類的對象，並且int代表化學式中這些同位素的數量。所以公式C2H3NO會存在這樣的：當試圖更新一個類型的字典時，防止雙重哈希操作Dictionary <IComparable，int>

{"C12", 2 
"H1", 3 
"N14", 1 
"O16", 1}

這是所有罰款和花花公子，但是當我要添加兩種化學公式放在一起，我最終不得不計算Isotope哈希函數兩次更新值，請參閱後續代碼示例。

public class ChemicalFormula { 
    internal Dictionary<Isotope, int> _isotopes = new Dictionary<Isotope, int>(); 

    public void Add(Isotope isotope, int count) 
    { 
     if (count != 0) 
     { 
      int curValue = 0; 
      if (_isotopes.TryGetValue(isotope, out curValue)) 
      { 
       int newValue = curValue + count; 
       if (newValue == 0) 
       { 
        _isotopes.Remove(isotope); 
       } 
       else 
       { 
        _isotopes[isotope] = newValue; 
       } 
      } 
      else 
      { 
       _isotopes.Add(isotope, count); 
      } 
      _isDirty = true; 
     } 
    } 
}

雖然這可能看起來不是這將是一個緩慢的下降，它是當我們增加十億化學式一起，這種方法是一致的程序（>的運行時間的45％的最慢的部分）。我正在處理像「H5921C3759N1023O1201S21」這樣的大型化學公式，這些化學公式一直通過較小的化學公式加入。

我的問題是，是否有更好的數據結構來存儲這樣的數據？我試圖創建一個簡單的IsotopeCount對象，其中包含一個int，所以我可以訪問引用類型（而不是值類型）中的值以避免雙重散列函數。但是，這似乎並不有利。

編輯 Isotope是不可變的，程序的生命週期內應該不會改變，所以我應該能夠緩存的哈希碼。

我已經鏈接到source code，所以你可以看到更深入的類，而不是我複製和粘貼在這裏。

來源

2012-07-30 Moop

我第二個意見認爲Isotope應該用預先計算的散列做成不可變的。這會讓一切變得更簡單。

（事實上，在功能上，面向對象編程更適合於這種排序的計算，並將其與不可變對象待遇）

來源

2012-07-30 20:01:21

我同意你和@jonskeet關於緩存「同位素」的哈希碼，這對性能有一點幫助。但我認爲減速是詞典的內部因素，我正在尋找避免重複調用訪問內存中相同位置的方法。 – Moop 2012-07-30 21:02:55

如果您針對性能進行優化（並且不關心內存使用情況），則可以爲每個同位素分配一個唯一的'int'索引，該索引將用作'int'數組索引。你將在每一個公式中使用更多的內存，但是數組訪問會更快。 – 2012-07-30 21:09:06

這是一個有趣的想法。正如其他用戶所指出的那樣，我將重點關注一些我會一直使用的「同位素」（即C，N，H，O，S，P），並且可以爲這些獨特的'int '值（即0 - 20）。所有其他同位素我可以分配一個更大的獨特'int'，如果用戶添加了一個不尋常的元素，例如'Hf'，我只需調整內部的int []'數組來調整它。這應該可以節省內存並提高性能。 – Moop 2012-07-31 18:37:42

我已經嘗試創建一個簡單的IsotopeCount對象，它包含一個int，所以我可以在引用類型（而不是值類型）中訪問該值以避免雙重哈希函數。但是，這似乎並不有利。

那麼它會阻止雙散列......但顯然它在空間方面更糟糕。 做什麼性能差異你注意到了？

如果你這麼做的話，你應該強烈考慮的另一個選擇是在Isotope類中緩存散列，假設它是不可變的。（如果不是，那麼將它用作字典鍵至少有點令人擔憂）。

如果您可能使用大多數Isotope值作爲字典鍵（或候選），那麼在初始化過程中可能需要計算散列值。否則，選擇一個特別不可能的哈希值（在理想的世界中，這可能是任何值），並將其用作「未緩存」的值，然後對其進行懶惰計算。

如果你在GetHashCode有45％的運行時間，你看過優化嗎？究竟是GetHashCode還是Equals這是問題所在？（請您談一下「散列」，但我懷疑你的意思是「一般的哈希查找」。）

如果你能發佈Isotope類型中的相關內容，我們也許能幫助更多。

編輯：的另一個選項考慮如果您使用.NET 4將是ConcurrentDictionary，其AddOrUpdate方法。您使用的字典作爲關聯與價值的關鍵手段

public void Add(Isotope isotope, int count) 
{ 
    // I prefer early exit to lots of nesting :) 
    if (count == 0) 
    { 
     return 0; 
    } 

    int newCount = _isotopes.AddOrUpdate(isotope, count, 
             (key, oldCount) => oldCount + count); 
    if (newCount == 0) 
    { 
     _isotopes.Remove(isotope); 
    } 
    _isDirty = true; 
}

來源

2012-07-30 19:51:42

感謝您的提示和想法（提前退出I a格力與！）。我使用'IsotopeCount'包裝器（〜5-7％）獲得稍好的性能，但以內存爲代價並增加了複雜性，所以我認爲這不會有好處。我現在在創建'同位素'的時候計算了我自己的哈希函數，這對我有所幫助。我也忽略了'.Equals（）'方法來簡化和加快平等比較。我已經嘗試過'ConcurrentDictionary'，但是這帶來了很大的性能下降（我認爲是由於額外的鎖定和線程安全性）。 – Moop 2012-07-31 18:34:11

你真的需要對同位素隨機存取按類型計數或：你會使用這樣的？

我猜想後者。

我給你的建議是不是一本字典，但與IsotopeTuples的有序數組（或列表），類似的工作：

class IsotopeTuple{ 
    Isotope i; 
    int count; 
}

由名同位素排序。

爲什麼排序？因爲如此，當你想將兩個同位素「添加」在一起時，你可以通過遍歷兩個數組來做到這一點（希望這很清楚，如果需要，我可以詳細說明）。不需要哈希計算，只需要快速比較訂單。

這是處理矢量乘法時經典的方法，其中維度是單詞。在文本挖掘中廣泛使用。

權衡當然是初始向量的構造是（n）log（n），但我懷疑你是否會感受到這種影響。

來源

2012-07-30 20:00:08 Vitaliy

我確實有一些使用隨機訪問「同位素」的方法，但我可能會重寫那些。我可以讓'Isotope：IComparable '來處理排序的列表。我可能會嘗試這個並回來。 – Moop 2012-07-30 20:51:15

我最初嘗試做一個'SortedList '並橫切兩個數組，但遇到了在嵌套循環中修改Value集合的問題，所以這不起作用。我轉移到了標準（非泛型）'SortedList'並添加了所需的演員表並且它可以工作，但是在'Dictionary '方法的表現最差。最後，我嘗試了一個'List '像你所建議的，但被迫一直調用'list。Sort（）'確保它被排序，並最終導致性能問題。感謝您的建議，但 – Moop 2012-07-31 18:29:42

爲什麼你必須不斷地添加東西到列表中？你能詳細說明用例嗎？你是如何實現比較器的？ – Vitaliy 2012-07-31 20:02:52

，你能想到的，如果你有同位素的數量有限，而且沒有記憶的另一種解決方案問題：

public struct Formula 
{ 
    public int C12; 
    public int H1; 
    public int N14; 
    public int O16; 
}

我猜你正在尋找有機化學，所以你可能沒有處理許多同位素，如果查找的問題，這將是一個非常快...

來源

2012-07-30 20:14:24

我編寫了處理所有元素（> 100）和同位素（> 1,000）的代碼，以至於幾乎不可能像您所描述的那樣，尤其是.Add方法。但我同意，這是一個非常簡單的公式，可以快速高效地進行。 – Moop 2012-07-30 20:57:27

當試圖更新一個類型的字典時，防止雙重哈希操作Dictionary <IComparable，int>

回答

相關問題