Sparse Matrix Multiplication - Nhân ma trận thưa hiệu quả

Cho hai ma trận A và B, tính tích A×B. Giả sử số cột A = số hàng B. Tận dụng tính thưa (nhiều phần tử 0) để tối ưu.

Ví dụ: A=[[1,0,0],[-1,0,3]], B=[[7,0,0],[0,0,0],[0,0,1]] → [[7,0,0],[-7,0,3]].

Giải thuật (Chỉ lưu phần tử khác 0)

Chuyển ma trận A thành dạng thưa: mỗi hàng lưu vector (col, value) cho các phần tử ≠ 0. Nhân: với mỗi phần tử (k, val) của hàng i trong A, duyệt cột j của B, nếu B[k][j] != 0 thì ret[i][j] += val * B[k][j].

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
        int r1 = A.size(), r2 = B.size();
        int c1 = A[0].size(), c2 = B[0].size();
        vector<vector<int>> ret(r1, vector<int>(c2, 0));
        vector<vector<pair<int,int>>> sparseA(r1);

        for (int i = 0; i < r1; i++)
            for (int j = 0; j < c1; j++)
                if (A[i][j] != 0)
                    sparseA[i].push_back({j, A[i][j]});

        for (int i = 0; i < r1; i++)
            for (auto& p : sparseA[i])
                for (int k = 0; k < c2; k++)
                    if (B[p.first][k] != 0)
                        ret[i][k] += p.second * B[p.first][k];

        return ret;
    }
};

Đầu vào

{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}

Đầu ra

[[7, 0, 0, ],[-7, 0, 3, ],]