代码之家  ›  专栏  ›  技术社区  ›  DEHAAS

自更新收集并发问题

  •  2
  • DEHAAS  · 技术社区  · 16 年前

    我正在尝试建立一个自更新集合。集合中的每个项都有一个位置(x,y)。更改位置时,将激发一个事件,集合将重新定位该项。

    在内部,该系列使用的是__交错字典_。外部字典使用X坐标A键,而嵌套字典使用Y坐标A键。然后,嵌套字典将项目列表作为值。

    该集合还维护一个字典,用于存储嵌套字典“项到存储位置查找”中存储的项位置。

    我很难保证收集线程的安全,这是我真正需要的。

    集合的源代码:

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

    每次运行测试时,实际存储位置都会有所不同。我很感激你的任何反馈。

    1 回复  |  直到 16 年前
        1
  •  1
  •   user7116    16 年前

    为了提高并发性,可以潜在地为每个x坐标维护一个锁列表,否则在性能上看不到多大的提高。

    或者,您可以切换到四叉树或其他一些空间索引系统,以便在项目移动时最小化数据结构的扰动。使用四叉树,您可以通过在单个树级别而不是数据结构范围内保持独立锁来最小化并发性问题。

    您的数据结构使跟踪移动对象变得非常昂贵,因为它几乎必须不断更新自己。使用“带括号”的方法(如果您的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();
        }
    }