3

我想找出 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 中的矩阵,请告诉我。

我已经看到大多数人使用单指针表示。我想知道与双数组表示相比是否有一些性能优势?

4

2 回答 2

5

查看所需的内存访问。

对于单指针情况,您有:

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

对于双指针情况,您有:

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

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

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

于 2013-11-03T10:18:06.890 回答
0

这里有几篇关于行主要格式的文章。

http://en.wikipedia.org/wiki/Row-major_order

http://fgiesen.wordpress.com/2011/05/04/row-major-vs-column-major-and-gl-es/

这些是 CUDA 编程中的常见结构;因此我的兴趣。

于 2013-11-03T10:18:10.960 回答