数据结构:密矩阵

             

   一般来说,矩阵的每个元在计算机内存中逐个储存,这种数据结构通常叫做密矩阵(dense matrix).由于在计算机内存中所有数据都是按顺序排成一行,所以在储存矩阵时我们就有两种选择,一是把矩阵所有行首尾相接,叫做行主序(row-major),二是把矩阵所有列首尾相接,叫列主序(column-major).例如对于 $2 \times 2$ 的矩阵 $ \boldsymbol{\mathbf{A}} $,列主序下,矩阵元在内存中的顺序依次 $A_{11}, A_{21}, A_{12}, A_{22}$,而在行主序下顺序为 $A_{11},A_{12},A_{21},A_{22}$.

   在 fortran 和 Matlab 中1,语言自带的矩阵都是列主序,而在 C/C++ 中如果用指针的指针(或数组的数组)来表示矩阵,得到的将会是行主序.当然,由于 C++ 的灵活性,我们完全可以创造行主序和列主序两种不同的矩阵类.由于 C++ 的数组的指标从 0 开始,那么矩阵的行标和列表也习惯从 0 开始.

   在我们用双索引寻找矩阵元时,我们需要先将其转换为单索引.假设矩阵尺寸为 $N_1 \times N_2$,那么

\begin{equation} \begin{aligned} &\begin{cases} n = i + N_1 j &\text{(列主序)}\\ n = N_2 i + j &\text{(行主序)} \end{cases}\\ &(i = 0, 1, \dots, N_1-1,\quad j = 0, 1, \dots, N_2-1) \end{aligned} \end{equation}

   行主序和列主序也可以延申至高维矩阵,如果使用列主序,那么当我们在内存中按顺序读取数据的时候,第 1 个索引(index)将变化得最快,第 2 个索引变化得第二快,最后得索引变化得最慢.行主序则相反,最后的索引变化得最快,而第一个最慢.例如 4 维数组的多索引变为单索引的公式为

\begin{equation} \begin{cases} n = i_1 + N_1 i_2 + N_1 N_2 i_3 + N_1 N_2 N_3 i_4 &\text{(列主序)}\\ n = N_2 N_3 N_4 i_1 + N_3 N_4 i_2 + N_4 i_3 + i_4 &\text{(行主序)} \end{cases} \end{equation}
从性能角度来看,单索引要比多个索引要快.

   若要由单索引计算多索引,我们可以用整数除法(向下取整)/ 和求余运算 %,例如对列主序的矩阵有

\begin{equation} \begin{cases} i = n \% N\\ j = n / N \end{cases} \end{equation}


1. ^ Matlab 最初就是由 fortran 编写的.

致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择会员制,大量广告,内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 10 元,我们一个星期内就能脱离亏损, 并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

         

© 小时科技 保留一切权利