多次元配列での配列オフセットの計算 (列対行優先)

行優先順のウィキペディアの記事が表示されます。 2 より大きい次元について説明したセクションがあります。ここにも良い記事があります。その記事では、行優先のレイアウトを使用した 3 次元配列の次の式を示しています。

Address = Base + ((depthindex*col_size+colindex) * row_size + rowindex) * Element_Size

3D 配列の場合:A[depth][col][row] と入力します。ベースは、配列の開始オフセットです。さらに、サイズ変数は各次元の異なるサイズです。 Element_Size 変数は、配列を構成する型のサイズを示します。

標準の C++ 整数で構成される行優先の配列 a[4][6][5] があるとします。 [1][3][2] のオフセットを計算するには、次の数値を式に代入します:

Address = Base + ((1 * 6 + 3) * 5 + 2) * 4

列優先のレイアウトを持つ 3 次元配列の場合、方程式は次のようになります。

Address = Base + ((rowindex*col_size+colindex) * depth_size + depthindex) * Element_Size

上記の例で列優先のレイアウトを使用してプラグインする数値は、次のようになります:

Address = Base + ((2 * 6 + 3) * 4 + 1) * 4

3 次元や 2 次元に焦点を当てて、人為的に自分を制約しないでください。代わりに、n 次元配列をアドレス指定するための式を学習することに集中してください .

n 次元のアドレス指定を表現すると、この主題についての理解が深まり、2 次元と 3 次元のアドレス指定の公式を別々に覚えるよりも、1 つの公式を覚えやすくなります。

n 次元アドレス指定の試みは次のとおりです:

#define LEN 10

int getValue_nDimensions( int * baseAddress, int * indexes, int nDimensions ) {
    int i;
    int offset = 0;
    for( i = 0; i < nDimensions; i++ ) {
        offset += pow(LEN,i) * indexes[nDimensions - (i + 1)];
    }

    return *(baseAddress + offset);
}

int main() {
    int i;
    int * baseAddress;
    int val1;
    int val2;

    // 1 dimensions
    int array1d[LEN];
    int array1d_indexes[] = {2};
    int array1d_nDimensions = 1;
    baseAddress = &array1d[0];
    for(i = 0; i < LEN; i++) { baseAddress[i] = i; }
    val1 = array1d[2];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array1d[2];
        baseAddress,
        &array1d_indexes[0],
        array1d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    // 3 dimensions
    int array3d[LEN][LEN][LEN];
    int array3d_indexes[] = {2,3,4};
    int array3d_nDimensions = 3;
    baseAddress = &array3d[0][0][0];
    for(i = 0; i < LEN*LEN*LEN; i++) { baseAddress[i] = i; }
    val1 = array3d[2][3][4];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array3d[2][3][4];
        baseAddress,
        &array3d_indexes[0],
        array3d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    // 5 dimensions
    int array5d[LEN][LEN][LEN][LEN][LEN];
    int array5d_indexes[] = {2,3,4,5,6};
    int array5d_nDimensions = 5;
    baseAddress = &array5d[0][0][0][0][0];
    for(i = 0; i < LEN*LEN*LEN*LEN*LEN; i++) { baseAddress[i] = i; }
    val1 = array5d[2][3][4][5][6];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array5d[2][3][4][5][6];
        baseAddress,
        &array5d_indexes[0],
        array5d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    return 0;
}

出力:

SANITY CHECK:     2     2
SANITY CHECK:   234   234
SANITY CHECK: 23456 23456

「行優先」と「列優先」という用語は、3 番目の次元にうまく変換できません。次に格納される要素が現在の行または現在の列からのものであるという概念は崩壊します。少しコミカルに聞こえますが、これは「深さ優先」対「幅優先」の順序になります。後続の各要素は、単一のエントリではなく、1 つの完全な 2 次元マトリックスです。

          / X
         / 
        +---+---+---+
       /   /   /   /|  
      +---+---+---+-+-------   
      | 1 | 5 | 9 |/|  Y
      +---+---+---+ +
      | 2 | 6 | A |/|
      +---+---+---+ +
      | 3 | 7 | B |/| 
      +---+---+---+ +
      | 4 | 8 | C |/
      +---+---+---+

したがって、メモリには文字通り1、2、3、4、5、6、7、8、9、10、11、12、13が順番にメモリに含まれます。これは、従来の列優先順序です。 X とマークされた位置に D エントリを配置しても、行列が列優先順であるという事実は変わりません。 Y の場所に D エントリを配置しても、列優先順序を使用しているという事実は変更されていません。次のブロックを配置する場所は、深さ方向 (X) または幅方向 (Y) の順序を使用している場合に影響します。ご存じのように、これらは等価ですが、何かと呼ぶと方程式を書くのに役立つかもしれません:

[ 0 ベースの配列を想定]

次の式を使用して、2 次元の列主要要素のメモリ位置にアクセスします。

MatrixOffset = base + (sizeof(entry) * ((4 * ( column - 1 ))   +  (row - 1)))

このアドレスは、深さまたは幅を使用して調整されますが、すべて用語の問題です.

TotalOffset = MatrixOffset + (sizeof(entry) * ((4 * 3) * (depth - 1))) 

または

TotalOffset = MatrixOffset + (sizeof(entry) * ((4 * 3) * (width - 1))) 

定数 4 と 3 は、変数 COLUMNS と ROWS である可能性があります。

4 次元については聞かないでください!