協調3個列表的最佳算法

我正在尋找一種方法來協調來自3個不同來源的元素。我簡化了元素只有一個鍵（字符串）和版本（長）。協調3個列表的最佳算法

該列表同時獲得（2個來自單獨的數據庫查詢，1個來自另一個系統上的內存緩存）。

對於我的最終結果，我只關心所有3個來源中不完全相同的元素。所以我關心的結果是一個鍵列表，每個系統都有相應的版本。

Element1 | system1:v100 | system2:v100 | system3:v101 | 
Element2 | system1:missing | system2:v200 | system3:v200 |

並且可以丟棄具有相同版本的元素。

實現這一目標的2種方式我認爲是

等待所有數據源完成檢索，並且不是通過每個列表循環聚集的主列表與鍵+所有3個版本的工會（丟棄所有相同的項目）。
第一個列表完成檢索後，將其放入併發集合（如字典（在.net 4.0中提供））中，並在剩餘列表（在併發集合中）一旦可用。

我的想法是，第二種方法會快一點，但可能不會太多。直到所有3種來源都存在，我才能真正做到很多，所以從第二種方法中獲得的並不多，引入了爭用。

也許還有其他方法可以解決這個問題嗎？另外，由於版本是使用long來存儲的，並且會有數百個（可能是數百萬）元素，因此可能會關注內存分配（可能不是一個大問題，因爲這些對象很短）

來源

2012-10-18 Sonic Soul

是否所有的列表都有相同的大小，位置'我'持有第i個元素的版本？ –

no ..更多的時候，他們會有不同的大小。取決於哪個版本是不同的（或缺失），這可能是好的，或警告的理由。 –

和項目的順序也會有所不同..我可以添加排序當然，但不能依賴該指標將是所有項目相同。 –

HashSet是選擇，因爲它擁有聯盟和Intersect方法

HashSet.UnionWith Method

要使用這個，你必須重載Equals和GetHashCode。
一個好的（獨特的）散列是性能的關鍵。

如果版本全是v，那麼數字可以使用數字來構建缺少0的散列。
如果版本爲Int10或更低版本，則可以使用Int32創建完美散列。

另一種選擇是ConcurrentDictionary（沒有併發HashSet）並且有三個feed。
仍然需要覆蓋Equals和GetHashCode。
我的直覺是三個HashSets然後聯盟會更快。

如果所有的版本都是數字，你可以使用0作爲缺失，那麼可以直接打包到UInt32或UInt64中，然後直接把它放在HashSet中。 Union在解包之後。使用位推動< <而不是數學打包解壓縮。

這只是兩個UInt16，但它在2秒內運行。
這將比哈希類更快。

如果所有三個版本都很長，那麼HashSet <integral type>將不是一個選項。
long1^long2^long3;可能是一個很好的散列，但這不是我的專業知識。
我知道Tuple上的GetHashCode是不好的。

class Program 
{ 
    static void Main(string[] args) 
    { 
     HashSetComposite hsc1 = new HashSetComposite(); 
     HashSetComposite hsc2 = new HashSetComposite(); 
     for (UInt16 i = 0; i < 100; i++) 
     { 
      for (UInt16 j = 0; j < 40000; j++) 
      { 
       hsc1.Add(i, j); 
      } 
      for (UInt16 j = 20000; j < 60000; j++) 
      { 
       hsc2.Add(i, j); 
      } 
     } 
     Console.WriteLine(hsc1.Intersect(hsc2).Count().ToString()); 
     Console.WriteLine(hsc1.Union(hsc2).Count().ToString()); 
    } 
} 

public class HashSetComposite : HashSet<UInt32> 
{ 
    public void Add(UInt16 u1, UInt16 u2) 
    {  
     UInt32 unsignedKey = (((UInt32)u1) << 16) | u2; 
     Add(unsignedKey);   
    } 
    //left over notes from long 
    //ulong unsignedKey = (long) key; 
    //uint lowBits = (uint) (unsignedKey & 0xffffffffUL); 
    //uint highBits = (uint) (unsignedKey >> 32); 
    //int i1 = (int) highBits; 
    //int i2 = (int) lowBits; 
}

使用ConcurrentDictionary進行測試，結果超過兩倍。
在插入物上鎖定很昂貴。

來源

2012-10-18 13:26:33 Paparazzi

不錯。是啊我想過使用我的元素的哈希集（只是覆蓋我的元素GetHasCode返回密鑰。但我沒有意識到UnionWith方法..非常酷 –

而你需要重寫Equals。但是如果你有一個完美的散列，那麼是未使用。 – Paparazzi

您的問題似乎適用於基於事件的解決方案。基本上分配事件以完成每個來源的數據。使用類型保留全局併發散列。在你的事件處理程序中，檢查完成的數據源，如果你的併發哈希包含當前元素的鍵值，那麼只需將其添加到列表中，如果不是僅僅插入一個給定元素的新列表。

但根據您的性能要求，這可能會使應用程序過於複雜。你的第一個方法是最簡單的方法。

來源

2012-10-18 14:05:20 omerkirk

謝謝..這是什麼＃2方法的建議是..我只是不知道這將如何與3線程更新相同的哈希.. –

NET並沒有一個併發的HashSet據我所知。 – Paparazzi

協調3個列表的最佳算法

回答

相關問題