多维数组索引。

Question

多维数组索引。

3

我在多个地方都看到过，通过这种方式分配多维数组是低效的，应该避免使用。

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;
}

另一种方法是分配足够 m*n 的数组，并相应地进行索引，从而得到 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;
}

我想知道在资源使用和时间上，这真的有多大的差别？我知道在第一个示例中总共分配了32个字节，在第二个示例中分配了27个字节。当处理更大的矩阵时，我可以看到这会有所不同，但是时间复杂度是否会改变还是无关紧要的，因为您不管怎样都需要循环m * n次？我应该总是遵循第二个示例作为基本标准吗？

- Kayla

2个回答

1

如果您有一个矩形矩阵，即所有 m x n 的值，则使用第二个选项会更少繁琐、更少占用内存，并且更少出错（虽然这仍然是一种口味问题）。

如果您没有一个矩形的东西，例如一个由不同长度的子数组组成的数组，则第一种选项变得更有效率。在那种情况下，内存浪费可能非常重要。

另一个例子，在矩阵上，将是一个三角形矩阵，其外部为 0 或其他已知值。实现可以从该属性中受益，并使用来自三角形外部的“无聊”或可预测的值，而无需对它们进行存储。

- Yunnosch

那么就时间复杂度而言，这真的没有太大的区别吗？ - Kayla

你关注的是什么复杂度？如果设置子 malloc/free 是一个相关的负担，那么需要将其考虑在内。它可能会超过收益/劣势。但是一般的预测是不可能的。像往常一样，在优化之前，你应该进行测量/基准测试。 - Yunnosch

我明白了，谢谢。我认为第一个虽然更易于查看和索引，但并没有太大的好处。 - Kayla

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dbush · Accepted Answer

通过直接为多维数组分配内存，您可以兼顾两者的优点：

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);

这会像第二个例子一样在单个连续块中创建内存，从而实现更有效的读写操作，并为您提供2D数组索引，使代码更易于阅读，并让编译器确定内部索引内存块的最佳方法。