存储具有相应索引的对象的最有效方法

Question

我想存储点的集合，它们是 class Point 的对象。（Point 包含 positionX、positionY、electricalPotential 等属性。）他们每个人都应该有一个索引 i，但不需要以任何方式排序。这就是为什么我首先使用字典 Dictionary<int, Point> meshpoints 的原因。

第一题：
如果我只想用某个 index/key 存储对象，那么字典是存储数据的最有效方式吗，尤其是当涉及到每个元素的添加、搜索和循环等性能问题时？

第二题：
如果我想添加一个新点，我如何获得"next"免费密钥？就像如果我有带有散列键 0、1、2、3 和 4 的字典，我如何获得 5下一个项目键？

选项 1： meshpoints.Keys.Max() 和 meshpoints.Keys.Last() 在我的测试中花费了很多时间。

Dictionary<int, string> meshpoints = new Dictionary<int, string>();

meshpoints.Add(meshpoints.Keys.Max() + 1, "itemA");

meshpoints.Add(meshpoints.Keys.Max() + 1, "itemB");

选项 2： 创建一个单独的变量 counter 在我的性能测试中相当快，但这真的是最优雅的方式吗？我的意思是，你总是有一个带有字典的单独整数值到所有方法等。...

Dictionary<int, string> meshpoints = new Dictionary<int, string>();
int counter = 0;

meshpoints.Add(counter, "itemA");
counter++;

meshpoints.Add(counter, "itemB");
counter++;

选项 3: meshpoints.Count() 将不起作用，因为我也随时删除项目。

Answer 1

如果您不喜欢有两个单独的变量，则创建一个新结构将它们绑定在一起：

struct MeshPointContainer
{
    private int _counter = 0;
    private List<Point> _pts = new List<Point>();

    public int Add(Point pt) {
        _pts.Add(pt);
        return ++counter;
    }
}

然后像这样使用它：

var meshPoints = new MeshPointContainer();
meshPoints.Add(new Point(-1f));

如果您希望能够删除点，这会稍微复杂一些，但到目前为止您还没有表示这样做。

Answer 2

你不需要字典，因为你想做的事情可以用一个列表来完成。

因为你使用Count + 1作为新ID，你可以添加一个自动生成的ID到点class，这是一个更好的设计：

public class Point
{ 
  static private int NextID;

  int ID { get; }
  public Point()
  {
    ID = NextID++;
  }
}

List<Point> meshPoints = new List<Point>();

var meshPointA = new Point();
var meshPointB = new Point();
var meshPointC = new Point();

meshPoints.Add(meshPointA);
meshPoints.Add(meshPointB);
meshPoints.Add(meshPointC);

var meshPoint = meshPoints.Where(p => p.ID == 2).SingleOrDefault();

有了它，您将永远不会在添加、插入和删除对象时出现重复 ID 或冲突。

使用选项 1，Max 不提供速度性能。

对于option3，使用Count会导致这些问题：如果你添加4个点然后删除第一个然后添加一个，最后一个的ID为3而剩下的两个有3和4的ID ...所以选项2更好。

如果你想要一个字典，你可以通过创建一个 class 来做同样的事情，它嵌入了一个内部字典，它有 NextID，并且提供了你想要提供的方法，比如添加、删除、 ContainsX, IDs (Items.Keys), Points (Items.Values) 等等（所有你想管理的这个专门的集合）：

public class PointsDictionary : IEnumerable<Point>
{
  private readonly Dictionary<int, Point> Items = new Dictionary<int, Point>();

  private int NextID;

  public Point this[int index]
  {
    get { return Items.ContainsKey(index) ? Items[index] : null; }
    set { ... }
  }

  public Dictionary<int, Point>.KeyCollection IDs
  {
    get { return Items.Keys; }
  }

  public Dictionary<int, Point>.ValueCollection Points
  {
    get { return Items.Values; }
  }

  public int Add(Point point)
  {
    int index = NextID++;
    Items.Add(index, point);
    return index;
  }

  ...

}

所以在这里，您将拥有一个强大而干净的设计。

Answer 3

这个问题变量太多，无法正确回答。如果你提到的数据必须存储

with a certain index/key,

访问密钥必须为访问者所知...否则为什么要使用以整数作为密钥的字典？

how do I get the "next" free key?

不能保证 Object.GetHashCode Method 的唯一性，应该由您自己覆盖以创建适当的哈希，但可以这样做

var myDict = new Dictionary<int, PointIt>();

var p1 = new PointIt() { PositionX=1, PositionY=2,  ElectricalPotential=999.99};
var p2 = new PointIt() { PositionX=1, PositionY=2,  ElectricalPotential=999.99};

myDict.Add(p1.GetHashCode(), p1);
myDict.Add(p2.GetHashCode(), p2);

myDict.ToList()
      .ForEach(itm => Console.WriteLine($"Key ({itm.Key}) Value {itm.Value}"));

输出如

Key (23832771) Value X:1 Y:2 Potential:999.99
Key (44512918) Value X:1 Y:2 Potential:999.99

public class PointIt
{
    public int PositionX { get; set; }
    public int PositionY { get; set; }
    public double ElectricalPotential { get; set; }

    public override string ToString()
        => $"X:{PositionX} Y:{PositionY} Potential:{ElectricalPotential}";
}

存储具有相应索引的对象的最有效方法

Most efficient way of storing objects with corresponding indices

c#

performance

dictionary

hashtable

list