替代在C多維數組

Question

TI有以下代碼：

#define FIRST_COUNT 100 
#define X_COUNT 250 
#define Y_COUNT 310 
#define z_COUNT 40 

struct s_tsp { 

    short abc[FIRST_COUNT][X_COUNT][Y_COUNT][Z_COUNT]; 
}; 

struct s_tsp xyz; 

我需要通過這樣的數據來運行：

for (int i = 0; i < FIRST_COUNT; ++i) 
    for (int j = 0; j < X_COUNT; ++j) 
      for (int k = 0; k < Y_COUNT; ++k) 
       for (int n = 0; n < Z_COUNT; ++n) 
         doSomething(xyz, i, j, k, n); 

我試圖想到一個更優雅，更少的腦死亡方法。 （我知道這種多維數組在cpu使用方面效率很低，但在這種情況下這是無關緊要的。）有沒有更好的方法來處理我在這裏構造的東西？

Answer 1

如果你需要一個4D陣列，那麼這就是你需要的。這是可能的「扁平化」成一維malloc()版「數組」，然而這是不是很乾淨：

abc = malloc(sizeof(short)*FIRST_COUNT*X_COUNT*Y_COUNT*Z_COUNT); 

是否訪問也都比較困難：

*(abc + FIRST_COUNT*X_COUNT*Y_COUNT*i + FIRST_COUNT*X_COUNT*j + FIRST_COUNT*k + n) 

所以，這顯然有點的痛苦。

但是你做的優勢在於，如果你需要簡單地遍歷每一個元素，你可以這樣做：

for (int i = 0; i < FIRST_COUNT*X_COUNT*Y_COUNT*Z_COUNT; i++) { 
    doWhateverWith *(abc+i); 
} 

顯然，這種方法對於大多數用途非常難看，而且是一個有點整潔訪問類型。這也是一個更多的內存保守，只需要一個指針取消引用，而不是4.

Answer 2

注意：本文中使用的示例旨在解釋這些概念。因此，這些示例可能不完整，可能缺少錯誤處理等。

當涉及到在C中使用多維數組時，以下是兩種可能的方法。

陣列

在C扁平化的，陣列被實現爲一個連續存儲器塊。這些信息可以用來處理存儲在數組中的值，並允許快速訪問特定的數組位置。

例如，

int arr[10][10]; 
int *ptr = (int *)arr ; 

ptr[11] = 10; 
// this is equivalent to arr[1][0] = 10; assign a 2D array 
// and manipulate now as a single dimensional array. 

利用陣列的鄰接的性質被稱爲flattening of arrays的技術。

襤褸陣列

現在，考慮下面的例子。

char **list; 
list[0] = "United States of America"; 
list[1] = "India"; 
list[2] = "United Kingdom"; 
for(int i=0; i< 3 ;i++) 
    printf(" %d ",strlen(list[i])); 
// prints 24 5 14 

這種類型的實現被稱爲粗糙陣列，並且其中可變大小的字符串被用來在地方是有用的。流行的方法是在每個維度上完成dynamic-memory-allocation。

注意：命令行參數（char *argv[]）僅作爲不齊的數組傳遞。

比較扁平且粗糙的陣列

現在，讓我們考慮下面的代碼片斷，其比較所述flattened和ragged陣列。

/* Note: lacks error handling */ 
int flattened[30][20][10]; 
int ***ragged; 
int i,j,numElements=0,numPointers=1; 
ragged = (int ***) malloc(sizeof(int **) * 30); 
numPointers += 30; 
for(i=0; i<30; i++) { 
    ragged[i] = (int **)malloc(sizeof(int*) * 20); 
    numPointers += 20; 
    for(j=0; j<20; j++) { 
     ragged[i][j]=(int*)malloc(sizeof(int) * 10); 
     numElements += 10; 
    } 
} 

printf("Number of elements = %d",numElements); 
printf("Number of pointers = %d",numPointers); 

// it prints 
// Number of elements = 6000 
// Number of pointers = 631 

從上面的例子中，ragged陣列需要631-pointers，換句話說，用於指向6000整數631 * sizeof(int *)額外的存儲器位置。而flattened數組只需要一個基址指針：即數組名稱足以指向連續的6000存儲位置。

但是OTOH，ragged陣列是靈活的。在不知道所需存儲位置的確切數量的情況下，您無法爲最壞的情況分配內存。同樣，在某些情況下，只有在運行時才知道所需的確切存儲空間數量。在這種情況下，ragged陣列變得非常方便。

行優先和陣列的列優先

C如下row-major排序爲多維陣列。在C中，陣列的Flattening可被視爲由於此方面的影響。 C的row-major的意義在於它適合在編程中進行大部分訪問的自然方式。例如，讓我們來看一個例子用於穿越N * M 2D矩陣，

for(i=0; i<N; i++) { 
    for(j=0; j<M; j++) 
     printf(「%d 」, matrix[i][j]); 
    printf("\n"); 
} 

矩陣中的每行被訪問一個接一個，由快速變化的列。這種自然的方式將C陣列排列在內存中。相反，請考慮以下示例，

for(i=0; i<M; i++) { 
    for(j=0; j<N; j++) 
     printf(「%d 」, matrix[j][i]); 
    printf("\n"); 
} 

這會比列索引更頻繁地更改列索引。正因爲如此，這兩個代碼片段之間的效率差別很大。是的，第一個比第二個更有效率！

因爲第一個按照C的自然順序（row-major順序）訪問數組，所以它更快，而第二個需要更多的時間來跳轉。隨着尺寸數量和元件尺寸的增加，性能差異會變寬。

所以當在C中使用多維數組時，很好考慮上面的細節！