Are the x,y and row, col attributes of a two-dimensional array backwards?

Question

If I think of the x,y coordinate plane, x,y is the common notation for an ordered pair, but if I use a two-dime array I have myArray[row][col] and row is the y and col is the x. Is that backwards or am I just thinking about it wrong? I was thinking it would look like myArray[x][y] but that's wrong if I want real rows and columns (like in a gameboard.) Wouldn't it be myArray[y][x] to truly mimic a row column board?

Tripersonal

I found myself asking the same question to my parents. Good to know that there's no standard. – Teacup

Answer 1

You have it right, and it does feel a bit backwards. The row number is a y coordinate, and the column number is an x coordinate, and yet we usually write row,col but we also usually write x,y.

Whether you want to write your array as [y][x] or [x][y] depends mostly on how much you actually care about the layout of your array in memory (and if you do, what language you use). And whether you want to write functions/methods that can operate on rows or columns in isolation.

If you are writing C/C++ code, arrays are stored in Row Major Order which means that a single row of data can be treated as 1 dimensional array. But a single column of data cannot. If I remember correctly, VB uses column major order, so languages vary. I'd be surprised of C# isn't also row major order, but I don't know.

Stifling

This is the clearest explanation I have read in 20 mins of searching – Seale

C# is column major. To check: declare a multi-dimensional array, such as int a[2, 2]; in an unsafe block, fix the first element: fixed(int* p = &a[0,0]), and iterate int* q = p; q++ for each step. If the array was initialized int[,] a = new int[2, 2] { { 1, 2 }, { 3, 4 } }; you see 1, 2, 3, 4. If it was row major you would see the row dimension (first dimension) to change first. – Milker

@Milker Your example indicates to me that C# is row-major ({1, 2} is a row). Given C#'s lineage from other C-like languages, row-major seems far more likely. Also see the comments to https://mcmap.net/q/281400/-two-dimensional-array-in-memory-duplicate which explains that the CLI is specified to use row-major order. – Cupbearer

@jamesdlin, you are right, I flipped the definitions of row-major and column-major. It's a problem with this terminology. I was thinking of column-first (column index varies fastest), which is row-major. – Milker

Answer 2

This is what I do for my own sanity:

int x = array[0].length;
int y = array.length;

And then for every single array call I make, I write:

array[y][x]

This is particulary useful for graphing algorithms and horizontal/vertical matrix flipping.

Scala

This question gets a lot of hits. Funny how that goes over the years. I'll have to remember this answer. Thanks. – Tripersonal

Answer 3

It doesn't matter how you store your data in the array ([x][y] or [y][x]). What does matter is that you always loop over the array in a contiguous way. A java two dimensional array is essentially a one dimensional array storing the second array (eg. in the case of [y][x] you have a long array of [y] in which each y holds the corresponding [x] arrays for that line of y).

To efficiently run through the whole array, it's important to access the data in a way so that you don't continuously have to do searches in that array, jumping from one y-array-of-xarrays to another y-array-of-xarrays. What you want to do is access one y element and access all the x's in there before moving to the next y element.

So in an Array[y][x] situation. always have the first variable in the outer loop and the second in the inner loop:

for (int ys = 0; ys < Array.length; ys++)
    for (int xs = 0; xs < Array[y].length; xs++)
    {
        do  your stuff here
    }

And of course pre-allocate both Array.lengths out of the loop to prevent having to get those values every cycle.

Butlery

Answer 4

I love the question. You’re absolutely right. Most of the time we are either thinking (x, y) or (row, col). It was years before I questioned it. Then one day I realized that I always processed for loops as if x was a row and y was a column, though in plane geometry it’s actually the opposite. As mentioned by many, it really doesn’t matter in most cases, but consistency is a beautiful thing.

Teetotal

Answer 5

For better or for worse, the inconsistent notation was inherited from math.

Multidimensional arrays follow matrix notation where M_i,j represents the matrix element on row i and column j.

Multidimensional arrays therefore are not backward if used to represent a matrix, but they will seem backward if used to represent a 2D Cartesian plane where (x, y) is the typical ordering for a coordinate.

Also note that 2D Cartesian planes typically are oriented with the y-axis growing upward. However, that also is backward from how 2D arrays/matrices are typically visualized (and with the coordinate systems for most raster images).

Cupbearer

Answer 6

Actually, It's up to you. There is no right of thinking in your question. For example i usually think of a one-dimension array as a row of cell. So, in my mind it is array[col][row]. But it is really up to you...

Alluvion

If you're thinking of cache consequences, there is a right way of looking at it... – Brink

@mmeyers: Not really, the effect is that you store the game-board sideways. It's common to store images this way. – Constitutionalism

I think that the question is without any given context ... Of course in different contexts, there is different logics. – Alluvion

@Joel: 1) As long as you still iterate correctly regardless of how you're thinking about it, yes. That might require going (in your perspective) column-by-column rather than row-by-row. 2) I don't get notified when you call me mmeyers. That's the fourth time that's happened since notifications were implemented. :) – Brink

Answer 7

I bet there are a lot of differing opinions on this one. Bottom line is, it doesn't really matter as long as you are consistent. If you have other libraries or similar that is going to use the same data it might make sense to do whatever they do for easier integration.

If this is strictly in your own code, do whatever you feel comfortable with. My personal preference would be to use myArray[y][x]. If they are large, there might be performance benefits of keeping the items that you are going to access a lot at the same time together. But I wouldn't worry about that until at a very late stage if at all.

Burgher

Answer 8

Well not really, if you think of a row as elements on the x axis and then a 2d array is a bunch of row elements on the y axis, then it's normal to use y to operate on a row, as you already know the x (for that particular row x is always the same, it's y that's changing with its indices) and then use x to operate on the multiple row elements (the rows are stacked vertically, each one at a particular y value)

Akan