Alternative to multidimensional array in c

Question

tI has 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 execute the following data:

 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 tried to come up with a more elegant, less brainwave approach. (I know that this multidimensional array is inefficient in terms of processor usage, but in this case it does not matter.) Is there a better approach to how I structured here?

Answer 1

If you need a 4D array, then what you need. This allows it to be "flattened" into the one-dimensional array malloc() ed ", however it is not so clean:

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

Access is also difficult:

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

So obviously a little pain.

But you have the advantage that if you just need to iterate over each individual element, you can do:

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

Obviously, this method is terribly ugly for most applications and slightly simplified for one type of access. It is also a bit more conservative for memory and requires only one dereference pointer, not 4.

Answer 2

NOTE. The intent of the examples used in this post is simply an explanation of the concepts. Thus, the examples may be incomplete, there may be no error handling, etc.

When it comes to using a multidimensional array in C , the following are two possible ways.

Array smoothing

In C arrays are implemented as a contiguous block of memory. This information can be used to manage the values ​​stored in the array and provides quick access to a specific location of the array.

For instance,

 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 method of using 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 a dangling array and is useful in places where variable strings are used. A popular method is to perform dynamic-memory-allocation for each dimension.

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

Comparison of Flattened and Dangling Arrays

Now consider the following code snippet that compares 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 

In the above example, ragged arrays require 631-pointers , in other words, 631 * sizeof(int *) extra memory locations to indicate integers 6000 . While for the flattened array only one base pointer is needed: i.e. The name of the array is enough to point to adjacent memory cells 6000 .

But OTOH, ragged arrays are flexible. In cases where the exact number of required memory locations is unknown, you cannot afford to allocate memory for the worst case scenario. Again, in some cases, the exact amount of required memory space is known only at run time. In such situations, ragged arrays become convenient.

Array of rows and columns of arrays

C follows the row-major order for multidimensional arrays. Flattening arrays can be seen as an effect due to this aspect in C The row-major C order value corresponds to it naturally, in which most of the access is done in programming. For example, let's look at an example for moving an 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 ​​drawn one after another, quickly changing the column. Array C is arranged in memory in this natural way. On the 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 most often changes the column index than the row index. And because of this, there is a big difference in performance between these two pieces of code. Yes, the first one is more effective than the second!

Since the first one accesses the array in a natural ( row-major order) C, therefore, it is faster, while the second takes longer to transition. The difference in performance will expand as the size and size of the item increases.

Therefore, when working with multidimensional arrays in C , it is useful to consider the above details!