自我更新集合併發問題

Question

我正在嘗試構建自我更新集合。集合中的每個項目都有一個位置（x，y）。當職位更改時，會觸發一個事件，集合將重新定位該項目。

集合內部使用「鋸齒狀字典」。外部字典使用x座標一個鍵，而嵌套字典使用y座標一個鍵。嵌套字典然後將項目列表作爲值。

集合還維護一個字典，用於存儲存儲在嵌套字典中的項目位置 - 項目到存儲的位置查找。

我在收集線程安全，我真的需要一些麻煩。對於集合

的源代碼：

public class PositionCollection<TItem, TCoordinate> : ICollection<TItem> 
    where TItem : IPositionable<TCoordinate> 
    where TCoordinate : struct, IConvertible 
{ 
    private readonly object itemsLock = new object(); 
    private readonly Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>> items; 
    private readonly Dictionary<TItem, Vector<TCoordinate>> storedPositionLookup; 

    public PositionCollection() 
    { 
     this.items = new Dictionary<TCoordinate, Dictionary<TCoordinate, List<TItem>>>(); 
     this.storedPositionLookup = new Dictionary<TItem, Vector<TCoordinate>>(); 
    } 

    public void Add(TItem item) 
    { 
     if (item.Position == null) 
     { 
      throw new ArgumentException("Item must have a valid position."); 
     } 

     lock (this.itemsLock) 
     { 
      if (!this.items.ContainsKey(item.Position.X)) 
      { 
       this.items.Add(item.Position.X, new Dictionary<TCoordinate, List<TItem>>()); 
      } 

      Dictionary<TCoordinate, List<TItem>> xRow = this.items[item.Position.X]; 

      if (!xRow.ContainsKey(item.Position.Y)) 
      { 
       xRow.Add(item.Position.Y, new List<TItem>()); 
      } 

      xRow[item.Position.Y].Add(item); 

      if (this.storedPositionLookup.ContainsKey(item)) 
      { 
       this.storedPositionLookup[item] = new Vector<TCoordinate>(item.Position); 
      } 
      else 
      { 
       this.storedPositionLookup.Add(item, new Vector<TCoordinate>(item.Position)); // Store a copy of the original position 
      } 

      item.Position.PropertyChanged += (object sender, PropertyChangedEventArgs eventArgs) => this.UpdatePosition(item, eventArgs.PropertyName); 
     } 
    } 

    private void UpdatePosition(TItem item, string propertyName) 
    { 
     lock (this.itemsLock) 
     { 
      Vector<TCoordinate> storedPosition = this.storedPositionLookup[item]; 
      this.RemoveAt(storedPosition, item); 
      this.storedPositionLookup.Remove(item); 
     } 

     this.Add(item); 

    } 
} 

我寫了一個簡單的單元測試，以檢查併發問題：

 [TestMethod] 
    public void TestThreadedPositionChange() 
    { 
     PositionCollection<Crate, int> collection = new PositionCollection<Crate, int>(); 
     Crate crate = new Crate(new Vector<int>(5, 5)); 
     collection.Add(crate); 

     Parallel.For(0, 100, new Action<int>((i) => crate.Position.X += 1)); 

     Crate same = collection[105, 5].First(); 
     Assert.AreEqual(crate, same); 
    } 

實際存儲的位置變化我每次運行測試時間。我很感激你可能有的任何反饋。

Answer 1

爲了提高併發性，您可以維護每個X座標的鎖列表，否則在性能上你不會看到太多的增益。

或者，您可以切換到四叉樹或其他空間索引系統，以最大限度地減少項目移動時數據結構的擾動。使用四叉樹，您可以通過在獨立樹級別保持獨立鎖而不是數據結構範圍來最大限度地減少併發問題。

您的數據結構使得跟蹤移動對象非常昂貴，因爲它必須不斷更新自己。使用「bucketed」方法（如果您有X/Y座標限制），只有在項目更改了存儲桶時纔可以限制更新。

private void UpdatePosition(TItem item) 
{ 
    // each bucket holds some MxN section of the X,Y grid 
    var nextBucket = CalculateBucket(item.Position); 
    if (nextBucket != item.Bucket) 
    { 
     lock (wholeCollectionLock) 
     { 
      this.buckets[nextBucket].Add(item); 
      this.buckets[item.Bucket].Remove(item); 
      item.Bucket = nextBucket; 
     } 
    } 
} 

public IEnumerable<TItem> ItemsAt(TPosition position) 
{ 
    var bucket = CalculateBucket(position); 
    lock (wholeCollectionLock) 
    { 
     // this will be efficient enough for cases where O(n) searches 
     // have small enough n's 
     // needs to be .ToArray for "snapshot" 
     return this.buckets[bucket].Where(xx => xx.Position == position).ToArray(); 
    } 
}