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?

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

The time complexity you're referring might not make much of a difference when accessing since you already realize you're iterating m * n. There could be a difference in the allocation and deallocation process if the arrays are very large. The memory usage is definitely a difference since assuming you're iterating 10x10 then in the first example you're allocating (10*sizeof(pointer)) 10*sizeof(var) as apposed to 100*sizeof(var) which would be less memory usage.

There isn't a standard for how arrays should be indexed there is preference involved but as far as I've seen people prefer the second example or the answer that dbush provided earlier.