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

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

这里先给出arrayindex类的源代码。

#ifndef ARRAYINDEX_HPP
#define ARRAYINDEX_HPP

#include <cstring>
#ifdef debug0
  #include <cstdio>
#endif


class ArrayIndex
{
  public:
    ArrayIndex(size_t ndim, int ranges[][2]);
    ~ArrayIndex(void);

    size_t Getsidx(int a_midx[], int& o_stat);
    void   Getmidx(size_t a_sidx,  int o_midx[]);
    size_t Getlength(void);
    size_t Getndim(void);
    size_t Getdim(size_t a_n);
    void   Getrange(size_t a_dim, int o_range[2], int& o_stat);


  public:
    enum{NORMAL, WRONG_DIM, WRONG_RANGE};
  private:
    size_t length_;
    size_t ndim_;
    size_t maxdim_;
    size_t *dims_;
    size_t *size_;
    size_t **shift_;
    int **range_;
};

inline   size_t ArrayIndex::Getlength(void)
{
  return length_;
}


inline  size_t ArrayIndex::Getndim(void)
{
   return ndim_;
}

inline  size_t ArrayIndex::Getdim(size_t a_n)
{
   return dims_[a_n];
}

inline void  ArrayIndex::Getrange(size_t a_dim, int o_range[2], int& o_stat)
{
  if(a_dim>=ndim_) {o_stat = ArrayIndex::WRONG_DIM; return;}

  o_range[0] = range_[a_dim][0];
  o_range[1] = range_[a_dim][1];
  o_stat = ArrayIndex::NORMAL;
  return;
}


size_t ArrayIndex::Getsidx(int a_midx[], int& o_stat)
{
  size_t sidx=a_midx[0]-range_[0][0];
  for(size_t n=1;n<ndim_;n++)
  {
    sidx += shift_[n][ a_midx[n]-range_[n][0] ];
  }
  return sidx;
}


void ArrayIndex::Getmidx(size_t a_sidx, int o_midx[])
{
  size_t loc = a_sidx;
  for(size_t n=ndim_-1; n>0; n--)
  {
     for(size_t m=0;m<dims_[n];m++)
     if( loc >= shift_[n][m] )   o_midx[n] = m;

     loc -= shift_[n][ o_midx[n] ];

     o_midx[n]  += range_[n][0];
  }
  o_midx[0] = loc + range_[0][0];
}



ArrayIndex::ArrayIndex(size_t ndim, int ranges[][2]):
ndim_(ndim),
range_(NULL)
{

  range_ = new int* [ndim_];
  range_[0] = new int [ndim_ * 2];
  for(size_t n=1;n<ndim_;n++)  range_[n] = range_[n-1] + 2;


  dims_ = new size_t[ndim_];
  size_ = new size_t[ndim_];


  length_ = 1;
  maxdim_ = 0;
  for(size_t n=0;n<ndim_;n++)
  {

    dims_[n] = ranges[n][1] - ranges[n][0] + 1;
    range_[n][0] = ranges[n][0];
    range_[n][1] = ranges[n][1];

    size_[n] = length_;
    length_ *= dims_[n];
    if(dims_[n]>maxdim_)  maxdim_ = dims_[n];

  }

  shift_ = new size_t* [ndim_];
  shift_[0] = new size_t[maxdim_*ndim_];
  for(size_t n=1;n<ndim_;n++)  shift_[n] = shift_[n-1] + maxdim_;

  for(size_t n=1;n<ndim_;n++)
  {
    shift_[n][0] = 0;
    for(size_t m=1;m<dims_[n];m++)
    {
       shift_[n][m] = shift_[n][m-1] + size_[n];
    }
  }


  return;
}



ArrayIndex::~ArrayIndex(void)
{
  delete [] shift_[0];
  delete [] shift_;

  delete [] range_[0];
  delete [] range_;


  delete [] size_;
  delete [] dims_;
}



#endif

还有一个测试代码

#include "qkarray.hpp"

int main(void)
{
   int stat;
   size_t ndim=5;
   int    range[5][2] = {{1,2},{5,7},{1,5},{9,10},{1,1}},  midx[20];


   ArrayIndex index(ndim,range);
   index.Getrange(4, range[0], stat);



   if(ndim==5)
   {

     size_t count = 0;
     for(size_t n=0;n<ndim;n++) {
       midx[n] = 0;
       index.Getrange(n,range[n],stat);
       printf(" Range[%5ld] = %5ld:%5ld\n", n, range[n][0],range[n][1]);
     }
     printf(" Array size = %d\n",index.Getlength() );

     count = 0;
     for(int m=range[4][0];m<=range[4][1];m++)
     for(int l=range[3][0];l<=range[3][1];l++)
     for(int k=range[2][0];k<=range[2][1];k++)
     for(int j=range[1][0];j<=range[1][1];j++)
     for(int i=range[0][0];i<=range[0][1];i++)
     {
        midx[0] = i; midx[1] = j; midx[2] = k; midx[3] = l;midx[4] = m;
        index.Getmidx(count, midx);
        count ++;
        printf("[%5ld] [%5ld] [%5ld] [%5ld] [%5ld] == %5ld \n", midx[0], midx[1], midx[2], midx[3],midx[4],
          index.Getsidx(midx, stat));
     }
   }

   return 1;

}

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

在分析04中，我写出了多维编号到一维编号的转换关系。不过那时假设多维编号采用C风格，都是从0开始的。实际我需要支持非0开始的编号，即可以从任一一个整数a开始以1递增到另外一个不小于a的整数b。在这种情况下，要将非0开始的多维编号转换为内部以0开始的编号，就可以使用前述的公式了。

这次，开始进行设计。

首先命名这个类为 arrayindex

它必须具备的最重要的方法有

1 根据给定的维数和每个维的范围创建一个实例

ArrayIndex(size_t ndim, int ranges[][2]);

ndim是一个非负数，表示维数。range是每个维的范围range[i][0]是起始编号，

range[i][1]是终止编号。为了方便，令i>=1

2 从一个多维编号转换到一维编号

size_t Getsidx(int a_midx[], int& o_stat);

a_midx[]存储多维编号，为方便起见，从a_mix[1]开始有效。

3 从一个一维编号转换到多维编号

void Getmidx(size_t a_sidx, int o_midx[]);

这个类的关键成员应该包含
    size_t length_; // 数组数据总个数
    size_t ndim_;    // 维数
    size_t maxdim_; // 最大维数
    size_t *dims_;   // 每个维的尺寸
    size_t *size_;   // 每个维度上切片的尺寸。比如，数组[5][3][2],第一维是一维的串，它的切片就是单个元素，尺寸为1；第二维是一个二维的片，其切片是低一维的串，每个串的尺寸是5；第三维是一个三维块，其切片是低一维片，尺寸是5X3。如此类推到更高维。
    size_t **shift_; // 每个维上所有标号的偏移。比如数组[5][3][2]，按照我们先前的分析，必须存储第一维的5个偏移，第二维的3个偏移和第三维的2个偏移。因此shift_是个二维数组。
    int **range_;    // 每个维的范围

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而已）也很小。
目前不打算支持动态的数组尺寸。但是当基本功能实现之后，这个特性应该不难扩展。

« 上一页 1 2 … 5 6 7 8 9 10 11 12 13 下一页 »