Traversing n-dimensional array

[yorki]

Hello everyone,

so far i have got following,

one int to hold number of dimension dim
one array to hold the size of each dimension (like shp[10,20] for 2d or say shp[30,10,20] for 3d)


how would i traverse through array?

I would be really grateful if someone can help me figure out a good way to do this. I am really stumped.

Thanks,

Yorki

[bernt]

Sounds like a good recursion problem to me.
So the classic recursive questions are asked: what's the base case for this recursion, and how does one simplify the original problem to get to that base case?

[Dino]

Sounds like a nested loop exercise to me.

[nonoob]

I believe yorki is trying for a generic algorithm to handle any dimension array.
Nested loops are not dynamic because they would hard-code the array's dimensionality.

Assume the array is linear... which is how it is stored in memory anyway.
For any index [i,j,k...] calculate the element offset. For example,

shp[30,10,20]
So to index array[i;j;k]
you would index at array[ i * (10 * 20) + j * 20 + k ]

In general, multiply first axis index by product of all lengths of axes following.
Multiply second axis index by product of all length of axes following.
Etc.

[yorki]

I believe yorki is trying for a generic algorithm to handle any dimension array.
Nested loops are not dynamic because they would hard-code the array's dimensionality.

Assume the array is linear... which is how it is stored in memory anyway.
For any index [i,j,k...] calculate the element offset. For example,

shp[30,10,20]
So to index array[i;j;k]
you would index at array[ i * (10 * 20) + j * 20 + k ]

In general, multiply first axis index by product of all lengths of axes following.
Multiply second axis index by product of all length of axes following.
Etc.

That is exactly what i need.

The array is allocated using malloc as 1d array so it is linear in memory.
but to add to problem i will be performing some stencil operation on array which requires two neighbors along each axes and i have got some ghost cells as well so i need to exclude them from operation

assume 2d array

0 1 2 3 4
5 6 7 8 9
10 11 12 13 14
15 16 17 18 19

i want to only traverse through elements 6,7,8,11,12,13 and 14

and for 6 i should get 5,6,1 and 11 as neighbor.

i am stuck at
how to traverse along each axes and leave out boundary cells and get current cells position

if you could provide pseudo code for this traversal and recursive function that will be grate help.

Thanks.

[tabstop]

Why elements 6,7,8,11,12,13,14? If you only want interior cells, you don't want 14.

As to "I'm at a point and I want the neighbors", that is neither traversing nor recursive, so asking for a traversal and recursive function isn't going to get you anywhere. Given that you are at position n, the neighbors in the last direction are going to be at +/- 1; the neighbors in the next-to-last direction are going to be at +/- (size of last dimension); the neighbors in the third-to-last direction are going to be at +/- (size of last dimension * size of next-to-last dimension), etc.

As to traversing, assuming you want to start at an interior cell, you want to start at the coordinate (1,1,1,...,1), which by the formula given above means you are at offset n, which can be calculated in general by

n = 0;
for (i = dim-1; i >=0; i--) {
    n *= dimensions[dim];
    n++;
}

From there, you can just move forward one space at a time. If the number of dimensions isn't known ahead of time, then I would just calculate the coordinates anew each time, and if you reach the end of a "row", then don't process. (You can "cheat" a little bit by knowing that you will have to skip two consecutive "elements": the last one in one row, and the first one in the next; and as you move up in dimensions you can skip more elements at a time. But that's going to be a little tricky to get correct, so I wouldn't do that unless you're running unacceptably slow.)

[yorki]

Why elements 6,7,8,11,12,13,14? If you only want interior cells, you don't want 14.

As to "I'm at a point and I want the neighbors", that is neither traversing nor recursive, so asking for a traversal and recursive function isn't going to get you anywhere. Given that you are at position n, the neighbors in the last direction are going to be at +/- 1; the neighbors in the next-to-last direction are going to be at +/- (size of last dimension); the neighbors in the third-to-last direction are going to be at +/- (size of last dimension * size of next-to-last dimension), etc.

As to traversing, assuming you want to start at an interior cell, you want to start at the coordinate (1,1,1,...,1), which by the formula given above means you are at offset n, which can be calculated in general by

n = 0;
for (i = dim-1; i >=0; i--) {
    n *= dimensions[dim];
    n++;
}

From there, you can just move forward one space at a time. If the number of dimensions isn't known ahead of time, then I would just calculate the coordinates anew each time, and if you reach the end of a "row", then don't process. (You can "cheat" a little bit by knowing that you will have to skip two consecutive "elements": the last one in one row, and the first one in the next; and as you move up in dimensions you can skip more elements at a time. But that's going to be a little tricky to get correct, so I wouldn't do that unless you're running unacceptably slow.)

Hi,
yes it was typo as 14 is not included, when i mentioned recursive function i was talking about recursive function to get coordinates as the number of dimension is unknown at compile time.

i have managed to get the neighbors and coordinates, but i am still stuck at array traversal of interior cells.

the formula above works but only for 2 dimension as soon as i goes in to 3 dimension it does not work.

i appreciate your help.

Thank you.

[tabstop]

Hi,
yes it was typo as 14 is not included, when i mentioned recursive function i was talking about recursive function to get coordinates as the number of dimension is unknown at compile time.

It's a for loop, it's not really recursive. If you've got the offset n, then starting at the right-most dimension, you alternate % and / to peel off the coordinates. (For instance, if you had a 7 x 6 x 9 x 4 array, and n = 777, then: 777%4 = 1, so that's the last coordinate; 777/4=194, 194%9=5, so that's the third coordinate; 194/9=21, 21%6=3, so that's the second coordinate; 21/6=3, 3%7 is 3, so that's the first coordinate.)

i have managed to get the neighbors and coordinates, but i am still stuck at array traversal of interior cells.

Array traversal is pretty simple: n++.

[yorki]

It's a for loop, it's not really recursive. If you've got the offset n, then starting at the right-most dimension, you alternate % and / to peel off the coordinates. (For instance, if you had a 7 x 6 x 9 x 4 array, and n = 777, then: 777%4 = 1, so that's the last coordinate; 777/4=194, 194%9=5, so that's the third coordinate; 194/9=21, 21%6=3, so that's the second coordinate; 21/6=3, 3%7 is 3, so that's the first coordinate.)


Array traversal is pretty simple: n++.

Hum that's pretty neat trick to calculate coordinates i have used recursion i will change it.

This is what i have got for array traversal

 
   int n = 0,i;

  for(d=dim-1;d >= 0; d--)
  {
    n *=dimensions[d]; 
    n++;
    
    /* endInd[] holds end index for dimension (position 0 is domension 0, position 1 is
       dimension 1...etc)*/
    for(i=0;i<endInd[0]-1;i++) 
    {
       printf("%d ",arr[n+i+dimShp[0]);
    }printf("\n");
  }

for 2d 5x4 (XxY where is X is fastest changing axes) array this should print

6 7 8
11 12 13

which it does , but for 3d array 5x4x3 (XxYxZ where X is fastest changing axes) it prints

6 7 8
10 11 12
31 32 33

where as the answer should be.

26 27 28
31 32 33


Thanks.

One more thing is there any literature around which explains all this in detail (i.e. coordinate calculation and traversal.. etc) i would be grateful if you can point it out.

[tabstop]

My code rather assumed C-style indexing, where the fastest-moving index is the last one. That appears to not be correct, unless you fixed it or something.

Either way, I don't see anyway you get 6 out of this unless you're skipping a dimension, or you really do have all that code inside your for loop somehow (you need to run that whole for loop by itself to get n; partial values don't help).

[yorki]

My code rather assumed C-style indexing, where the fastest-moving index is the last one. That appears to not be correct, unless you fixed it or something.

Either way, I don't see anyway you get 6 out of this unless you're skipping a dimension, or you really do have all that code inside your for loop somehow (you need to run that whole for loop by itself to get n; partial values don't help).

Sorry,

it was my mistake i should have written YxX as it is C-style indexing.

i am not trying to skip dimension but just the boundary cells in each dimension.

Here is my code for main

main( int argc, char* argv[])
{
  int i,dim,noshp;
  int *arr,sprod = 1,*dimensions,*cords,offset,*endInd;
  int w,x,y,z;

  if(argc <= 2)
  {
    printf("\nUsage ./arr <DIM> <Shp-0> <Shp-1> .. <Shp-d>\
            \nProgram will exit now.\n\n");
    exit(-1);
  }
  
  dim = atoi(argv[1]); 

  //holds shape information for each dim
  dimensions = malloc(dim * sizeof(int)); 
  cords = malloc(dim * sizeof(int));    // holds cordinates 
  
  for(i=0;i<dim;i++)
  {
    int shp = atoi(argv[i+2]);
    if(shp < 0)
    {
      printf("\nShape must be non-negative and non-zero.\
              \nProgram will exit now.\n\n");
      exit(-1);
    }
    dimensions[i] = shp; // x y z ...   
    //shape product
    sprod *= shp;    
  }    
  arr = malloc((sprod) * sizeof(int));  
  
  for(i=0;i<sprod;i++)
  {
    arr[i] = i;
  }  
  
  int n=0,size=1,p,d,loop,dimEnd,arrLen,offsetLeft,offsetRight;
  arrLen = sprod;
  
  for(d=dim-1;d >= 0; d--)
  {
    n *=dimensions[d];
    n++;    
    for(i=0;i<dimensions[0]-2;i++)//loop for 1 to (n-ghost) element in this dimension
    {
      printf("%d ",n+i+dimensions[0]);
    }printf("\n");
  }
}

[tabstop]

So, again, if you let the for loop on n run as it's supposed to:

for(d=dim-1;d >= 0; d--)
  {
    n *=dimensions[d];
    n++;
  }
  printf("%d\n", n);

you'll get your starting point of 26. Now you start trying to print rows, if you want. (You know you have to print dimensions[0]-2 in a row, which is a good start. It looks like you've sort of got the next bit, kind of: adding dimensions[0] gets you to the next row. You have to do that dimensions[1]-2 times, though. And you have to do all of that, dimensions[2]-2 times, etc. You can't really put this into a for loop, since you won't know ahead of time how many for loops you need; which is why I suggested the determine-coordinates route.)

[yorki]

which is why I suggested the determine-coordinates route.)

Does that mean i should do,
(pseudo code)

  for(d=0;d<arrLength;d++) //loop for all elements
  {
    getCords(d); //get the coordinates for current element
    if(isNotBoundaryElement) //check for boundary condition using coordinates
    {
       //do print
    }
  } //next element

Thanks

[tabstop]

Does that mean i should do,
(pseudo code)

  for(d=0;d<arrLength;d++) //loop for all elements
  {
    getCords(d); //get the coordinates for current element
    if(isNotBoundaryElement) //check for boundary condition using coordinates
    {
       //do print
    }
  } //next element

Thanks

That's the basic idea.

[yorki]

Thanks for all your help.

coordinates solution works as a treat.

Still there is one request
if you can point me toward literature related to array or array indexing or coordinate calculation that would be grate help.

(your way of getting coordinates is simplest i have came across so far, and it never appeared in any searches i did before)


Thanks