java - 行主序地址计算

Question

我正在计算转换为平面一维数组的 n 维数组的索引。

    private int toFlatindex(int... dimensionIndices){
    int index = 0;

    for (int k = dimensionIndices.length - 1; k >= 0; k--) {

        // Check if the specified index is within the bounds of the array
        if(dimensionIndices[k] < 0 || dimensionIndices[k] >= dimensionSizes[k]) {
            return -1;
        }

        // get the index in the flat array using the formula from https://en.wikipedia.org/wiki/Row-major_order#Address_calculation_in_general
        int start = 1;
        for (int l = dimensionSizes.length - 1; l >= k+1; l--) {
            start = start * dimensionSizes[l]; 
        }

        index += dimensionIndices[k]*start;
    }

    return index;
}

我已经编写了这段代码，它显示并测试正确。尽管我已经从维基百科编写了公式，但我并不完全理解发生了什么。我希望有人对此进行解释，或者更好地链接有关地址计算的视频教程/讲座。

Answer 1

让我们手动处理前几个维度。

对于单行的一维数组，元素 [k]位于k位置.

对于二维数组，元素 [j,k]指定k '行的第一个元素 j 。这是k + start of row j 。第 j 行的起始位置为 j * number of columns 。如果维度列在数组 dimensionSize 中，则列数为 dimensionSize[0] 。

将其放在一起，元素 [j,k]位于dimensionSize[0] * j + k .

对于 3d 数组，元素 [i,j,k]指定k '行的第一个元素 j在“平面”内i的元素立方体。这是k + start of row j in plane i 。平面 i 中第 j 行的起始位置为 i * size of plane + j * size of row 。把这些放在一起，元素 [i,j,k]位于

dimensionSize[0] * dimensionSize[1] * i + dimensionSize[0] * j + k.

另一种写法是

dimensionSize[0] * (dimensionSize[1] * i + j) + k.

这种模式正在显现。如果我们有一个 4d 数组，元素 [h,i,j,k]将会是

dimensionSize[0] * (dimensionSize[1] * (dimensionSize[2] * h + i) + j) + k

现在用数组 dimensionIndices[0..3] 替换索引 k,j,i,h您应该能够看到该函数正在对任意数量的维度进行此计算。

更简单的编码是:

int getOffset(int [] sizes, int [] indices) {
  int ofs = indices[sizes.length - 1];
  for (int d = sizes.length - 2; d >= 0; --d) {
    ofs = ofs * sizes[d] + indices[d];
  }
  return ofs;
}