int[,] 数组与 Dictionary<> 在常量更新方面的效率比较

Question

我正在使用Unity（只是次要相关）中的C#创建一个游戏场景，它实际上是.NET，因为它在Unity中。这个场景是二维的，并且通过细化方法基于细胞自动机生成，可以使场景的形状“可用”于我的意图。

目前，基础游戏场景的数据（活着的单元格或死亡的单元格，开放的或关闭的，通道或墙壁）以二进制值的形式存储在一个int [，]数组中。最终，还将在该数组中存储其他数据，或者可能存储在与该int [，]数组映射回的辅助集合中。

其他数据将包括关于以下事项的信息：玩家是否访问过此单元格、当前玩家是否能看到该单元格（LoS）、该单元格中是否有敌人或物品/项目。

显然，LoS、hasVisited和敌人数据将是动态的，随着玩家导航和敌人沿其路径移动而变化。

我希望从一开始就设计并开发时考虑性能，因为早期错误可能会导致性能瓶颈，这可能需要重构，浪费宝贵的开发时间，接近项目结束时。

我的问题是：

更新一个或多个数组来跟踪数据是否会以线性或指数方式变得资源密集？换句话说，如果mapA是[80,80]，而mapB是[160,160]，那么mapB在维护方面要消耗大约4倍的资源，还是更多或更少？如果大小超过某个int [，]值，使用类似于Dictionary或自定义集合这样的东西是否有好处？

我的初始想法是使用类似于Dictionary<int [，]，Dictionary<string，string>> 的东西。我在工作中经常使用字典，但是我不考虑性能，因为它是内部的，非常具体化，所以我对Dictionary<>的性能不太熟悉。与同一个网格的多个不同数据的多个数组相比，字典的好处是我可以拥有有意义的键，而不仅仅是需要跟踪的其他值。然而，我怀疑数组可能只是更快，而长期来看不太可读。

谢谢！

- Jesse Williams

---

好的，我会对它们进行一些测试。在实际场景中，获取一个计时器并查找它们将消耗的时间。 - Christoph K

就像这样：我已经将4个大小相似的盒子存放在一个2x2的正方形中。现在我想要将16个上述的盒子存放在一个4x4的正方形中。增加了多少？无论如何：注重性能没有错，但我建议首先考虑可理解性和可维护性。然后再看看你是否真的有性能问题。然后再看看你可以在哪里进行改进。一个带有二维int数组作为键和字符串-字符串对字典的字典听起来不像是你以后会喜欢调试的东西。 - Willem van Rumpt

在我还是学生的久远时代，有一位教授在我们谈论程序优化时告诉我们：“在开发过程中，不要这样做。等到程序可以运行后，也不要这样做。”当然，获得最佳性能可能需要大量重构，但在弄清楚程序花费时间的地方之前很难知道要优化什么。而要想得到可工作的代码，你必须先弄清楚这些问题。 - Tony Vitabile

@TonyVitabile：然后下一步是：性能提升是否真的值得带来的可读性损失（这往往是不可避免的）？ - Willem van Rumpt

@JesseWilliams：通常在计算机领域是这样的。为x个项目保留空间需要x个空间。为4x个项目保留空间需要4x的空间。如果在该空间中处理数据的成本取决于您使用的算法。对x [0,1]进行索引访问与对x [875,232]进行索引访问一样快，搜索性能（例如）将随着空间增加而不断恶化（但当然会保持其BigO特征）：在家里寻找你的猫比在你的邻居家花费更少的时间。 - Willem van Rumpt

Answer 1

根据这个答案，一个字典在内部是一个结构体数组。因此，你只是在自己的多维数组上添加了一个额外的层。如果你正在寻找微观优化，那么你永远无法通过在其上堆叠更多内容来打败数组。

此外，int[,] 至少会有助于可读性，因为它是数据在视觉上准确显示的表示。所以首先，请确保你需要进行优化。优先考虑可读性而不是过早的优化。

我建议对于你所做的事情，使用 int[,]。它将具有更好的性能和可读性。

- krillgar

---

谢谢 - 这很有道理。我认为只要有记录，即使有一个额外的“重复”数组带有次要值，也会相当易读。 - Jesse Williams

@JesseWilliams：追求“非常易读”，而不是“相当易读”。 “易读”通常意味着“易读，因为我正在处理这些内容，所以我已经花费了时间意识到所有其他依赖关系。”易读会在一个月内自动降级为“相当易读”。 - Willem van Rumpt

哈哈，是的，我所说的并不是角度，而是相对比较。在我的日常工作中作为一名QA分析师，我经常阅读到的代码质量最好也只是相当易读，而且通常几乎难以理解，因此我非常支持让事情有意义。我也很喜欢注释——如果某个变量、方法或循环函数不是立即明显的，它将有注释（通常是复数）。 - Jesse Williams

@JesseWilliams：这是我最讨厌的事情之一，所以我很少错过传递信息的机会。我每天都看到很多代码，“创意解决方案”、“智能实现”和“优化”在90%的情况下实际上都没有带来任何好处，而且在90%的情况下还会保证未来维护时的噩梦。交付的东西并不糟糕、不有故障、不功能错误，只是没有改进，也不值得增加复杂性。 - Willem van Rumpt

Answer 2

这可能取决于游戏空间的大小和稀疏程度，但我会考虑使用字典或其他管理结构。

如果您有一个1000x1000的游戏空间并且使用数组，即使您只“访问”其中的10％，它也将生成1,000,000个数组单元。 字典方法将使用内部数组，但仅在需要时才会增长，并且最初会很小。 比如说10x10（不确定，需要检查）。

我假设访问空间的百分比可能远远低于100％。 直到需要更大的空间，字典才会保持较小的内存占用量，而且当它变得很大时，字典的开销是可以忽略不计的。

- sm14

---

在初始化时，整个游戏空间必须是“已知”的，但是关于任何给定单元格的数据可能是稀疏的，并且对于距离存活单元格曼哈顿距离> 1的死亡单元格不存在。 - Jesse Williams

Answer 3

更新：正如评论中的人们指出的那样，int[,]在C#中似乎与我假设的C++ int[][]有很大的不同，我将答案作为参考。所以当性能没有受到影响时，应该始终优先选择可读性，使用int[,]而不是我下面提出的方法。

我还要补充说，甚至可以将二维区域简化为一个简单的int[]可能更高效。你可以轻松地这样做：

int[] myArray = new int[width * height];

int x, y; // suppose you want to reach the cell at (x, y) coordinates
int cell = myArray[x + y * width];

for(int i=0 ; i<myArray.Length ; ++i) // suppose you want to iterate through the array
{
    int x = i % width;
    int y = i / width; // be sure that width is an int here, we want the auto-flooring

    int cell = myArray[x + y * width] // like above ;)

    int cell = myArray[i] // or of course for simplicity
}

在我写这篇文章时，我不确定在C#中[]是否比[,]更有效，但我知道在C++中是这样的。

关于这个问题的完整教程: 使用单维数组表示二维数据

- Sharundaar

---

@quetzalcoatl - 很好的观点。我在想，性能的提升是否会被从单个单元格中获取信息时需要从x-y对中数学确定值所抵消。 - Jesse Williams

@Sharundaar：据我所知，由于计算机内存空间是线性的，您在代码中提供的计算与数组索引器执行的计算完全相同，因此我认为您并没有获得任何优势，反而失去了可读性。 - Tony Vitabile

更新了我的答案，基本上已经完善了。 - Sharundaar

@ScottChamberlain：是的，C#的int[][]是int* arr[]（很容易与int(*arr)[]混淆，但实际上在C#中无法完全表示，除了int[,]不是100%匹配），但是在这里讨论C++类型系统没有太多意义吧？当我写下那个评论时，Sharundaar并没有声称代码是在C++中，而且问题是关于C#的，没有提到C++。如果你仔细看，有int[]，所以那段代码是C#。因此，我只谈论C#，我不认为OP知道C++的复杂性，这比C#难得多。 - quetzalcoatl

@Quetzalcoatl; 去掉指针越界检查实际上会使您的代码更容易崩溃和失败。抱歉，但我建议您继续使用内置的索引器。 - Tony Vitabile