alternative to multidimensional array in c

Question

tI have the following code:

 #define FIRST_COUNT 100
 #define X_COUNT 250
 #define Y_COUNT 310
 #define z_COUNT 40

struct s_tsp {

     short abc[FIRST_COUNT][X_COUNT][Y_COUNT][Z_COUNT];
};

struct s_tsp xyz;

I need to run through the data like this:

for (int i = 0; i < FIRST_COUNT; ++i)
    for (int j = 0; j < X_COUNT; ++j)
          for (int k = 0; k < Y_COUNT; ++k)
                for (int n = 0; n < Z_COUNT; ++n)
                      doSomething(xyz, i, j, k, n);

I've tried to think of a more elegant, less brain-dead approach. ( I know that this sort of multidimensional array is inefficient in terms of cpu usage, but that is irrelevant in this case.) Is there a better approach to the way I've structured things here?

Answer 1

If you need a 4D array, then that's what you need. It's possible to 'flatten' it into a single dimensional malloc()ed 'array', however that is not quite as clean:

abc = malloc(sizeof(short)*FIRST_COUNT*X_COUNT*Y_COUNT*Z_COUNT);

Accesses are also more difficult:

*(abc + FIRST_COUNT*X_COUNT*Y_COUNT*i + FIRST_COUNT*X_COUNT*j + FIRST_COUNT*k + n)

So that's obviously a bit of a pain.

But you do have the advantage that if you need to simply iterate over every single element, you can do:

for (int i = 0; i < FIRST_COUNT*X_COUNT*Y_COUNT*Z_COUNT; i++) {
    doWhateverWith *(abc+i);
}

Clearly this method is terribly ugly for most uses, and is a bit neater for one type of access. It's also a bit more memory-conservative and only requires one pointer-dereference rather than 4.

Answer 2

NOTE: The intention of the examples used in this post are just to explain the concepts. So the examples may be incomplete, may lack error handling, etc.

When it comes to usage of multi-dimension array in C, the following are the two possible ways.

Flattening of Arrays

In C, arrays are implemented as a contiguous memory block. This information can be used to manipulate the values stored in the array and allows rapid access to a particular array location.

For example,

int arr[10][10];
int *ptr = (int *)arr ;  

ptr[11] = 10; 
// this is equivalent to arr[1][0] = 10; assign a 2D array 
// and manipulate now as a single dimensional array. 

The technique of exploiting the contiguous nature of arrays is known as flattening of arrays.

Ragged Arrays

Now, consider the following example.

char **list;
list[0] = "United States of America";
list[1] = "India";
list[2] = "United Kingdom";
for(int i=0; i< 3 ;i++)
    printf(" %d ",strlen(list[i]));
// prints 24 5 14

This type of implementation is known as ragged array, and is useful in places where the strings of variable size are used. Popular method is to have dynamic-memory-allocation to be done on the every dimension.

NOTE: The command line argument (char *argv[]) is passed only as ragged array.

Comparing flattened and ragged arrays

Now, lets consider the following code snippet which compares the flattened and ragged arrays.

/* Note: lacks error handling */
int flattened[30][20][10];
int ***ragged;
int i,j,numElements=0,numPointers=1;
ragged = (int ***) malloc(sizeof(int **) * 30);
numPointers += 30;
for( i=0; i<30; i++) {
    ragged[i] = (int **)malloc(sizeof(int*) * 20);
    numPointers += 20;
    for(j=0; j<20; j++) {
        ragged[i][j]=(int*)malloc(sizeof(int) * 10);
        numElements += 10;
    }
}

printf("Number of elements = %d",numElements);
printf("Number of pointers = %d",numPointers);

// it prints
// Number of elements = 6000
// Number of pointers = 631 

From the above example, the ragged arrays require 631-pointers, in other words, 631 * sizeof(int *) extra memory locations for pointing 6000 integers. Whereas, the flattened array requires only one base pointer: i.e. the name of the array enough to point to the contiguous 6000 memory locations.

But OTOH, the ragged arrays are flexible. In cases where the exact number of memory locations required is not known you cannot have the luxury of allocating the memory for worst possible case. Again, in some cases the exact number of memory space required is known only at run-time. In such situations ragged arrays become handy.

Row-major and column-major of Arrays

C follows row-major ordering for multi-dimensional arrays. Flattening of arrays can be viewed as an effect due this aspect in C. The significance of row-major order of C is it fits to the natural way in which most of the accessing is made in the programming. For example, lets look at an example for traversing a N * M 2D matrix,

for(i=0; i<N; i++) {
    for(j=0; j<M; j++)
        printf(“%d ”, matrix[i][j]);
    printf("\n");
}

Each row in the matrix is accessed one by one, by varying the column rapidly. The C array is arranged in memory in this natural way. On contrary, consider the following example,

for(i=0; i<M; i++) {
    for(j=0; j<N; j++)
        printf(“%d ”, matrix[j][i]);
    printf("\n");
}

This changes the column index most frequently than the row index. And because of this there is a lot of difference in efficiency between these two code snippet. Yes, the first one is more efficient than the second one!

Because the first one accesses the array in the natural order (row-major order) of C, hence it is faster, whereas the second one takes more time to jump. The difference in performance would get widen as the number of dimensions and the size of element increases.

So when working with multi-dimension arrays in C, its good to consider the above details!