I have read in several places that allocating multidimensional arrays as such is inefficient and should be avoided.
int main(){
int** arr2d = malloc(3*sizeof(int*));
for(int m = 0; m < 3 ; ++m){
arr2d[m] = malloc(sizeof(int)*3);
}
for(int m = 0 ; m < 3 ; ++m){
for(int n = 0; n < 3; ++n){
arr2d[m][n] = m+n;
}
}
for(int m = 0 ; m < 3 ; ++m){
for(int n = 0; n < 3; ++n){
printf("%d,",arr2d[m][n]);
}
printf("\n");
}
for(int m = 0; m < 3 ; ++m){
free(arr2d[m]);
}
free(arr2d);
return 0;
}
The alternative would be to allocate an array enough for m*n and index it accordingly giving the idea of 2D
int main(){
int* arr = malloc(9*sizeof(int));
for(int m = 0; m < 3; ++m){
for(int n = 0; n < 3; ++n){
int index = m*3+n;
arr[index] = m+n;
}
}
for(int m = 0; m < 3; ++m){
for(int n = 0; n < 3; ++n){
int index = m*3+n;
printf("%d,",arr[index]);
}
printf("\n");
}
free(arr);
return 0;
}
What I'm wondering is how much of a difference in terms of resource usage and timing does that really make? I know in the first example a total of 32 bytes are allocated and in the second example 27 bytes are allocated. When dealing with much larger matrices I can see that making a difference but does time complexity change or does it not matter since you're looping m*n number of times regardless? Should I always follow the second example as basically standard?
You can get the best of both worlds by allocating memory for a multidimentional array directly:
int (*arr)[3] = malloc(3 * sizeof *arr);
for(int m = 0 ; m < 3 ; ++m){
for(int n = 0; n < 3; ++n){
arr[m][n] = m+n;
}
}
for(int m = 0 ; m < 3 ; ++m){
for(int n = 0; n < 3; ++n){
printf("%d,",arr[m][n]);
}
printf("\n");
}
free(arr);
This creates the memory in a single contiguous block like the second example, allowing for more efficient reads and writes, and gives you 2D array indexing, allowing for easier to read code and for letting the compiler figure out the best way to index into the memory block internally.
If you have a rectangular matrix, i.e. all m x n values, then it is less tedious, less memory consumption and less error-prone to use the second option (though it arguably still is a matter of taster....).
The first option becomes more efficient if you do not have a rectangular thing, e.g. something like a array of differently long sub arrays.
Memory waste can get very relevant there.
Another example, back at matrices, would be a triangular matrix, with 0 or other know values outside of the triangle. Implementations could benefit from that attribute and use the "boring" or predictable values from outside the triangle, wihtout needing to store them.