SparseMatrixMulutiplication [source code]


public class SparseMatrixMulutiplication {
static
/******************************************************************************/
public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int h = A.length, n = A[0].length, w = B[0].length;
        int[][] res = new int[h][w];
        List<int[]> listA = new ArrayList<>(), listB = new ArrayList<>();
        for (int i = 0; i < h; i++)
            for (int j = 0; j < n; j++)
                if (A[i][j] != 0) 
                    listA.add(new int[]{i, j, A[i][j]});
        for (int i = 0; i < n; i++)
            for (int j = 0; j < w; j++)
                if (B[i][j] != 0)
                    listB.add(new int[]{i, j, B[i][j]});
        for (int[] pointA : listA)
            for (int[] pointB : listB)
                if (pointA[1] == pointB[0]) {
                    int x = pointA[0];
                    int y = pointB[1];
                    int val = pointA[2] * pointB[2];
                    res[x][y] += val;
                }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SparseMatrixMulutiplication.Solution tester = new SparseMatrixMulutiplication.Solution();
    }
}

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

真正自己面试的时候就要留意一下这个坑, 这种很基本的东西不要真正到了面试的时候也忘记了;

这个题目严格来说不能说是一点思路都没有, 所谓sparse, 那么直接想到的方法就是做一个记录: 用overriding的逻辑来记录所有的entry(数据);

下面就是你记录下来的这个东西, 怎么反映到乘积里面去;

感觉这个题目也不是想的那么简单: 首先这里想要做的其实是针对sparse的一个优化, 那么你先想想, 最普通的笨办法的速度是什么? 如果是m x n and n x t, 那么最后的复杂度是mnt.

具体做法是针对最后的结果的每个entry进行iterate;
每个entry计算的时候回过头来计算两个operand的相应行和列的乘积;

那么你优化能优化到什么程度呢?

好像有点思路, 这个算法你光是盯着sparse来想, 是未必想的出来的; 要继续想到sparse的定义是什么? 其他的地方全都是0, 然后我们做得又是乘积. 我们已经知道用overriding的思路来写, 那么也就是有一个default的情况在里面; 两个数相乘, 我们可以认为default就是0, 除非两个数都不是0. 有了这个思路感觉可以写了; 不对, 这个思路其实还不完整, 不过感觉整个算法大概有想法了;

最后写出来的算法其实也挺没劲的; 这个问题的优化, 感觉就是一个信息压缩的过程, 本来一个sparse的matrix, 那么很大的一个问题就是信噪比很低; 我们用一个list把所有的有用的信息记录下来(或者用Map, 都一样的); 这样就得到了两个很小的list, 然后这两个小list之间再来一个穷搜的iterate就行了; 最后的速度是mn + nt + listA.length * listB.length;

最后的速度实际上只有127ms (27%), 估计我这个算法还是有问题;

这个是discussion上的最优解: 48(98)

public class Solution {  
    public int[][] multiply(int[][] A, int[][] B) {  
        int m = A.length, n = A[0].length, nB = B[0].length;  
        int[][] C = new int[m][nB];  

        for(int i = 0; i < m; i++) {  
            for(int k = 0; k < n; k++) {  
                if (A[i][k] != 0) {  
                    for (int j = 0; j < nB; j++) {  
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];  
                    }  
                }  
            }  
        }  
        return C;     
    }  
}

这个其实我是想到了的, 上面的分析的时候也写到了, 只有当两个operand都不是0的时候, 才有相乘的意义; 为了达到这样一个筛选, 只要iterate A一个就行了; 这样可以省略掉很多对B的array access; 不过我后来认为这个算法其实对于实际的加速几乎没有作用; 因为最后你A的每一个entry你其实都access了. 这个算法的复杂度看代码可以看出来, 是mn + Number_Of_Non_Zero_A_entry * nB, 好像其实很快? 好像实际上是比我的算法要快一些的, 因为我压缩B用的时间肯定比他这里的第二项要大;

哎, 有点可惜, 本来都想到了这个点子, 不过没有仔细的分析下去; 严格来说这个算法在我脑子里其实都已经写出来了; 还是分析的不够彻底不够concrete, 对这个的复杂度当时也是毛估估了一下就放弃了; write it down!!!

另外这个解好像是有说法的: http://www.cs.cmu.edu/~scandal/cacm/node9.html

A sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row.

这个其实就是我的做法, 一个对sparse进行压缩的思路;

上面那个代码是作者被别人提醒之后想到的一个改进版本, 下面这个是他自己原来的版本: 101(31)

public int[][] multiply(int[][] A, int[][] B) {  
    int m = A.length, n = A[0].length, nB = B[0].length;  
    int[][] result = new int[m][nB];  

    List[] indexA = new List[m];  
    for(int i = 0; i < m; i++) {  
        List<Integer> numsA = new ArrayList<>();  
        for(int j = 0; j < n; j++) {  
            if(A[i][j] != 0){  
                numsA.add(j);   
                numsA.add(A[i][j]);  
            }  
        }  
        indexA[i] = numsA;  
    }  

    for(int i = 0; i < m; i++) {  
        List<Integer> numsA = indexA[i];  
        for(int p = 0; p < numsA.size() - 1; p += 2) {  
            int colA = numsA.get(p);  
            int valA = numsA.get(p + 1);  
            for(int j = 0; j < nB; j ++) {  
                int valB = B[colA][j];  
                result[i][j] += valA * valB;  
            }  
        }  
    }  

    return result;     
}

这个算法的复杂度感觉其实跟上面那个算法是一样的, 不过最后速度差很多, 估计还是数据结构的overhead太严重;

另外他这里对A的压缩办法其实有点类似page rank的处理办法: matrix第一维不压缩, 但是第二维压缩; 我当时其实有想到这个例子, 因为page rank是一个经典的sparse压缩问题了;

最后的结果其实是差不多的; 如果我的做法, 我没有对B也单独进行一个压缩的话, 而是直接在B里面就进行处理, 感觉速度可能能够赶上他这个算法;

Thanks for providing this nice solution, @yavinci. I have a question about it. It seems like the CMU lecture solution is for sparse matrix multiplies dense vector. And I guess "another non-zero array on B" could be useful. The reason is that, for an element [k, j] in B, it would be detected for non-zero elements several times on the fly, depending on how many i's make elements [i, k] non-zero in A. However, your solution is faster than my Java solution with two HashMaps. I guess the reason could be the efficiency of primitive types in your solution.

看到, discussion上面有一个人是跟我一样的做法, 不过最后速度差很多, 也是不理解; 不过其实这个看法还是不够成熟的, 单独压缩B的cost几乎一定会超过因为这个repeated visit造成的损失, 因为n nB几乎可以确定比 A当中非零个数 nB;

Moreover, I guess the set of test cases is not good enough right now. Your solution inspired me to detecting both on the fly: storing non-zero elements in A in a List of Lists and then detecting B and do multiplication is kind of like detecting both on the fly.

上面那个48的代码的作者这样说:

Given A and B are sparse matrices, we could use lookup tables to speed up. At the beginining I thought two lookup tables would be necessary. After discussing with @yavinci, I think one lookup table for B would be enough. Surprisingly, it seems like detecting non-zero elements for both A and B on the fly without additional data structures provided the fastest performance on current test set.

However, I think such fastest performance could due to an imperfect test set we have for OJ right now: there are only 12 test cases. And, for an element B[k, j], it would be detected for non-zero elements several times if we detecting both A and B on the fly, depending on how many i's make elements A[i, k] non-zero. With this point, the additional data structures, like lookup tables, should save our time by focusing on only non-zero elements. If it is not, I am worried the set of OJ test cases probably is not good enough.

Anyway, I am posting my respective solutions below. Comments are welcome. Thanks @yavinci again for discussing with me.

所以他也认为其实AB都压缩的办法未必是一个很差的办法; 所以我感觉我这个题目的精华应该还是get到了;

discussion里面其实也没有更好的解法了, 有一个人po了一篇又臭又长的分析, 懒得看了: https://discuss.leetcode.com/topic/72871/54ms-detailed-summary-of-easiest-java-solutions-beating-99-9/5

Problem Description

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 |

When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Operations using standard dense-matrix structures and algorithms are slow and inefficient when applied to large sparse matrices as processing and memory are wasted on the zeroes. Sparse data is by nature more easily compressed and thus require significantly less storage. Some very large sparse matrices are infeasible to manipulate using standard dense-matrix algorithms.

Difficulty:Medium
Total Accepted:29.2K
Total Submissions:57.6K
Contributor: LeetCode
Companies
linkedin facebook
Related Topics
hash table

LC311 SparseMatrixMulutiplication

SparseMatrixMulutiplication [source code]

Problem Description

results matching ""

No results matching ""