0

我要求的东西有点奇怪，但这是我的要求（这有点计算密集型，到目前为止我在任何地方都找不到）..

我需要<TKey, TValue>大约 30 件物品的集合。但是该集合用于大规模嵌套foreach循环，这些循环可能会严重迭代近十亿次。收集操作很简单，看起来像：

 Dictionary<Position, Value> _cells = new 


_cells.Clear();
_cells.Add(Position.p1, v1);
_cells.Add(Position.p2, v2);
//etc

简而言之，无非是增加了大约 30 件物品并清理了收藏。此外，这些值将在某个时候从其他地方读取。我需要按键读取/检索。所以我需要一些类似于Dictionary. 现在，由于我试图从 CPU 中挤出每一盎司，我也在寻找一些微优化。一方面，我不需要集合在添加时检查是否存在重复项（与添加项相比，这通常会使字典变慢List<T>）。我知道我不会将重复项作为键传递。

由于Add方法会做一些检查，所以我尝试了这个：

_cells[Position.p1] = v1; 
_cells[Position.p2] = v2;
//etc

List<T>但是对于大约 10k 次迭代，这仍然比这样的典型实现慢了大约 200 毫秒：

List<KeyValuePair<Position, Value>> _cells = new 


_cells.Add(new KeyValuePair<Position, Value>(Position.p1, v1));
_cells.Add(new KeyValuePair<Position, Value>(Position.p2, v2));
//etc

现在，在完全迭代后，这可以扩展到一个明显的时间。请注意，在上述情况下，我已按索引从列表中读取项目（这对于测试目的来说是可以的）。对我们来说，常规的问题List<T>很多，主要原因是无法通过密钥访问项目。

简而言之，我的问题是：

  1. 是否有一个自定义集合类可以让按键访问项目，但在添加时绕过重复检查？任何第三方开源集合都可以。

  2. 或者请给我指出一个好的入门者如何从IDictionary<TKey, TValue>接口实现我的自定义集合类

更新：

我听从了 MiMo 的建议，List 还是更快。也许它与创建字典的开销有关。

4

2 回答 2

2

但这仍然比像这样的典型 List 实现慢了大约十次迭代

仅添加 30 个值的十次迭代会慢几毫秒？我不相信。除非您的散列/相等例程非常慢，否则仅添加几个值应该花费很少的时间。（这可能是一个真正的问题。我已经看到通过将关键选择调整为可以快速散列的东西来大幅改进代码。）

如果它真的需要更长的毫秒时间，我会敦促你检查你的诊断。

但总体而言它速度较慢也就不足为奇了：它正在做更多的工作。对于列表，它只需要检查是否需要增加缓冲区，然后写入数组元素，并增加大小。就是这样。没有散​​列，没有计算正确的桶。

是否有一个自定义集合类可以让按键访问项目，但在添加时绕过重复检查？

不。您要避免的工作正是使以后可以通过密钥快速访问的原因。

但是，您何时需要通过键执行查找？您是否经常在不查找密钥的情况下使用集合？执行键查找时集合有多大？

也许您应该建立一个键/值对列表，并且仅在您完成编写并准备开始查找时将其转换为字典。

于 2012-12-02T20:58:25.570 回答
2

我的建议是从源代码Dictionary<TKey, TValue>开始并对其进行更改以针对您的具体情况进行优化。

您不必支持删除单个键/值对，这可能有助于简化代码。似乎还可以检查您可以摆脱的密钥等的有效性。

于 2012-12-02T21:08:21.813 回答