自更新集合并发问题
自更新集合并发问题
提问于 2010-05-18 04:53:26
我正在尝试构建一个自我更新的集合。集合中的每一项都有一个位置(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
Stack Overflow用户
回答已采纳
发布于 2010-05-18 05:26:58
您可能会在每个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();
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2852724
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号