文档章节

稀疏矩阵乘法

o
 osc_n6euf5h6
发布于 2019/03/19 22:35
字数 1212
阅读 6
收藏 0

精选30+云产品,助力企业轻松上云!>>>

给定两个 稀疏矩阵 A 和 B,返回AB的结果。
您可以假设A的列数等于B的行数。

题目地址:https://www.jiuzhang.com/solution/sparse-matrix-multiplication/#tag-other

本参考程序来自九章算法,由 @Roger 提供。

题目解法:

时间复杂度分析:
假设矩阵A,B均为 n x n 的矩阵,
矩阵A的稀疏系数为a,矩阵B的稀疏系数为b,
a,b∈[0, 1],矩阵越稀疏,系数越小。

方法一:暴力,不考虑稀疏性
Time (n^2 * (1 + n)) = O(n^2 + n^3)
Space O(1)

方法二:改进,仅考虑A的稀疏性
Time O(n^2 * (1 + a * n) = O(n^2 + a * n^3)
Space O(1)

方法三(最优):进一步改进,考虑A与B的稀疏性
Time O(n^2 * (1 + a * b * n)) = O(n^2 + a * b * n^3)
Space O(b * n^2)

方法四:另外一种思路,将矩阵A, B非0元素的坐标抽出,对非0元素进行运算和结果累加
Time O(2 * n^2 + a * b * n^4) = O(n^2 + a * b * n^4)
Space O(a * n^2 + b * n^2)

解读:矩阵乘法的两种形式,假设 A(n, t) * B(t, m) = C(n, m)

// 形式一:外层两个循环遍历C (常规解法)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        for (int k = 0; k < t; k++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

// 或者写成下面这样子
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        int sum = 0;
        for (int k = 0; k < t; k++) {
            sum += A[i][k] * B[k][j];
        }
        C[i][j] = sum;
    }
}
// 形式二:外层两个循环遍历A
for (int i = 0; i < n; i++) {
    for (int k = 0; k < t; k++) {
        for (int j = 0; j < m; j++) {
            C[i][j] += A[i][k] * B[k][j];
        }
    }
}

两种方法的区别

代码上的区别(表象):
调换了第二三层循环的顺序

核心区别(内在):
形式一以C为核心进行遍历,每个C[i][j]只会被计算一次,就是最终答案。
形式二以A为核心进行遍历,每个A[i][k] 乘上 B[k][j]之后,会被累加到 C[i][j],每个C[i][j]将被累加t次。

 

举个例子,若A矩阵2x3,B矩阵3x2,C矩阵2x2
       A                 B              C
a00 , a01 , a02      b00 , b01      c00 , c01
a10 , a11 , a12      b10 , b11      c10 , c11
                            b20 , b21

形式一的计算过程:遍历C,假设遍历到c00,计算c00 = a00 * b00 + a01 * b10 + a02 * b20
形式二的计算过程:遍历A,
假设遍历到a00,a00 * b00 累加到 c00, a00 * b01 累加到c01;
假设遍历到a01,a01 * b10 累加到 c00, a01 * b11 累加到c01;

 

 再回到本题目,可以发现是否为稀疏矩阵,对于上述形式一来说,并无法进行优化,因为是以C为核心
但是对于形式二来说,以A为核心,若A[i][k]为0,那么该元素就不必进行对应相乘并累加的操作了。
故方法二,就是基于此进行优化的。

// 方法一
public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        // write your code here
        // A(n, t) * B(t, m) = C(n, m)
        int n = A.length;
        int t = A[0].length;
        int m = B[0].length;
        int[][] C = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int sum = 0;
                for (int k = 0; k < t; k++) {
                    sum += A[i][k] * B[k][j];
                }
                C[i][j] = sum;
            }
        }
        
        return C;
    }
}

// 方法二
public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        // write your code here
        // A(n, t) * B(t, m) = C(n, m)
        int n = A.length;
        int t = A[0].length;
        int m = B[0].length;
        int[][] C = new int[n][m];
        
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < t; k++) {
                if (A[i][k] == 0) {
                    continue;
                }
                for (int j = 0; j < m; j++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }
        
        return C;
    }
}

// 方法三
public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        // write your code here
        // A(n, t) * B(t, m) = C(n, m)
        int n = A.length;
        int t = A[0].length;
        int m = B[0].length;
        int[][] C = new int[n][m];
        
        List<List<Integer>> B_nonZero_colIndices = new ArrayList<>();
        for (int k = 0; k < t; k++) {
            List<Integer> colIndices = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                if (B[k][j] != 0) {
                    colIndices.add(j);
                } 
            }
            B_nonZero_colIndices.add(colIndices);
        }
        
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < t; k++) {
                if (A[i][k] == 0) {
                    continue;
                }
                for (int colIndex : B_nonZero_colIndices.get(k)) {
                    C[i][colIndex] += A[i][k] * B[k][colIndex];
                }
            }
        }
        
        return C;
    }
}

// 方法四
public class Solution {
    /**
     * @param A: a sparse matrix
     * @param B: a sparse matrix
     * @return: the result of A * B
     */
    public int[][] multiply(int[][] A, int[][] B) {
        // write your code here
        // A(n, t) * B(t, m) = C(n, m)
        int n = A.length;
        int t = A[0].length;
        int m = B[0].length;
        int[][] C = new int[n][m];
        
        List<Point> A_Points = getNonZeroPoints(A);
        List<Point> B_Points = getNonZeroPoints(B);
        
        for (Point pA : A_Points) {
            for (Point pB : B_Points) {
                if (pA.j == pB.i) {
                    C[pA.i][pB.j] += A[pA.i][pA.j] * B[pB.i][pB.j];
                }
            }
        }
    
        return C;
    }
    
    
    private List<Point> getNonZeroPoints(int[][] matrix) {
        List<Point> nonZeroPoints = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] != 0) {
                    nonZeroPoints.add(new Point(i, j));
                }
            }
        }
        return nonZeroPoints;
    }
    
    class Point {
        int i, j;
        Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Tensorflow——tf.matmul() 和tf.multiply() 的区别

1.tf.multiply()两个矩阵中对应元素各自相乘 格式: tf.multiply(x, y, name=None) 参数: x: 一个类型为:half, float32, float64, uint8, int8, uint16, int16, int32, int64, complex64, c......

SpareNoEfforts
2018/10/30
0
0
MapReduce 矩阵乘法之我见

一、最简单的算法 把mn 和nl的矩阵A和B相乘,这估计是最容易想到的方法了: 把A(mn)的元素,每个发送l次,把B(nl)的元素每个发送m次。将发送到一起的数据相乘求和,得到最后的结果。 优点...

一只小桃子
2014/05/18
2.2K
5
稀疏矩阵的加减乘除算法

参考数据结构严蔚敏稀疏矩阵乘法 1 #include<iostream> 2 #include<vector> 3 #include<unistd.h> 4 #include<fstream> 5 6 using namespace std; 7 class Tuple{ 8 public: 9 int row,col,v......

osc_38q1uccr
2018/03/29
1
0
tf.matmul() 和tf.multiply() 的区别

1.tf.multiply()两个矩阵中对应元素各自相乘 格式: tf.multiply(x, y, name=None) 参数: x: 一个类型为:half, float32, float64, uint8, int8, uint16, int16, int32, int64, complex64, c......

osc_i06got93
2018/05/03
3
0
行逻辑链接的矩阵乘法

Description 对于一个稀疏矩阵,当需要频繁的随机存取任意一行的非零元时,则需要知道每一行的第一个非零元在三元组表中的位置。为此,可以将算法5.2中用来指示“行”信息的辅助数组cpot固定...

osc_j6x7mc4h
2019/10/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何删除使用Python的easy_install安装的软件包? - How do I remove packages installed with Python's easy_install?

问题: Python's easy_install makes installing new packages extremely convenient. Python的easy_install使安装新包非常方便。 However, as far as I can tell, it doesn't implement th......

fyin1314
20分钟前
0
0
如何将逗号分隔的字符串转换为数组? - How to convert a comma separated string to an array?

问题: I have a comma separated string that I want to convert into an array, so I can loop through it. 我有一个逗号分隔的字符串,我想将其转换成数组,因此可以循环遍历它。 Is the...

富含淀粉
50分钟前
13
0
深源恒际:担心个人身份被冒用?不存在!

本文作者:c****t 近日,苟晶被冒名顶替身份参加高考的事件在社会各界掀起广泛热议。事件调查结果公布后,舆论风向逆转,吃瓜群众认为当事人夸大其词消费了公众情绪,一边对当事人所遭遇的不...

百度开发者中心
昨天
5
0
CKEditor 5 + SpringBoot实战(三):SpringData JPA数据持久化

在本系列的文章中,我将介绍如何在Spring Boot Application中使用CKEditor编辑器。介绍的内容包括基本环境的搭建,文件上传,SpringData JPA数据持久化,CKEditor5的安装,CKEditor图片上传,...

树下魅狐
今天
9
0
Confluence 如何查看页面 ID

如果你希望查看页面的 ID 你有 2 个方法。 例如,你希望查看 https://www.cwiki.us/display/CONFLUENCEWIKI/Get+started 页面的 Page ID 的话。 如果你的标题栏没有特殊字符,那么将会使用英...

honeymoose
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部