c# - C# List 执行时间过长。寻找（）

Question

我正在使用 C# 构建一个涉及基于网格的地图系统的游戏。我将网格系统存储在 List 对象中，其中 T 是包含位置和其他数据的类型。在调用一个查找图块邻居的函数时，我遇到了执行的极度延迟。我已将延迟缩小到调用我的 List 的 Find() 方法。该方法如下所示：

list.Find(tile => tile.X == x && tile.Y == y)

为什么会造成如此巨大的滞后？将我的图块存储在列表中是否有更好的选择？

Answer 1

如果您的地图是正方形/矩形且大小固定（或大小可变但不经常更改），则您可能会通过使用二维数组并按索引访问图块来获得更好的性能。

您不指示x和y值是磁贴索引还是与磁贴中包含的坐标相关。无论哪种方式，您都可以大概计算每个图块的索引，这样对于n图块，索引从 运行0..n-1，可用于索引到数组中。

您可以将地图数组定义为：

Tiles[,] map = new Tiles[numXTiles, numYTiles];

然后访问磁贴就像：

var tile = map[x, y];

有迹象表明多维数组的性能低于锯齿状数组，但多维数组更容易创建，并且（在我看来）具有更好的语法。如果这仍然是一个问题，您可以转而使用锯齿状数组，或使用一维数组，并将索引计算为：x + y * numXTiles。

Answer 2

Find是 O(n)，其中 n 是列表的计数。如果您总是通过坐标对进行查找，那么 Dictionary 真的很有帮助，因为您可以在键上进行 O(1) 查找。您可以从 a 开始Dictionary<Tuple<int,int>, Tile>，看看是否适合您的需求。显然，从长远来看，字典是否更好取决于列表的大小和您需要进行的查找类型。

Answer 3

如果您经常执行相同类型的查询，例如在您的情况下，使用组合键上的索引器来检索对象是有意义的，因为索引器通常具有或多或少的恒定性能。这意味着如果对象数量增加，找到对象的时间不会增加......

为此，请使用字典，其中 TKey 是例如一个字符串，每个键是 tile.X + " " + tile.Y 例如。要检索对象，您只需调用 dic[tile.X + " " + tile.Y]

Answer 4

因为在那个 lambda 表达式中你暗示你知道 x 和 y 坐标，所以你最好使用已经建议的 2D 数组。LINQ 很棒，但不应该到处使用。