稀疏矩阵乘法 - 微软题

题目 ： 实现三元组表示的稀疏矩阵乘法
思路 ： 基础方法，将两个稀疏矩阵分别存储到两个哈希表中，若两个矩阵的size分别为(m, n)(n, r)，进行m->r->n三重循环，若该点在哈希表中，则进行累加，若累加结果不为0,则将其加入返回结果中。
代码 ：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <unordered_map>
   
4. 
   
5. using namespace std;
   
6. 
   
7. struct Point {
   
8.   int first_point;
   
9.   int second_point;
   
10.   Point (int x, int y) : first_point(x), second_point(y) {}
    
11. };
    
12. 
    
13. struct HashFunc {
    
14.   size_t operator()(const Point& p) const {
    
15.     return ((hash<int>()(p.first_point) ^ (hash<int>()(p.second_point) << 1)) >> 1);
    
16.   }
    
17. };
    
18. 
    
19. struct EqualPoint {
    
20.   bool operator ()(const Point& p1, const Point& p2) const {
    
21.     return p1.first_point == p2.first_point && p1.second_point == p2.second_point;
    
22.   }
    
23. };
    
24. 
    
25. class SparseMatrixOperator {
    
26. public:
    
27.   vector<vector<int>> SparseMatrixMultiply(vector<vector<int>>& matrix1, vector<vector<int>>& matrix2, int m, int n, int r) {
    
28.     vector<vector<int>> matrix_multiply;
    
29.     unordered_map<Point, int, HashFunc, EqualPoint> matrix_store1;
    
30.     for (vector<int> iter : matrix1) {
    
31.       Point p(iter[0], iter[1]);
    
32.       matrix_store1[p] = iter[2];
    
33.     }
    
34.     unordered_map<Point, int, HashFunc, EqualPoint> matrix_store2;
    
35.     for (vector<int> iter : matrix2) {
    
36.       Point p(iter[0], iter[1]);
    
37.       matrix_store2[p] = iter[2];
    
38.     }
    
39.     for (int i = 0; i < m; i++) {
    
40.       for (int j = 0; j < r; j++) {
    
41.         int element_multiply = 0;
    
42.         for (int k = 0; k < n; k++) {
    
43.           Point p1(i, k);
    
44.           Point p2(k, j);
    
45.           if (matrix_store1.find(p1) != matrix_store1.end() && matrix_store2.find(p2) != matrix_store2.end()) {
    
46.             element_multiply += matrix_store1[p1] * matrix_store2[p2];
    
47.           }
    
48.         }
    
49.         if (element_multiply != 0) {
    
50.           matrix_multiply.push_back({i, j, element_multiply});
    
51.         }
    
52.       }
    
53.     }
    
54.     return matrix_multiply;
    
55.   }
    
56. 
    
57.   void print(vector<vector<int>>& matrix, int m, int n) {
    
58.     unordered_map<Point, int, HashFunc, EqualPoint> element_store;
    
59.     for (vector<int> iter : matrix) {
    
60.       Point p(iter[0], iter[1]);
    
61.       element_store[p] = iter[2];
    
62.     }
    
63.     for (int i = 0; i < m; i++) {
    
64.       for (int j = 0; j < n; j++) {
    
65.         Point p(i, j);
    
66.         if (element_store.find(p) != element_store.end()) {
    
67.           cout << element_store[p] << " ";
    
68.         } else {
    
69.           cout << "0" << " ";
    
70.         }
    
71.       }
    
72.       cout << endl;
    
73.     }
    
74.   }
    
75. };
    
76. 
    
77. int main() {
    
78.   // matrix1
    
79.   // 1 0
    
80.   // 0 2
    
81.   // 0 0
    
82.   vector<vector<int>> matrix1 = {{0, 0, 1}, {1, 1, 2}};
    
83.   // matrix2
    
84.   // 3 0 0 4
    
85.   // 0 0 5 0
    
86.   vector<vector<int>> matrix2 = {{0, 0, 3}, {0, 3, 4}, {1, 2, 5}};
    
87.   SparseMatrixOperator sparse_matrix_operator;
    
88.   vector<vector<int>> matrix_multiply =  sparse_matrix_operator.SparseMatrixMultiply(matrix1, matrix2, 3, 2, 4);
    
89.   cout << "matrix1:" << endl;
    
90.   sparse_matrix_operator.print(matrix1, 3, 2);
    
91.   cout << "matrix2:" << endl;
    
92.   sparse_matrix_operator.print(matrix2, 2, 4);
    
93.   cout << "matrix_multiply:" << endl;
    
94.   sparse_matrix_operator.print(matrix_multiply, 3, 4);
    
95.   return 0;
    
96. }
    

复制代码