Hiệu suất mảng 2 chiều so với mảng 1 chiều

Question

Trong C, có sự khác biệt về thời gian và không gian giữa mảng m × n 2 chiều so với mảng 1 chiều có chiều dài m × n (với giá trị lớn của m và n)? Các yếu tố truy cập sẽ nhanh hơn với mảng 1 chiều?

Answer 1

Trong C, mảng 2 chiều chỉ là lược đồ lập chỉ mục gọn gàng cho mảng 1 chiều. Cũng giống như với mảng 1D, mảng 2D phân bổ một khối bộ nhớ tiếp giáp, và ký hiệu A[row][col] tương tự như nói A[row*NCOLS+col].

Thông thường nếu bạn đã thực hiện các mảng đa chiều của riêng bạn sử dụng các mảng chiều duy nhất, bạn muốn viết một chức năng lập chỉ mục:

int getIndex(int row, int col) { return row*NCOLS+col; } 

Giả sử inlines trình biên dịch của bạn chức năng này, việc thực hiện ở đây sẽ được chính xác giống như nếu bạn đã sử dụng chức năng 'lập chỉ mục' được xây dựng trong các mảng 2D.

Để minh họa:

#define NROWS 10 
#define NCOLS 20 

này:

int main(int argc, char *argv[]) { 
    int myArr[NROWS*NCOLS]; 
    for (int i=0; i<NROWS; ++i) { 
     for (int j=0; j<NCOLS; ++j) { 
      myArr[getIndex(i,j)] = i+j; 
     } 
    } 
    return 0; 
} 

nên thực hiện tương tự như này:

int main(int argc, char *argv[]) { 
    int myArr[NROWS][NCOLS]; 
    for (int i=0; i<NROWS; ++i) { 
     for (int j=0; j<NCOLS; ++j) { 
      myArr[i][j] = i+j; 
     } 
    } 
    return 0; 
} 

Mặc dù như AraKpointed out, nếu bạn đang nhảy xung quanh hàng rất nhiều và các hàng rất lớn, bạn có thể gặp nhiều lỗi trang ... trong trường hợp đó, Chức năng lập chỉ mục om (với các hàng và cols chuyển xung quanh) có thể hữu ích, nhưng chỉ đơn giản là thay đổi kích thước nào trong mảng 2 chiều mà bạn coi là các hàng và bạn coi các cột đó là cột nào.

Answer 2

Tôi không nghĩ có bất kỳ sự khác biệt nào. Bên trong, c xử lý một mảng hai chiều giống như một số mảng một chiều theo thứ tự.

Tuy nhiên, như với tất cả mọi thứ về hiệu suất, số dặm của bạn có thể thay đổi. Có thể có một số loại sự khác biệt số học con trỏ tinh tế. Chạy thử nghiệm theo thời gian trên cả hai trường hợp. Cho dù ai chạy chiến thắng nhanh hơn.

Answer 3

Tôi chỉ đoán, nhưng tôi sẽ nói rằng mảng 1d nhanh hơn mảng 2d. Tuy nhiên, nó sẽ không thể đo được nhanh hơn. Loại như $ 1,000,000.01 là hơn $ 1.000.000.

Tôi muốn sử dụng mọi thứ dễ dàng hơn để mã hóa.

Answer 4

Thực ra, nếu bạn sử dụng mảng hai chiều trong C, trình biên dịch sẽ thực hiện ánh xạ thành mảng một chiều cho bạn. Nếu bạn sử dụng mảng một chiều và bạn muốn coi nó như là một chiều hai chiều, thì bạn phải tự viết bản đồ.

Điều duy nhất mà bạn phải quan tâm là bạn nên truy cập mảng hàng-khôn ngoan, bởi vì trình biên dịch C sẽ lưu trữ hàng mảng hai chiều của bạn sau hàng. Nếu bạn truy cập vào một mảng lớn hai chiều thì các lỗi trang có thể xảy ra. Ngay cả khi bạn đang lập trình bằng ngôn ngữ chỉ hỗ trợ mảng một chiều, bạn có thể dễ dàng viết ánh xạ vào bất kỳ số thứ nguyên nào.

Hãy xem bài viết Wikipedia này nếu bạn muốn thực hiện mapping row-wise. Lập bản đồ của bạn có thể là cột khôn ngoan, chẳng hạn như ma trận FORTRAN chẳng hạn.

Answer 5

Robert là chính xác.Các biểu thức lập chỉ mục được biên dịch thành các biểu thức số học con trỏ và do đó không có sự khác biệt.

Tuy nhiên, những gì có thể có tác động là thứ tự truy cập và do đó bạn có thể muốn tự mình triển khai mọi thứ để bạn có thể kiểm soát thứ tự truy cập. Ví dụ cột đầu tiên so với hàng đầu tiên hình thức.

Trên các bộ xử lý hiện đại, truy cập các mảng lớn ở các bước khác nhau có thể có sự khác biệt về hiệu suất không mong muốn. Truy cập tuần tự luôn nhanh nhất và các bước khác có thể chậm hơn tới 30 lần do tương tác bộ nhớ cache. Mảng đa chiều trong đó các kích thước bên trong là một sức mạnh của hai thường có hiệu suất kém vì chúng tương tác với bộ nhớ cache kết hợp. Để hiểu những vấn đề này, không có thay thế thực sự để thực hiện đo lường.

Answer 6

Như đã nói khác, sự khác biệt thực sự là cách bạn truy cập các mục của bạn: điều quan trọng là cách các mục của bạn được bố trí trong bộ nhớ, tuyến tính, ít nhất là trên các kiến ​​trúc chung. Vì vậy, tất cả những gì bạn thực sự là mảng 1d, 2d, v.v ... chỉ là "tiện lợi" và trình biên dịch hợp lý nên tối ưu hóa việc lập chỉ mục - nhưng trong thực tế, một khi bạn có nhiều biến, trình biên dịch thường không thành công như x86 vì sự chết đói.

Bây giờ, tùy thuộc vào ứng dụng của bạn, nhưng tôi nghĩ bạn nên nghĩ đến bố cục 1d theo mặc định, đặc biệt là nếu bạn cần xử lý nhiều thứ nguyên. Vấn đề đầu tiên với mảng đa chiều trong C là bạn không thể phân bổ động chúng - nếu bạn phân bổ trên cơ sở mỗi hàng, bạn sẽ có những màn trình diễn khủng khiếp vì bạn không có bộ nhớ liền kề. Xem FFTW doc để biết chi tiết về điều này. Lưu ý rằng bạn luôn có thể mô tả bộ nhớ duy nhất của bạn với chỉ mục mảng thuận tiện trên đầu trang của nó (bạn phân bổ một khối bộ nhớ nxm lớn và sau đó tạo một mảng con trỏ n cho mỗi hàng).