Multi-dimensional array vs. One-dimensional

Question

This is basically a restatement of this question: Java: Multi-dimensional array vs. One-dimensional but for C#.

I have a set amount of elements that make sense to store as a grid. Should I use a array[x*y] or a array[x][y]?

EDIT: Oh, so there are one dimensional array[x*y], multidimensional array[x,y] and jagged array[x][y], and I probably want jagged?

I would mark `multidimensional` array as `array[x,y]` instead of `array[x][y]` — Snowbear, Mar 29 '11 at 16:56

score 12 · Accepted Answer · answered Mar 29 '11 at 16:50

12

There are many advantages in C# to using jagged arrays (array[][]). They actually will often outperform multidimensional arrays.

That being said, I would personally use a multidimensional or jagged array instead of a single dimensional array, as this matches the problem space more closely. Using a one dimensional array is adding complexity to your implementation that does not provide real benefits, especially when compared to a 2D array, as internally, it's still a single block of memory.

answered Mar 29 '11 at 16:50

Reed Copsey

554,122
78
1,158
1,373

4

Sorry but I hate that term "Jagged Arrays". .net documentation throws so much terminology out there that someone would think that a jagged array was a new datatype. Its just an array of array dangit! – JonH Mar 29 '11 at 16:55
3

@JonH: Yes, but it's the official term for that, and there are specific optimizations in place in the CLR for working with them. – Reed Copsey Mar 29 '11 at 17:01

score 12 · Answer 2 · answered Mar 29 '11 at 18:02

I ran a test on unreasonably large arrays and was surprised to see that Jagged arrays([y][x]) appear to be faster than the single dimension array with manual multiplication [y * ySize + x]. And multi dimensional arrays [,] are slower but not by that much.

Of course you would have to test out on your particular arrays, but it would seem like the different isn't much so you should just use whichever approach fits what you are doing the best.

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");
}

Very interesting post. I found the ProfileTimer on code.google.com. At first I could not reproduce your results. The memory allocation for the jagged array was very slow and 2-dim access was very slow. Then I unchecked "Prefer 32-bit" in the build options and everything matched your results very closely. — dcaswell, Jan 12 '15 at 14:37

score 10 · Answer 3 · answered Mar 29 '11 at 16:55

Pros of array[x,y]:
- Runtime will perform more checks for you. Each index access will be checked to be within allowed range. With another approach you could easily do smth like a[y*numOfColumns + x] where x can be more than "number of columns" and this code will extract some wrong value without throwing an exception.
- More clear index access. a[x,y] is cleaner than a[y*numOfColumns + x]

Pros of array[x*y]:
- Easier iteration over the entire array. You need only one loop instead of two.

And winner is... I would prefer array[x,y]

Multi-dimensional array vs. One-dimensional

3 Answers3

Linked