C++-এ Sparse Matrix Multiplication: স্পার্স ম্যাট্রিক্স গুণফল বের করা

দুটি ম্যাট্রিক্স A এবং B দেওয়া আছে। A এর কলাম সংখ্যা B এর সারি সংখ্যার সমান। স্পার্স ম্যাট্রিক্স (অধিকাংশ এলিমেন্ট ০) হলে গুণফল দক্ষতার সাথে বের করতে হবে।

উদাহরণ

A = [[1,0,0],[-1,0,3]], B = [[7,0,0],[0,0,0],[0,0,1]]

আউটপুট: [[7,0,0],[-7,0,3]]

সমাধানের পদ্ধতি (Sparse Representation)

1. A এর নন-জিরো এলিমেন্টগুলো প্রতিটি সারিতে সংরক্ষণ করুন: sparseA[i] = vector of {col, value}।
2. রেজাল্ট ম্যাট্রিক্স ret[r1][c2] ইনিশিয়ালাইজ করুন।
3. প্রতিটি সারি i এবং এর নন-জিরো এন্ট্রি {x, val} এর জন্য:
   • B এর x-তম সারির সব কলাম k এর জন্য:
     • যদি B[x][k] != 0 হয়, তবে ret[i][k] += val * B[x][k]।
4. ret রিটার্ন করুন।

এই পদ্ধতিতে শুধু নন-জিরো এলিমেন্টগুলোর ওপর লুপ চলে, যা স্পার্স ম্যাট্রিক্সের জন্য খুব দক্ষ।

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();
        int r2 = B.size();
        int c1 = A[0].size();
        int c2 = B[0].size();
        vector<vector<int>> ret(r1, vector<int>(c2));
        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(int j = 0; j < sparseA[i].size(); j++) {
                for(int k = 0; k < c2; k++) {
                    int x = sparseA[i][j].first;
                    if(B[x][k] != 0) {
                        ret[i][k] += sparseA[i][j].second * B[x][k];
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> A = {{1,0,0},{-1,0,3}};
    vector<vector<int>> B = {{7,0,0},{0,0,0},{0,0,1}};
    vector<vector<int>> res = ob.multiply(A, B);
    // Print result
    for(auto &row : res) {
        for(int val : row) cout << val << " ";
        cout << endl;
    }
    return 0;
}

ইনপুট

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

আউটপুট

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