C中的矩阵表示

Question

我想找出C编程语言中amxn实矩阵的最佳表示.

矩阵表示作为单个指针的优点是什么:

double* A;

使用此表示,您可以分配内存:

A = (double* )malloc(m * n * sizeof(double));

在这种表示中,矩阵访问需要额外的乘法:

aij = A[i * m + j];

矩阵表示作为双指针的缺点是什么:

double** B;

内存分配需要一个循环:

double** B = (double **) malloc(m * sizeof(double*));
for (i = 0; i < m; i++)
    A[i] = (double *) malloc(n * sizeof(double))

在这种表示中,您可以使用直观的双索引`bij = B [i] [j],但是有一些缺点会影响性能.我想知道在性能方面什么是最好的演示.

这些矩阵应该用于数值算法,例如奇异值分解.我需要定义一个函数:

void svd(Matrix A, Matrix U, Matrix Sigma, Matrix V);

我正在寻找代表Matrix的最佳方式.如果有任何其他有效的方法来表示C中的矩阵,请告诉我.

我已经看到大多数人使用单指针表示.我想知道是否有一些性能优势而不是双数组表示？

Answer 1

查看所需的内存访问.

对于单指针案例,您有:

1. 读取指针(基地址),可能来自寄存器
2. 读取四个整数,可能是从寄存器或硬编码到指令集.对于array[i*m+j]中,4个值是i,m,j和sizeof(array[0]).
3. 乘以并加
4. 访问内存地址

对于双指针案例,您有:

1. 读取指针(基地址),可能来自寄存器
2. 读取索引,可能来自寄存器
3. 将索引乘以指针的大小并添加.
4. 从内存中获取基地址(不太可能是一个寄存器,可能在运行缓存中).
5. 读取另一个索引,可能来自寄存器
6. 乘以对象的大小并添加
7. 访问内存地址

您必须访问两个内存位置的事实可能使双指针解决方案比单指针解决方案慢得多.显然,缓存至关重要; 这就是为什么访问数组以使访问对缓存友好很重要的一个原因(因此您可以尽可能频繁地访问相邻的内存位置).

您可以在我的大纲中挑选细节,一些"乘法"操作可能是移位操作等,但一般概念仍然存在:双指针需要两次内存访问而不是一次单指针解决方案,这将是慢一点