Sparse Matrix Multiplication

Leave a comment

March 13, 2017 by oneOokay

Given two sparse matrices A and B, return the result of AB.

You may assume that A‘s column number is equal to B‘s row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]
B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]
     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

就主要来复习一下矩阵的乘法…高等数学都忘了…

A和B矩阵相乘,只有在A的column数==B的row数的时候才有意义.否则没有意义.并且AB != BA(BA不一定有意义).

当A[rowA][colA] 和 B[rowB][colB]相乘时(colA==rowB),得到的新矩阵AB[rowA][colB]

AB[i][j] = sum(A[i][x] * B[x][j]) 其中x = [0, colA(rowB)]

另一种用向量的表现方法是:A:每一行为一个向量; B:每一列为一个向量.

Screen Shot 2017-03-12 at 11.17.05 PM

一个基本的求和的代码,自己体会……总之我觉得这个还挺妙的.

for(int i = 0; i < rowA; i ++){
    for(int k = 0; k < m; k ++){//m == colA == rowB
        for (int j = 0; j < colB; j ++){
             C[i][j] += A[i][k] * B[k][j];
         }
     }
}

另外一个不想关但是可能会用到的是: Arrays.fill(int[][], value);

那么这题因为是sparse matrixes, 考点在于2个巨大的含有很多0的矩阵相乘的话,如果对每一个元素都做乘法会TLE. 所以我们要减少做乘法的次数.

有三种解法:

  1. 利用HashTable来存Table B:这个用HashMap的方式很有意思
    • HashMap<Integer, HashMap<Integer, Integer>>: HashMap<B的行,HashMap<B的列,B[行][列]>>
    • B[i][j] = map.get(i).get(j);
    • map.keySet()/map.values()
  2. 直接用上面那段只需要在元素不等于零的时候做乘法就可以了
  3. 求出两个sum array: int[A的行数] sumA; int[B的列数] sumB.如果一行/列都为0的话,那么就可以直接skip那一行/列,不用乘了.
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length;
        int colB = B[0].length;
        int m = A[0].length;
        int[][] C = new int[rowA][colB];
        for(int i = 0; i < rowA; i ++){
            for(int k = 0; k < m; k ++){
                if (A[i][k] != 0){
                    for (int j = 0; j < colB; j ++){
                        if (B[k][j] != 0){
                            C[i][j] += A[i][k] * B[k][j];
                        }  }  }  }  }
        return C;
    }

public int[][] multiply(int[][] A, int[][] B) {
 int m = A.length;
 int l = A[0].length;
 int n = B[0].length;
 HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
 for (int i = 0; i < l; i ++){
 map.put(i, new HashMap<Integer, Integer>());
 for (int j = 0; j < n; j ++){
 if (B[i][j] != 0){
 map.get(i).put(j, B[i][j]);
 } } }
 int[][] C = new int[m][n];
 for (int i = 0; i < m; i ++){
 for (int k = 0; k < l; k ++){
 if (A[i][k] != 0){
 for (Integer j : map.get(k).keySet()){
 C[i][j] += A[i][k] * map.get(k).get(j);
 } } } }
 return C;
 }

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: