C++ - 悲催的科学匠人 - 冷水's blog

C++中实现动态多维数组模板的分析-04

对于一维化存储的数据，实现多维编号访问，索引是必须的。

考虑2D数组 array[0..I-1][0..J-1]，为了方便采用FORTRAN的数组元素排列顺序，即

for （j=0；j<J;j++)
for （i=0；i<I;i++)

那么一维编号

$n=i+j \times I$

为了避免乘法，我们可以预先计算好 S_j(j)=j*I 。则有一维编号计算公式为

n=i+S_j(j)

代价是我们必须事先计算好个 S_j(j) 。

再考虑3D数组 array[0..I-1][0..J-1][0..K-1]，其一维编号计算公式为

n=i+j*I+k*J*I

同理，令 $S_j(j)=j\times I$ 和 $S_k(k)=k\times J\times I$ ，上式可写为

n=i+S_j(j)+S_k(k)

这个方法可以推导到任意维数组。即对于维数组，设其第维范围是 $\left[ 0 \dots D_i-1 \right ]$ ,我们事先计算好偏移

$S_i(i)=\prod_{k=1,i-1}D_k$ $S_i(i)=\prod_{k=1,i-1}D_k \qquad ,i>1$

此外对于第一维

$$ S_1=1 $$

则元素 $[k_1][k_2]\dots[k_i]\dots[k_N]$ 的一维编号计算格式为

$n=\sum_{i=1}^{N} k_iS_i(k_i)$

这样对于多维数组 $A[N_1][N_2]\dots[N_n]$ ，只需要实现计算好 $N_1+N_2+\dots +N_n$ 个常数，即可采用上式来快速计算一维编号。

C++中实现动态多维数组模板的分析-03

基本上，我计划采用的方案是：

数据在内部采用一维数组方式存储。这样数据在内存中连续分布，有利于cach命中（其实我也不知道这个名称确切意义）。这对高性能计算这样的应用来说是必须的。
在数组类中封装若干索引数据，以支持多维指标到一维指标的互相转换。
索引数据可单独封装为一个类，实现数据和维数表达的分离。以便于多个数组对象之间共享，或者数组维数变化情况。
索引数据应该尽量的少。C语言中利用指针数组实现多维特性是不可以接收的，因为指针数组的维数只比数据数组的维数少了一维而已。当数组很大时（比如要几个G的空间），指针数组也很大，造成空间浪费。在我所考虑的方案中，对于数组[L][M][N]，只需要L+M+N个size_t类型的索引。因此，即使L*M*N很大（比如1000*1000*1000），L+M+N（才3000而已）也很小。
目前不打算支持动态的数组尺寸。但是当基本功能实现之后，这个特性应该不难扩展。

C++中实现动态多维数组模板的分析-02

我希望，一个多维数组模板类可以做到以下几点：

轻易的实现多维数组动态构造，无需使用者人工对多维指针进行设置，比如只需要一个对象定义就搞定。
如同FORTRAN一样，对各维的范围没有限制，如从-20到13这样的范围。C/C++是非得从0开始，这在很多时候是不方便的。
对维数没有限制，或者限制小。FORTRAN似乎支持最高到7维数组，我认为这个限制是不合适的，应该突破。
可以类似对数组阵列的形状（包括维数和各维尺寸）进行改变，比如开始定义为20X30，使用中可以调整为30X20或者6000或者10X6X100。
既可以通过多维指标来访问（如[i,j,k]），又可以通过一维化指标访问（如[n]），这在很多时候也是很有用的，至少循环的时候可以只用一层for语句。
支持多种数据类型，这个通过模板容易实现。
……还没想好，以后再补充

C++中实现动态多维数组模板的分析-01

C++原生多维数组与FORTRAN原生数组功能差远了。不明白为什么不在标准中把多维数组加强一些，本来这也不是什么难事。如果说用stl::vector可以实现就不做了，那也太差强人意了。boost::multiarray采用了一些高级技术，使得访问方式和原生数组一致。但是性能不佳，比原生数组性能第一个量级，完全无法接收。

在早期的FORTRAN中，动态多维数组采取一维化分配，然后映射为多维数组。一些C编写的数值计算程序也采取类似的方法。这样做能够保证性能，但是C中使用起来不方便。

我希望依然沿用一维化方式，但是采用C++封装内部的映射和指标转化算法，使得使用简便。我不追求与原生数组一致的[]访问方式，因为这样会为了表观的完美而引入复杂的机制，而本末倒置的降低性能。