在多维数组和单一数组之间，存储数据的最有效方法是什么？

Question

在多维数组和单一数组之间，存储数据的最有效方法是什么？

c#arraysmultidimensional-arrayunity-game-enginejagged-arrays

4

本质上，我不确定如何存储 3D 数据结构以实现最快的访问速度，因为我不确定多维数组底层正在发生什么。

注意：每次数组的大小都是常数且已知的，每个元素恰好为16位。

选项一是使用多维数组data[16, 16, 16]并通过data[x, y, z]简单访问。选项二是使用单维数组data[16 * 16 * 16]，并通过data[x + (y * 16) + (z * 16 * 16)]进行访问。

由于每个元素应该只有16位长，并且我怀疑多维数组会在内部存储很多其他数组的引用，每个引用至少占用32位，这将浪费很多内存。但是，我担心它可能比每次运行选项二中指定的方程式更快，而速度是这个项目的关键。

那么，是否有人能告诉我速度差异与内存消耗差异之间可能有多大？

- Benjamin James Drury

2

可能是多维数组 vs. 一维数组的重复问题。 - Mostafiz

我认为这可能会对你有所帮助为什么.NET中的多维数组比普通数组慢？ - Craveiro

3

单维度很可能更快：https://github.com/dotnet/coreclr/issues/4059#issuecomment-208491798，但如果你想知道哪匹马跑得更快，就应该比赛。 - Matthew Watson

Benjamin-James-Drury，我会稍微改变问题的表述，强调每个元素都是16位，因为这使得问题与类似的问题不同，并在答案中产生了有趣的看法。 - James R

我之前没有参考现有的问题是因为我的情况比较特殊，但我已经意识到我的想法是错误的，所以也许我应该默认参考它们。无论如何，感谢所有提供帮助的人，我很感激，并且确实会比赛看看哪个更快。 - Benjamin James Drury

这里关于性能的部分是非常有用的介绍：http://www.slideshare.net/wvdang/five-things-every-win32-developer-should-know - Ben

3个回答

3

我认为需要指出的是，如果您的数组维度都是16，那么您可以更高效地从(x, y, z)计算出数组的索引：

int index = x | y << 4 | z << 8;

反之亦然：

int x = index & 0xf;
int y = (index >> 4) & 0xf;
int z = (index >> 8) & 0xf;

如果情况是这样的话，我建议使用单维数组，因为它几乎肯定会更快。请注意，JIT编译器很可能会执行此优化（假设乘法已硬编码），但明确执行此操作仍然值得。我之所以说单维数组会更快，是因为最新的编译器缺少一些多维数组访问的优化，正如此线程中所讨论的。尽管如此，您应该进行仔细的计时以查看哪个才是最快的。就像Eric Lippert所说：“如果你想知道哪匹马更快，请比赛”。

- Matthew Watson

1

反之，x = index＆0xF，y = index＆0xF0和z = index＆0xF00。 - juharr

@downvoter：能否告诉我们答案有什么问题？这将非常有用。 - Matthew Watson

1

单维数组只有在按顺序访问时才更快，对吧？如果根据已知坐标进行查找，两者的性能应该是相同的。 - Luaan

@Luaan，你看了我发的关于一些编译器优化缺失的链接吗？ - Matthew Watson

1

是的，没错。所提到的缺失优化是将部分计算提升到内部循环之外，这意味着很多不必要的乘法。因此，如果您尝试访问数组中的一个特定位置，则两者应该执行相同。唯一不同的情况是当您在一个“行”中循环“列”时 - 行偏移量一遍又一遍地计算...至少我是这样理解分析的。 - Luaan

虽然我没有选择这个答案，因为我觉得另一个人讲得更详细，但你找到正确索引和反向的方法对我来说将是非常宝贵的，所以谢谢你。 - Benjamin James Drury

1

我会选择使用一维数组，它应该更快。基本上，您可以编写一些测试，执行您最常见的任务并测量所花费的时间。此外，如果您有2^n的数组大小，使用左移操作而不是乘法访问元素位置会更快。

- Nickolay Olshevsky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ben · Accepted Answer

C#将多维数组存储为一块内存，因此它们编译成几乎相同的东西。（一个区别是有三组边界需要检查。）

也就是说，arr[x,y,z]几乎等同于arr[x + y*ny +z*nz*ny]，并且通常具有类似的性能特征。

然而，确切的性能将受到内存访问模式的影响，以及这如何影响缓存一致性（至少对于大量数据而言）。如果通过按不同顺序执行循环来更好地使当前使用的数据保持在处理器缓存中，则可能会发现按x、y、z嵌套循环比执行不同顺序的循环更快或更慢。

这高度取决于确切的算法，因此无法给出对所有算法都正确的答案。

与C或C++相比任何速度降低的另一个原因是边界检查，在一维数组情况下仍将需要进行检查。但是这些通常会自动删除，但不总是。

https://blogs.msdn.microsoft.com/clrcodegeneration/2009/08/13/array-bounds-check-elimination-in-the-clr/

再次强调，确切的算法会影响优化器是否能够删除边界检查。

您应该采取以下行动：

编写一个使用arr[x,y,z]的朴素版本的算法。
如果速度足够快，则可以停止。
否则，请对算法进行分析以检查实际上是数组访问存在问题，分析内存访问模式等。