13

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?

Improve this question
2
  • 1
    I would mark multidimensional array as array[x,y] instead of array[x][y] Commented Mar 29, 2011 at 16:56
  • Jagged arrays are more confortable to Linq with. Commented Dec 12, 2019 at 21:10

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

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: Yes, but it's the official term for that, and there are specific optimizations in place in the CLR for working with them.
12

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

1 Comment

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.
10

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]

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.