C中常量人口减少的二维数组的内存有效存储

Question

在常量整数值的二维数组中，每行可能有不同数量的有效列。每行中的行数和列数是已知的且恒定的。它们可以与值一起放在结构的结构中，如下所示：

        typedef struct {
            uint32_t numColumns;
            uint32_t column[100];
        } row_T;
       
        typedef struct {
            uint32_t numRows;
            row_T    row[100];
        } array_T;

数组用常量值初始化（我不喜欢这是在编译时还是在运行时完成）：

        array_T a  = {0};

        a.numRows = 2;
        a.row[0].numColumns = 2; // two values in row 0
        a.row[0].column[0] = 7;
        a.row[0].column[1] = 17;
        a.row[1].numColumns = 5; // five values in row 1
        a.row[1].column[0] = 100;
        a.row[1].column[1] = 2;
        a.row[1].column[2] = 5;
        a.row[1].column[3] = 12;
        a.row[1].column[4] = 4;

然后可以通过以下方式单步执行数组：

        for (uint32_t i=0; i<a.numRows; i++) {
            for (uint32_t j=0; j<a.row[i].numColumns; j++) {
                //do something with a.row[i].column[j];
            }
        }

问题是每行中的列数可能会有很大差异。因此定义一个足够大的数组是对内存的浪费。

为不同长度的行定义类型，例如

        typedef struct {
            uint32_t numColumns;
            uint32_t column[5];
        } row_5_T;
       
        typedef struct {
            uint32_t numColumns;
            uint32_t column[2];
        } row_2_T;

和

        typedef struct {
            uint32_t numRows;
            row_2_T row_0;
            row_5_T row_1;
        } array_2_T;

内存效率高，但不允许使用循环计数器作为获取行数据的索引。

根据行和列索引 (i,j) 查找此类结构中每个条目的内存位置是可能的，但不方便：

1+(sum of numColumns+1 for columns 0..i-1)+1+j

欢迎提出任何优雅解决方案的建议。

Answer 1

我们可以将数据存储在元素类型（显然 uint32_t）的单个主数组中，其中一个数组指示每一行在主数组中的起始位置。

对于具有 NRows 行且每行包含 NColumns[i] 列的数组：

为偏移量分配 space：size_t *Offset = malloc(NRows * sizeof *Offset);。
计算偏移量：Offset[0] = 0; for (size_t r = 0; r < NRows; ++r) Offset[r] = Offset[r-1] + NColumns[r-1];。
为主阵列分配space：uint32_t *Array = malloc((Offset[NRows-1] + NColumns[NRows-1]) * sizeof *Array);.
遍历数组：

for (size_t r = 0; r < NRows; ++r)
    for (size_t c = 0; c < NColumns[r-1]; ++c)
        ... // Here array element r, c is in Array[Offset[r] + c].

我们还可以设置指向当前行开头的指针：

for (size_t r = 0; r < NRows; ++r)
{
    uint32_t *Row = Array + Offset[r];
    for (size_t c = 0; c < NColumns[r-1]; ++c)
        ... // Here array element r, c is in Row[c].
}

C中常量人口减少的二维数组的内存有效存储

memory efficient storage of a constant depopulated 2D array in C

c

arrays

memory-efficient