Cấu trúc dữ liệu và Giải thuật Bài 14: Mảng đa chiều: Cấu trúc ma trận và cách lưu trữ Row-major/Column-major.

Trong thực tế, dữ liệu không phải lúc nào cũng là một danh sách phẳng 1 chiều. Khi bạn xử lý hình ảnh (mỗi pixel là một điểm ảnh), làm việc với bảng tính Excel, hay lập trình lưới tọa độ cho một bản đồ trong game, bạn đang làm việc với Mảng đa chiều (điển hình nhất là mảng 2 chiều - Ma trận).

Cú pháp khai báo trong các ngôn ngữ lập trình (như matrix[row][col]) mang lại cho chúng ta cảm giác dữ liệu được xếp thành một hình chữ nhật hoàn hảo. Nhưng đó chỉ là ảo giác mà trình biên dịch tạo ra. Ở tầng vật lý, sự thật phũ phàng hơn nhiều.

1. Sự thật về RAM: Không có "hình chữ nhật" nào cả

Hãy nhớ lại Bài 2: RAM Model. Bộ nhớ máy tính là một dải băng dài, 1 chiều, nối tiếp nhau từ ô nhớ 0 đến ô nhớ $N$. Không có khái niệm "hàng" hay "cột" trong phần cứng.

Vậy làm thế nào hệ điều hành "nhét" một ma trận 2D kích thước $3 \times 4$ (3 hàng, 4 cột) vào một đường thẳng 1D? Máy tính phải có một quy tắc để "duỗi thẳng" ma trận này ra. Có hai trường phái thiết kế để thực hiện việc này: Row-major Order (Ưu tiên hàng) và Column-major Order (Ưu tiên cột).

2. Row-major Order (Ưu tiên hàng)

Đây là cách lưu trữ mặc định của hầu hết các ngôn ngữ lập trình hiện đại như C/C++, Golang, Python, PHP, Java.

Trong Row-major, máy tính sẽ cắt ma trận theo từng hàng ngang, và xếp hàng này nối tiếp hàng kia vào bộ nhớ.

Giả sử bạn có ma trận:

Plaintext

[A, B, C, D] -> Hàng 0
[E, F, G, H] -> Hàng 1
[I, J, K, L] -> Hàng 2

Khi duỗi thẳng vào RAM, nó sẽ nằm liền tù tì như sau:

[ A, B, C, D, E, F, G, H, I, J, K, L ]

Công thức ánh xạ thần thánh $O(1)$:

Để lấy phần tử ở hàng i, cột j, máy tính không cần duyệt qua mảng. Nó sử dụng công thức toán học nội tại:

$\text{Vị trí 1D} = (i \times \text{Số cột}) + j$

Ví dụ: Để tìm phần tử G ở hàng 1, cột 2 (số cột tổng cộng là 4):

Vị trí = $(1 \times 4) + 2 = 6$. Nhìn lên dải RAM phía trên, phần tử ở chỉ số 6 chính xác là G. Thời gian truy xuất vẫn luôn là $O(1)$.

3. Column-major Order (Ưu tiên cột)

Ngược lại, một số ngôn ngữ chuyên biệt cho tính toán khoa học và thống kê như Fortran, MATLAB, R lại sử dụng Column-major.

Trong mô hình này, máy tính cắt ma trận theo từng cột dọc, và nối các cột lại với nhau.

Cùng ma trận trên, khi vào RAM nó sẽ trông thế này:

[ A, E, I, B, F, J, C, G, K, D, H, L ]

Công thức ánh xạ lúc này thay đổi thành:

$\text{Vị trí 1D} = (j \times \text{Số hàng}) + i$

4. Tại sao bạn bắt buộc phải biết điều này? (Cạm bẫy hiệu năng)

Bạn có thể nghĩ: "Hàng hay cột thì sao chứ? Kết quả truy xuất matrix[i][j] vẫn là $O(1)$ mà!". Về mặt Big-O toán học thì đúng, nhưng về mặt Hiệu năng thực tế của CPU, đây là yếu tố phân biệt giữa một đoạn code chạy mất 1 giây và 10 giây.

Hãy nhớ lại khái niệm Cục bộ không gian (Spatial Locality) của CPU Cache. Khi bạn đọc ô nhớ số 0, CPU sẽ "bốc" luôn một cụm ô nhớ (1, 2, 3...) lên Cache siêu tốc.

Giả sử bạn đang code bằng Golang (sử dụng Row-major), và bạn cần tính tổng toàn bộ ma trận $10000 \times 10000$. Có hai cách duyệt:

Cách 1: Duyệt theo hàng (Đúng chuẩn Row-major)

Go

for i := 0; i < 10000; i++ {        // Lặp hàng trước
    for j := 0; j < 10000; j++ {    // Lặp cột sau
        sum += matrix[i][j]
    }
}

• Hoạt động: Bạn đang đọc dữ liệu (0,0), (0,1), (0,2)... Theo cấu trúc Row-major, các ô nhớ này nằm sát cạnh nhau. CPU liên tục đạt trạng thái Cache Hit. Mã nguồn chạy nhanh như chớp.

Cách 2: Duyệt theo cột (Sai lầm tai hại)

Go

for j := 0; j < 10000; j++ {        // Lặp cột trước
    for i := 0; i < 10000; i++ {    // Lặp hàng sau
        sum += matrix[i][j]
    }
}

• Hoạt động: Bạn đang đọc (0,0), (1,0), (2,0)... Trong RAM, các phần tử này nằm cách xa nhau tới 10,000 ô nhớ! Mỗi lần lặp, CPU tìm trên Cache không thấy, đành lóc cóc xuống RAM để bốc dữ liệu mới lên (Cache Miss). Hiệu năng của vòng lặp này sẽ sụt giảm nghiêm trọng, thường là chậm hơn từ 5 đến 10 lần so với Cách 1 dù Big-O của cả hai đều là $O(n \times m)$.

Việc nắm rõ Mảng đa chiều được ánh xạ vào RAM như thế nào giúp bạn viết ra những đoạn mã thân thiện với CPU (Cache-friendly). Sự kết hợp giữa vòng lặp và cấu trúc dữ liệu không chỉ nằm ở cú pháp, mà nằm ở sự thấu hiểu phần cứng.

Sau khi đã hiểu bản chất vật lý, ở bài học tiếp theo, chúng ta sẽ rèn luyện tư duy không gian toán học (thuật toán) thông qua các bài toán phỏng vấn kinh điển về Mảng 2 chiều.