C 判断 "un-flattened"第i个元素在n维数组中的 "flattened"位置

Question

我有以下(不完整的)功能:

/* Populates char* name with the named location of the ith (flat) element
 * of an array with ndim dimensions where the length of each dimension 
 * is already stored in the int* dim.
 * 
 * name: a pointer to where the name should be populated
 * n: the base name of the array
 * dim: an int[] containing the length of each dimension
 * ndim: length of the dim array
 * i: name of the iteration variable being used
 **/
void populateName(char *name, const char *n, int *dim, int ndim, const char *i) {
  strcpy(name, n);
  char *loc = (char*)(name + strlen(n));
  char *curr;
  for (int k = 0; k < ndim; k++) {
    ...
    sprintf(loc, "[%s]", curr);
    loc += strlen(loc);
  }
}

for 循环中的“...”应该放什么？例如，调用 populateName() 时:

int dim[2] = {3, 4};
char name[1024];
populateName(name, "x", dim, 2, "i");

结果应该是这样的:

name = "x[i / 3][i % 4]"

或其他一些有效名称，用于访问定义为数组中的第 i 个位置:

int x[3][4];

上下文:我正在编写一个 C 程序，它生成 C 程序，这些程序根据用户定义的数据类型和用 IDL 编写的规则过滤大量数据。

编辑:返回包含数组中位置/坐标的元组的 python 函数可能会让我朝着正确的方向前进。特别是以下数组应使每个元素与其在数组中的平面位置相对应(此处使用 pylab):

In [14]: x
Out[14]: 
array([[[ 0,  1,  2],
    [ 3,  4,  5]],

   [[ 6,  7,  8],
    [ 9, 10, 11]],

   [[12, 13, 14],
    [15, 16, 17]]])

In [15]: x.flat.copy()
Out[15]: 
array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17])

Answer 1

解决此类问题的一个好方法是尝试一些示例。考虑下图，它显示了 3D 数组 x[2][3][5] 的内存布局:

我们如何将偏移量 14 转换到位置 x[0][2][4]？好吧，首先，我们看到每个 x[i] 包含 15 (3*5) 个 block ，因此首先我们通过计算整数除法 14/15 来确定 14 属于哪个 block = 0。因此，偏移量 14 位于 x[0] 内的某处。

我们现在可以应用相同的方法。 x[i][j] 包含 5 个 block ，因此偏移量 14 属于 block 号 14/5 = 2。实际上，正确的计算是 (14/5)%3，我们将看到对于偏移量 18。最后，x[i][j][k] 包含单个 block ，因此最后一个索引由 14%5 给出。可以这样想:我们正在解释这些内存块，就好像它们在每一步都有不同的大小。首先，我们假设所有内容都分成 15 个元素的 block 。然后，我们假设所有内容都分成 5 个元素的 block 。

你可以玩这个例子，看到偏移量 18 映射到 x[1][0][3] 因为 18/15 = 1; (18/5)%3 = 0，18%5 = 3。

可以看出，一般情况是对于维度n，我们将内存布局解释为好像它被组织在j block 中，其中j 是每个大于n 的维度的乘积，所以我们必须索引位置(i/j)%n。

这是我的实现:

void populateName(char *name, const char *n, int *dim, int ndim, const char *i) {
  strcpy(name, n);
  char *loc = (char*)(name + strlen(n));
  int j;
  int *mul = malloc(sizeof(int)*ndim);
  mul[ndim-1] = 1;
  /* Compute cumulative multipliers array */
  for (j = ndim-2; j >= 0; j--) {
    mul[j] = mul[j+1] * dim[j+1];
  } 
  for (j = 0; j < ndim; j++) {
    loc += sprintf(loc, "[(%s/%d)%%%d]", i, mul[j], dim[j]);
  }
  free(mul);
}

如您所见，它使用乘法器的累积数组，其中 mul[i] 保存大于 i 的每个维度的乘积。

顺便说一句，你不需要curr；由于 sprintf 返回打印的字符数，我们只需将 loc 移动相同的数量。它比在 sprintf 之后重复调用 strlen 更有效。

我没有太多时间来测试这个，但是通过我展示的例子，我明白了:

x[(i/15)%2][(i/5)%3][(i/1)%5]

这看起来是正确的。这是一个示例程序:

int main()
{
    int dims[] = { 2, 3, 5, 7, 9 };
    char name[1024];
    populateName(name, "x", dims, 5, "i");
    printf("%s\n", name);
    return 0;
}

这打印:

x[(i/945)%2][(i/315)%3][(i/63)%5][(i/9)%7][(i/1)% 9]

读取任意 n 维数组会变得更棘手，但原理始终相同。