Cộng và trừ ma trận
Sau bài này bạn sẽ làm được
- Cài phép cộng và trừ ma trận
- Kiểm tra điều kiện kích thước trước khi tính
- Viết hàm nhận ma trận với số cột cố định
- Nhận ra vì sao thứ tự duyệt ảnh hưởng tốc độ
Cộng và trừ ma trận là phép toán đơn giản nhất trong đại số tuyến tính: cộng từng cặp phần tử tương ứng. Đơn giản tới mức bài này dành phần lớn thời gian cho những chuyện xung quanh nó, những chuyện quyết định mã của bạn dùng lại được hay không.
#Phép toán theo từng phần tử
C[i][j] = A[i][j] + B[i][j] /* cộng */
C[i][j] = A[i][j] - B[i][j] /* trừ */enum { COT = 4 };
void cong_ma_tran(const int a[][COT], const int b[][COT],
int kq[][COT], size_t hang)
{
for (size_t i = 0; i < hang; ++i)
for (size_t j = 0; j < COT; ++j)
kq[i][j] = a[i][j] + b[i][j];
}
void tru_ma_tran(const int a[][COT], const int b[][COT],
int kq[][COT], size_t hang)
{
for (size_t i = 0; i < hang; ++i)
for (size_t j = 0; j < COT; ++j)
kq[i][j] = a[i][j] - b[i][j];
}A:
1 2 3 4
5 6 7 8
B:
10 20 30 40
50 60 70 80
A + B:
11 22 33 44
55 66 77 88#Điều kiện kích thước
Phép cộng chỉ định nghĩa được khi hai ma trận cùng kích thước. Trong C, một phần điều kiện đó được trình biên dịch kiểm tra hộ và một phần thì không.
| Điều kiện | Ai kiểm tra | Nếu sai thì sao |
|---|---|---|
| Cùng số cột | Trình biên dịch | Lỗi biên dịch, vì số cột nằm trong kiểu |
| Cùng số hàng | Bạn | Không ai báo gì, chương trình đọc ghi ngoài biên |
| Ma trận kết quả đủ chỗ | Bạn | Ghi tràn bộ nhớ |
int a[3][4], b[3][4], c[3][4];
int d[3][5];
cong_ma_tran(a, b, c, 3); /* đúng */
cong_ma_tran(a, d, c, 3); /* lỗi biên dịch: số cột khác nhau */
cong_ma_tran(a, b, c, 10); /* biên dịch sạch, chạy tràn bộ nhớ */Phiên bản linh hoạt với ma trận phẳng
/* Trả về 0 nếu ổn, âm một nếu tham số vô lý. */
int cong_ma_tran(const int *a, const int *b, int *kq,
size_t hang, size_t cot)
{
if (a == NULL || b == NULL || kq == NULL) return -1;
if (hang == 0 || cot == 0) return -1;
for (size_t i = 0; i < hang; ++i)
for (size_t j = 0; j < cot; ++j) {
size_t k = i * cot + j;
kq[k] = a[k] + b[k];
}
return 0;
}#Gộp thành một vòng lặp
Vì phép cộng xử lý từng phần tử độc lập và ma trận nằm phẳng liên tục trong bộ nhớ, hai vòng lặp lồng nhau có thể gộp thành một.
/* Hai vòng lặp */
for (size_t i = 0; i < hang; ++i)
for (size_t j = 0; j < cot; ++j)
kq[i * cot + j] = a[i * cot + j] + b[i * cot + j];
/* Một vòng lặp, cho ra kết quả giống hệt */
size_t n = hang * cot;
for (size_t k = 0; k < n; ++k)
kq[k] = a[k] + b[k];| Hai vòng lặp | Một vòng lặp | |
|---|---|---|
| Số dòng | 3 | 3 |
| Phép nhân mỗi lượt | Có, i * cot | Không |
| Trình biên dịch tối ưu song song được | Khó hơn | Dễ hơn |
| Dùng được khi kích thước dùng khác kích thước khai báo | Có, nếu viết m[i][j] | Không, vì có ô đệm ở cuối mỗi hàng |
#Nhân với một số
void nhan_so(const int *a, int he_so, int *kq, size_t n)
{
for (size_t k = 0; k < n; ++k)
kq[k] = a[k] * he_so;
}Phép này cũng theo từng phần tử nên hoàn toàn tương tự. Nhưng nó mang theo một rủi ro mà phép cộng ít gặp hơn: tràn số. Nhân một ma trận số lớn với hệ số lớn rất dễ vượt giới hạn int.
int kq[3][4];
nhan_so(&a[0][0], 100000, &kq[0][0], 12);
/* Nếu a chứa số cỡ 100000, tích là 10 tỷ, vượt giới hạn int. */long long kq[3][4];
void nhan_so(const int *a, int he_so, long long *kq, size_t n)
{
for (size_t k = 0; k < n; ++k)
kq[k] = (long long)a[k] * he_so; /* ép TRƯỚC khi nhân */
}#Một hàm cho mọi phép toán
Cộng, trừ, nhân từng phần tử, lấy giá trị lớn hơn: cả bốn đều là cùng một vòng lặp với một phép toán khác nhau. Con trỏ hàm cho phép viết chúng thành một hàm duy nhất.
/* Hàm nhận một con trỏ hàm hai ngôi và áp dụng nó lên từng cặp phần tử. */
void ap_dung(const int *a, const int *b, int *kq, size_t n,
int (*phep)(int, int))
{
for (size_t k = 0; k < n; ++k)
kq[k] = phep(a[k], b[k]);
}
static int cong(int x, int y) { return x + y; }
static int tru(int x, int y) { return x - y; }
static int nhan(int x, int y) { return x * y; }
static int lon_hon(int x, int y) { return x > y ? x : y; }
ap_dung(&a[0][0], &b[0][0], &kq[0][0], 12, cong);
ap_dung(&a[0][0], &b[0][0], &kq[0][0], 12, lon_hon);Bài toán mở rộng: cộng ma trận thưa
Khi ma trận chủ yếu là số 0, lưu đủ mọi ô là lãng phí. Một ma trận 10000 nhân 10000 chiếm bốn trăm megabyte dù chỉ có vài nghìn ô khác 0. Cách lưu thay thế là chỉ giữ danh sách các bộ ba hàng, cột, giá trị.
typedef struct {
size_t hang, cot;
int gia_tri;
} O;
/* Ma trận thưa là một mảng O đã sắp theo hàng rồi theo cột.
Phép cộng khi đó là phép trộn hai danh sách đã sắp, giống bước trộn
của sắp xếp trộn ở Chương 27. */
size_t cong_thua(const O *a, size_t na, const O *b, size_t nb,
O *kq, size_t co);Cấu trúc này bạn sẽ gặp lại ở Chương 25 khi học bảng băm. Ở đây chỉ cần ghi nhận rằng cách biểu diễn dữ liệu quyết định thuật toán, chứ không phải ngược lại.
Tự làm thử
- Viết chương trình nhập hai ma trận cùng kích thước, in ra tổng và hiệu của chúng.
- Gọi hàm cộng với số hàng lớn hơn kích thước thật, chạy dưới
-fsanitize=addressvà đọc thông báo. - Viết cả hai phiên bản hai vòng lặp và một vòng lặp, xác nhận kết quả giống nhau, rồi đo thời gian trên ma trận lớn.
- Nhân ma trận với hệ số lớn để gây tràn số, sau đó sửa bằng cách đổi kiểu kết quả và ép kiểu đúng chỗ.
- Cài hàm
ap_dungnhận con trỏ hàm, dùng nó cho bốn phép toán khác nhau, rồi đo xem nó chậm hơn hàm chuyên dụng bao nhiêu. - Viết hàm kiểm tra hai ma trận có bằng nhau không, trả về vị trí đầu tiên khác nhau nếu có.
Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.
Tóm tắt
- Cộng và trừ ma trận là phép toán theo từng phần tử, chỉ định nghĩa được khi hai ma trận cùng kích thước.
- Trình biên dịch kiểm tra được số cột vì nó nằm trong kiểu, nhưng số hàng là tham số nên bạn phải tự kiểm tra.
- Hai vòng lặp gộp được thành một khi vùng dữ liệu liên tục thật sự, tức khi kích thước khai báo bằng kích thước đang dùng.
- Khi nhân với hệ số, ép kiểu phải đặt lên toán hạng trước khi nhân, không đặt lên kết quả.
- Con trỏ hàm cho phép một vòng lặp phục vụ mọi phép toán, đổi lại mất khả năng nhúng và véc tơ hóa.