多维数组 vs 一维数组

Question

这基本上是重申了这个问题：Java: Multi-dimensional array vs. One-dimensional，不过是针对C#的。

我有一定量的元素需要作为网格存储。我应该使用array[x*y] 还是 array[x][y]？

编辑：哦，原来有一维的array[x*y]、多维的array[x,y] 和 jagged array[x][y]，我可能想要 jagged array？

- Zeta Two

---

我会将多维数组标记为array[x,y]而不是array[x][y]。 - Snowbear

锯齿数组在使用Linq时更加方便。 - Larry

Answer 1

我对超大的数组进行了测试，惊讶地发现不规则数组([y][x])似乎比手动乘法[y * ySize + x]的单维数组更快。而多维数组[,]比较慢，但差别并不大。

当然，你需要在你自己的数组上进行测试，但看起来差别不大，所以你应该使用最适合你的方法。

0.280 (100.0% | 0.0%) 'Jagged array 5,059x5,059 - 25,593,481'
|       0.006 (2.1% | 2.1%) 'Allocate'
|       0.274 (97.9% | 97.9%) 'Access'


0.336 (100.0% | 0.0%) 'TwoDim array 5,059x5,059 - 25,593,481'
|       0.000 (0.0% | 0.0%) 'Allocate'
|       0.336 (99.9% | 99.9%) 'Access'


0.286 (100.0% | 0.0%) 'SingleDim array 5,059x5,059 - 25,593,481'
|       0.000 (0.1% | 0.1%) 'Allocate'
|       0.286 (99.9% | 99.9%) 'Access'



0.552 (100.0% | 0.0%) 'Jagged array 7,155x7,155 - 51,194,025'
|       0.009 (1.6% | 1.6%) 'Allocate'
|       0.543 (98.4% | 98.4%) 'Access'


0.676 (100.0% | 0.0%) 'TwoDim array 7,155x7,155 - 51,194,025'
|       0.000 (0.0% | 0.0%) 'Allocate'
|       0.676 (100.0% | 100.0%) 'Access'


0.571 (100.0% | 0.0%) 'SingleDim array 7,155x7,155 - 51,194,025'
|       0.000 (0.1% | 0.1%) 'Allocate'
|       0.571 (99.9% | 99.9%) 'Access'



for (int i = 6400000; i < 100000000; i *= 2)
{
    int size = (int)Math.Sqrt(i);
    int totalSize = size * size;

    GC.Collect();

    ProfileTimer.Push(string.Format("Jagged array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[][] Jagged = new double[size][];
    for (int x = 0; x < size; x++)
    {
        Jagged[x] = new double[size];
    }

    ProfileTimer.PopPush("Allocate", "Access");

    double total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                total += Jagged[y][x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("Jagged array");


    GC.Collect();

    ProfileTimer.Push(string.Format("TwoDim array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[,] TwoDim = new double[size,size];

    ProfileTimer.PopPush("Allocate", "Access");

    total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                total += TwoDim[y, x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("TwoDim array");


    GC.Collect();

    ProfileTimer.Push(string.Format("SingleDim array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[] Single = new double[size * size];

    ProfileTimer.PopPush("Allocate", "Access");

    total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            int yOffset = y * size;
            for (int x = 0; x < size; x++)
            {
                total += Single[yOffset + x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("SingleDim array");
}

- BrandonAGr

---

非常有趣的帖子。我在code.google.com上找到了ProfileTimer。起初我无法重现您的结果。锯齿状数组的内存分配非常缓慢，而二维访问也非常缓慢。然后我在构建选项中取消了“首选32位”，一切都非常接近您的结果。 - dcaswell

Answer 2

在C#中使用交错数组(array[][])有很多优点，它们通常会比多维数组表现更好。

尽管如此，在实际问题中，我个人更倾向于使用二维数组或交错数组而不是一维数组。因为使用一维数组会使你的实现变得更加复杂，而没有提供真正的好处，特别是与2D数组相比，因为在内部，它仍然是一个单一的内存块。

- Reed Copsey

---

抱歉，但我很讨厌那个术语"Jagged Arrays"。.net文档中使用了许多术语，以至于有些人会认为“Jagged Array”是一种新的数据类型。实际上，它只是一个数组的数组！ - JonH

@JonH：是的，但这是官方术语，并且在CLR中有特定的优化方式来处理它们。 - Reed Copsey

Answer 3

array[x,y]的优点：
- 运行时将为您执行更多检查。每个索引访问都将检查是否在允许范围内。使用另一种方法，您可以轻松地执行类似于a[y*numOfColumns + x]的操作，其中x可能大于"列数"，并且这段代码将提取错误的值而不会抛出异常。
- 更清晰的索引访问方式。 a[x,y]比a[y*numOfColumns + x] 更干净。

array[x*y]的优点：
- 更容易迭代整个数组。您只需要一个循环而不是两个。

胜者是...我更喜欢array[x,y]

- Snowbear