Вычисления смещения массива в многомерном массиве (столбец vs row major)

Ответ 1

Когда я задал этот вопрос, я надеялся найти хорошие 3-мерные массивные примеры. Особенно примеры кода. Поскольку я не нашел ничего понятного, я решил создать небольшую программу на C, чтобы помочь отобразить концепцию. Он использует те же данные теста в массиве 3x4x5. Он также включает в себя тестовые данные для массива 5x5x5. Он создает основной массив столбцов из массива строк, поэтому вычисления смещения могут быть проверены.

Методы смещения массива:

//
// Arrays.cpp : 
//     Purpose: Display rowMajor & colMajor data and calculations.
//
#include "stdafx.h"

#define _show_Arrays 1  // 1=display rowMajor & colMajor arrays
#define _square_array 0 // 1=use arr[5][5][5], 0=use arr[3][4][5]

#if (_square_array == 1)
    const int depthSz = 5;
    const int rowSz = 5;
    const int colSz = 5;
    /*
    +---+---+---+---+---+
    |x00|x01|x02|x03|x04|
    +---+---+---+---+---+ 
    |x05|x06|x07|x08|x09|   
    +---+---+---+---+---+  
    |x0A|x0B|x0C|x0D|x0E|   
    +---+---+---+---+---+   
    |x0F|x10|x11|x12|x13|
    +---+---+---+---+---+ 
    |x14|x15|x16|x17|x18|
    +---+---+---+---+---+ 
          slice x          
    */
    short row_arr[depthSz][colSz][rowSz] = {
    { /* slice 0 */
      {0x000,0x001,0x002,0x003,0x004},
      {0x005,0x006,0x007,0x008,0x009},
      {0x00A,0x00B,0x00C,0x00D,0x00E},
      {0x00F,0x010,0x011,0x012,0x013},
      {0x014,0x015,0x016,0x017,0x018}},
    { /* slice 1 */
      {0x100,0x101,0x102,0x103,0x104},
      {0x105,0x106,0x107,0x108,0x109},
      {0x10A,0x10B,0x10C,0x10D,0x10E},
      {0x10F,0x110,0x111,0x112,0x113},
      {0x114,0x115,0x116,0x117,0x118}},
    { /* slice 2 */
      {0x200,0x201,0x202,0x203,0x204},
      {0x205,0x206,0x207,0x208,0x209},
      {0x20A,0x20B,0x20C,0x20D,0x20E},
      {0x20F,0x210,0x211,0x212,0x213},
      {0x214,0x215,0x216,0x217,0x218}},
    { /* slice 3 */
      {0x300,0x301,0x302,0x303,0x304},
      {0x305,0x306,0x307,0x308,0x309},
      {0x30A,0x30B,0x30C,0x30D,0x30E},
      {0x30F,0x310,0x311,0x312,0x313},
      {0x314,0x315,0x316,0x317,0x318}},
    { /* slice 4 */
      {0x400,0x401,0x402,0x403,0x404},
      {0x405,0x406,0x407,0x408,0x409},
      {0x40A,0x40B,0x40C,0x40D,0x40E},
      {0x40F,0x410,0x411,0x412,0x413},
      {0x414,0x415,0x416,0x417,0x418}}
    };

#else
  const int depthSz = 3;
    const int rowSz = 4;
    const int colSz = 5;
    /*
    +---+---+---+---+
    |000|001|002|003|  
    +---+---+---+---+  
    |004|005|006|007|   
    +---+---+---+---+   
    |008|009|00A|00B|   
    +---+---+---+---+   
    |00C|00D|00E|00F|
    +---+---+---+---+ 
    |010|011|012|013|
    +---+---+---+---+ 
         slice x
    */
    short row_arr[depthSz][colSz][rowSz] = {
    {  /* slice 0 */
      {0x000,0x001,0x002,0x003},
      {0x004,0x005,0x006,0x007},
      {0x008,0x009,0x00A,0x00B},
      {0x00C,0x00D,0x00E,0x00F},
      {0x010,0x011,0x012,0x013}},
    { /* slice 1 */
      {0x100,0x101,0x102,0x103},
      {0x104,0x105,0x106,0x107},
      {0x108,0x109,0x10A,0x10B},
      {0x10C,0x10D,0x10E,0x10F},
      {0x110,0x111,0x112,0x113}},
    {  /* slice 2 */
      {0x200,0x201,0x202,0x203},
      {0x204,0x205,0x206,0x207},
      {0x208,0x209,0x20A,0x20B},
      {0x20C,0x20D,0x20E,0x20F},
      {0x210,0x211,0x212,0x213}}
    };
#endif
    short col_arr[depthSz*colSz*rowSz]; //

char *calc_RowMajor(char *Base, int elemSz, int depth_idx, int row_idx, int col_idx)
{  // row major slice is navigated by rows
  char *address;
  int   lbound = 0; // lower bound (0 for zero-based arrays)
  address = Base        /* use base passed */
     + ((depth_idx-lbound)*(colSz*rowSz*elemSz))    /* select slice */
     + ((row_idx-lbound)*rowSz*elemSz)      /* select row */
     + ((col_idx-lbound)*elemSz);       /* select col */
    return address;
}
char *calc_ColMajor(char *Base, int elemSz, int depth_idx, int col_idx, int row_idx)
{  // col major slice is navigated by columns
  char *address;
  int   lbound = 0; // lower bound (0 for zero-based arrays)
  int   pageSz = colSz*rowSz*elemSz; 
  int   offset;

  offset = (col_idx-lbound)*(colSz*elemSz)  /* select column */
         + (row_idx-lbound)*(elemSz);   /* select row */
    if (offset >= pageSz)
    {   // page overflow, rollover
        offset -= (pageSz-elemSz);                          /* ajdust offset back onto page */
    }
    address = Base            /* use base passed */
            + ((depth_idx-lbound)*pageSz)  /* select slice */
            + offset;
    return address;
}

void disp_slice(char *pStr, short *pArr,int slice,int cols, int rows)
{
  printf("== %s slice %d == %p\r\n",pStr, slice,pArr+(slice*rows*cols));
  for(int x=0;x<rows;x++)
  {
    for(int y=0;y<cols;y++)
      printf("%03X ",*(pArr+(slice*rows*cols)+(x*cols)+y));
      printf("\r\n");
  }
}

int _tmain(int argc, _TCHAR* argv[])
{
  // initialize col based array using row based array data
  { // convert row_arr into col_arr
    short *pSrc = &row_arr[0][0][0];
    short *pDst = &col_arr[0];
    for(int d=0;d<depthSz;d++)
      for(int r=0;r<rowSz;r++)
        for(int c=0;c<colSz;c++)
        {
    *pDst++ = *(pSrc+((d*rowSz*colSz)+(c*rowSz)+r));
        }
  }

  printf("Using Array[%d][%d][%d]\r\n",depthSz,rowSz,colSz);

#if (_show_Arrays == 1)
  { for(int x=0;x<depthSz;x++) {disp_slice("rowMajor",&row_arr[0][0][0],x,rowSz,colSz);}}
  { for(int x=0;x<depthSz;x++) {disp_slice("colMajor",&col_arr[0],x,rowSz,colSz);}}
#endif

  int d = 2;    // depth
  int r = 3;    // row
  int c = 4;    // column

  for(d=0;d<depthSz;d++)
  { 
    c = r = d;  // simple access test pattern arr[0][0][0],arr[1][1][1],arr[2][2][2],...
    { // retrieve Array element
      printf("    row_arr[%d][%d][%d] = %x\t",d,r,c,row_arr[d][r][c]);
      printf("&row_arr[%d][%d][%d] = %p\r\n",d,r,c,&row_arr[d][r][c]);
    }
    { // retrieve RowMajor element
      short *pRowMajor = (short*)calc_RowMajor((char*)&row_arr[0][0][0],sizeof(short),d,r,c);
      printf("calc_RowMajor(%d,%d,%d) = %x\t\t",d,r,c,*pRowMajor);
      printf("pRowMajor = %p\r\n",pRowMajor);
    }
    {   // retrieve ColMajor element
      short *pColMajor = (short*)calc_ColMajor((char*)&col_arr[0],sizeof(short),d,c,r);
      printf("calc_ColMajor(%d,%d,%d) = %x\t\t",d,r,c,*pColMajor);
      printf("pColMajor = %p\r\n",pColMajor);
    }
 } // for

 getchar(); // just to hold the console while looking at the information
  return 0;
}

Ответ 2

Я бы посмотрел Строчный порядок в Википедии. Существует раздел, в котором описаны размеры выше 2. Здесь также есть хорошая статья . В этой статье приведена следующая формула для трехмерного массива с использованием макета строки:

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

Для трехмерного массива: тип A [глубина] [col] [строка]. Базой является начальное смещение массива. Кроме того, переменными размера являются разные размеры каждого измерения. Переменная Element_Size обозначает размер любого типа, из которого состоит массив.

Предположим, что у вас был массив строк major [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

Не искусственно ограничивайте себя, фокусируясь на трехмерном и двумерном. Вместо этого сосредоточиться на изучении выражения для адресации n-мерных массивов.

Выражение n-мерной адресации поможет вам понять эту тему и будет легче запомнить одну формулу, а не отдельные формулы для адресации 2d и 3d.

Здесь моя попытка 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

Ответ 4

Термины 'major major' и 'major major' не переводят хорошо на третье измерение. Понятие о том, что следующий элемент хранится из текущей строки или текущего столбца, разбивается. Это звучит немного комично, но это становится "большой глубиной" по сравнению с "широким основным" порядком. Каждый последующий элемент больше не является отдельной записью, кроме одной полной двухмерной матрицы.

          / 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 в памяти последовательно. Это классический порядок столбцов. Поместив запись D в позицию, помеченную X, вы не изменили того факта, что ваша матрица имеет порядок сортировки. Если вы поместите запись D, где Y, вы все равно не изменили тот факт, что используете основной порядок столбцов. Если вы решите разместить следующий блок, это повлияет, если вы используете упорядочение глубины (X) или ширину (Y). Поскольку вы хорошо знаете, что это эквиваленты, но называя это, что-то может помочь вам написать уравнения:

[0 предполагается, что на основе массива]

Вы получаете доступ к ячейке памяти для элемента с двумя размерами большого элемента через уравнение:

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-м размере!

Ответ 5

В основном в трехмерном аранжировке с основным строком. Например, Arr [3] [4] [5] когда u хотите Arr [0], он ищет передний срез изображения, как указано выше Arr [1] второй срез и так далее. поэтому Arr [0] означает двумерную матрицу размера [4] [5], поэтому каждое Arr [x] соответствует x * (4 * 5) Теперь об Arr [x] [y] можно думать о 1D массиве размера [5], положение которого [x] [y] сверху вниз на изображении выше поэтому, когда мы хотим, чтобы Arr [x] [y] = x * (4 * 5) + y * (5) теперь Arr [x] [y] [z] является конкретным элементом Arr [x] [y] на глубине z Орг [х] [у] [г] = х * (4 * 5) + у * 5 + г теперь, исходя из размера типа данных u, который нужно сохранить в массиве, смещение можно умножить на размер, получить адрес относительно начала

Ответ 6

Формула для k-мерных массивов

    k-1       n
i  + ∑  i  *  ∏  c
 0  n=1  n   m=0  m

где я индекс n - индекс размерности n для n = {0, 1, 2,... k-1} и c - индекс m - мощность размерности m при m = {0, 1, 2,... k-2}.

Более удобное отображение формулы в формате PNG можно найти здесь:

http://modula-2.info/m2r10/pmwiki.php/Spec/LanguageReport#MultiDimensionalArrays