精华内容
下载资源
问答
  • 稀疏矩阵加法

    2021-04-21 17:36:30
    稀疏矩阵加法代码总结 代码 SparseMatrix operator+(const SparseMatrix& b) { SparseMatrix res(rn,cn,vn+b.vn); SparseMatrix &a = (*this);//这一步保证可以使用a.row等 int i = 1, j = 1; while ...

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

    稀疏矩阵加法

    代码

      SparseMatrix operator+(const SparseMatrix& b)
        {
            SparseMatrix res(rn,cn,vn+b.vn);
            SparseMatrix &a = (*this);//有这行就可以使用a.row等写代码了,可以区分地更加清楚
            int i, j;
            for (i = 1, j = 1, res.vn = 1; i <= a.vn && j <= b.vn; )
            {
                if (a.row[i] < b.row[j])
                {
                    res.row[res.vn] = a.row[i];
                    res.col[res.vn] = a.col[i];
                    res.val[res.vn] = a.val[i];
                    res.vn++;
                    i++;
                }
                else if (a.row[i] > b.row[j])
                {
                    res.row[res.vn] = b.row[j];
                    res.col[res.vn] = b.col[j];
                    res.val[res.vn] = b.val[j];
                    res.vn++;
                    j++;
                }
                else
                {
                    if (a.col[i] < b.col[j])
                    {
                        res.row[res.vn] = a.row[i];
                        res.col[res.vn] = a.col[i];
                        res.val[res.vn] = a.val[i];
                        res.vn++;
                        i++;
                    }
                    else if (a.col[i] > b.col[j])
                    {
                        res.row[res.vn] = b.row[j];
                        res.col[res.vn] = b.col[j];
                        res.val[res.vn] = b.val[j];
                        res.vn++;
                        j++;
                    }
                    else
                    {
                        if (a.val[i] + b.val[j] != 0)
                        {
                            res.row[res.vn] = a.row[i];
                            res.col[res.vn] = a.col[i];
                            res.val[res.vn] = a.val[i] + b.val[j];
                            res.vn++;
                        }
                        i++, j++;//注意这个地方不管是否是0都要遍历下一个元素
                    }
                }
            }
            while (i <= a.vn)
            {
                res.row[res.vn] = a.row[i];
                res.col[res.vn] = a.col[i];
                res.val[res.vn] = a.val[i];
                res.vn++;
                i++;
            }
            while (j <= b.vn)
            {
                res.row[res.vn] = b.row[j];
                res.col[res.vn] = b.col[j];
                res.val[res.vn] = b.val[j];
                res.vn++;
                j++;
            }
            return res;
        }
    };
    

    总结

    其实思路很简单,分类讨论就可以,但是注意给res.vn赋值,否则就是零(当然可以直接赋值为a.vn+b.vn,但是这样逐个加的话不会浪费)

    展开全文
  • 数据结构之稀疏矩阵加法稀疏矩阵加法的算法源程序,
  • MyDS 稀疏矩阵加法

    2020-05-06 18:16:36
    #include<stdio.h> #include<string.h>...//稀疏矩阵加法,行优先,c=a+b,a和b都是nxm矩阵 int cmp(int a,int b,int c,int d){ if(a>c)return 1; if(a==c&&b>d) return 1;...
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    //稀疏矩阵加法,行优先,c=a+b,a和b都是nxm矩阵
    int cmp(int a,int b,int c,int d){
        if(a>c)return 1;
        if(a==c&&b>d) return 1;
        return 0;
    }
    void add(int a[][3],int b[][3],int c[][3]){
        int n=a[0][1],m=a[0][2],pc=0,pb=1;
        for(int i=1;i<=a[0][0];i++){
            while(pb<=b[0][0]&&cmp(a[i][1],a[i][2],b[pb][1],b[pb][2])){
                c[++pc][0]=b[pb][0],c[pc][1]=b[pb][1],c[pc][2]=b[pb][2];
                pb++;
            }
            if(pb<=b[0][0]&&a[i][1]==b[pb][1]&&a[i][2]==b[pb][2]){
                c[++pc][0]=a[i][0]+b[pb][0];
                c[pc][1]=a[i][1],c[pc][2]=a[i][2];
                pb++;
            }
            else {
                c[++pc][0]=a[i][0];
                c[pc][1]=a[i][1],c[pc][2]=a[i][2];
            }
        }
        while(pb<=b[0][0]){
            c[++pc][0]=b[pb][0];
            c[pc][1]=b[pb][1],c[pc][2]=b[pb][2];
            pb++;
        }
        c[0][0]=pc;c[0][1]=n;c[0][2]=m;
    }
    
    int a[10005][3],b[10005][3],c[10005][3];
    int main(){
        int n,m;scanf("%d%d",&n,&m);
        a[0][0]=n,b[0][0]=m;
        a[0][1]=a[0][2]=b[0][1]=b[0][2]=100;
        for(int i=1;i<=n;i++){
            int sa,sb,sc;scanf("%d%d%d",&sa,&sb,&sc);
            a[i][0]=sa,a[i][1]=sb;a[i][2]=sc;
        }
        for(int i=1;i<=m;i++){
            int sa,sb,sc;scanf("%d%d%d",&sa,&sb,&sc);
            b[i][0]=sa,b[i][1]=sb;b[i][2]=sc;
        }
        add(a,b,c);
        printf("%d\n",c[0][0]);
        for(int i=1;i<=c[0][0];i++){
            printf("%d %d %d\n",c[i][0],c[i][1],c[i][2]);
        }
        return 0;
    }
    
    
    展开全文
  • 原始计算过程如下:weight为稀疏矩阵,内存不连续,存储方式为value-index(coo、crs、csc等),稀疏矩阵的存储​www.jianshu.comSPARSE_GROUP_SIZE表示模型进行稀疏训练时,稀疏块的大小,可以设为4/8/16等,从weight...

    原始代码是循环累加和,计算效率较低,运行速度慢,可以考虑使用avx2指令集,实现计算加速。

    原始计算过程如下:weight为稀疏矩阵,内存不连续,存储方式为value-index(coo、crs、csc等),

    稀疏矩阵的存储www.jianshu.com
    061d75e0c79efa4d9be12625957af390.png

    SPARSE_GROUP_SIZE表示模型进行稀疏训练时,稀疏块的大小,可以设为4/8/16等,从weight中每次取SPARSE_GROUP_SIZE大小的数据与该层的输入进行乘法再累加,将累积和作为该层的输出,所有参数都为float32类型。

    int weightPos = 0;
    const float * __restrict x_ptr = x.data();
    float * __restrict y_ptr = y.data();
    for(int i=0; i<nGroups; ++i)
    {
        float sum = 0;
        int col = SPARSE_GROUP_SIZE*colIdx[i];
        //scalar product loop. compiler should optimize it.
        for(int k=0; k<SPARSE_GROUP_SIZE; ++k)
        {
            sum += weight[weightPos++]*x_ptr[col++];
        }
        y_ptr[rowIdx[i]] += sum;
    }

    avx2中,一个寄存器可以处理256bit的数据,即8个float32的数据。

    _mm_cvtss_f32docs.microsoft.com

    _mm256_mul_ps表示对两个float类型的向量进行相乘;

    _mm256_hadd_ps表示水平方向上对两个float类型向量做加法;

    _mm256_extractf128_ps表示从256中取128的数据,即4个f32;

    _mm_add_ss将两个向量相加;

    _mm_cvtss_f32从128的寄存器中取第一个f32的数据;

    //SPARSE_GROUP_SIZE = 8;
    for(int i=0; i<nGroups; ++i)
    {
        float sum2 = 0;
        int col = SPARSE_GROUP_SIZE*colIdx[i];
        
        __m256 res0 = _mm256_mul_ps(*(__m256*)(weight + weightPos),*(__m256*)(x_ptr + col));
    
        res0 = _mm256_hadd_ps(res0, res0);
        res0 = _mm256_hadd_ps(res0, res0);
        __m128 acc1 = _mm256_extractf128_ps(res0, 0);
        __m128 acc2 = _mm256_extractf128_ps(res0, 1);
        acc1 = _mm_add_ss(acc1, acc2);
        sum2 = _mm_cvtss_f32(acc1);
    
        y_ptr[rowIdx[i]] += sum2;
        weightPos += 8;
    }

    当稀疏度达到90%以上,将原始稀疏矩阵推理换成avx2后,模型的整体推理速度有了大幅度的提高。

    Intel 内部指令 --- AVX和AVX2学习笔记blog.csdn.net
    7a23fdce8e46b7bafdbb80514eeba099.png
    展开全文
  • 稀疏矩阵加法(十字链表)问题描述输入输出输入输出样例代码 问题描述 若将稀疏矩阵 \mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中,并用二维数组 BB 表示 AA 中的相应元素是否为零元素(以0和1分别...

    稀疏矩阵加法(十字链表)

    问题描述

    若将稀疏矩阵 \mathbf{A}A 的非零元素以行序为主序的顺序存于一维数组 VV 中,并用二维数组 BB 表示 AA 中的相应元素是否为零元素(以0和1分别表示零元素和非零元素)。例如,
    矩阵A
    可以使用一个数组和一个01矩阵表示在这里插入图片描述

    试写一算法,实现在上述表示法中实现矩阵相加的运算。并分析你的算法时间复杂度(在代码注释中给出)。


    输入

    在这里插入图片描述

    输出

    在这里插入图片描述

    输入输出样例

    输入:

    2 2
    1 1
    1 0
    0 1
    -2 -1
    1 0
    0 1

    输出:

    -1
    1 0
    0 0

    代码

    #include <stdio.h>
    #include <stdlib.h>
    //十字链表的结点
    typedef struct olnode{
        //line
        int i;
        //row
        int j;
        //elemtype
        int e;
        //right
        struct olnode *right;
        //down
        struct olnode *down;
    }ol;
    
    //存储行和列的头
    typedef struct {
        ol *rhead[100];
        ol *chead[100];
        //line
        int mu;
        //row
        int nu;
        //element
        int tu;
    }crosslist;
    
    //申请内存
    ol *lalloc(void){
        return (ol *)malloc(sizeof(ol));
    }
    
    int main(){
        int m,n;
        //读入行数和列数
        scanf("%d %d\n",&m,&n);
    
        //获取输入并返回数组长度
        int getinput(int *p);
        //获取输入的矩阵
        crosslist getarray(crosslist p,int v[]);
        //初始化头链表
        crosslist initialhead(crosslist p);
        //相加
        crosslist addarray(crosslist a,crosslist b);
        void addnode(crosslist p,int ia,int ja,int k,int v[]);
        //打印v数组
        void printv(crosslist a);
        //打印01矩阵
        void printm(crosslist a);
    
        //根据行数和列数
        int va[m*n];
        int vb[m*n];
        int vc[m*n];
    
        //存储行和列的头
        crosslist listheada;
        crosslist listheadb;
        listheada.mu=m;
        listheada.nu=n;
        listheadb.mu=m;
        listheadb.nu=n;
        listheada=initialhead(listheada);
        listheadb=initialhead(listheadb);
        //读入va
        listheada.tu=getinput(va);
        int i,j;
        //读入数组a
        listheada=getarray(listheada,va);
        //读入vb
        listheadb.tu=getinput(vb);
        //读入数组b
        listheadb=getarray(listheadb,vb);
        //相加
        listheada=addarray(listheada,listheadb);
    
        //输出
        printv(listheada);
        printm(listheada);
        
        return 0;
    }
    
    //读入数组va,p为数组名
    int getinput(int *p){
        int c;
        int i=0;
        //符号位
        int sig=1;
    	c=getchar();
        if(c=='\n'){
            c=getchar();
        }
        while(c!='\n'){
            sig=1;
    		//printf("read\n");
            if(c==' '){
                i++;
                c=getchar();
            }
            if(c=='-'){
                sig=-1;
                c=getchar();
            }
            p[i]=c-'0';
            while((c=getchar())!='\n'&&c!=' '){
                p[i]=p[i]*10+c-'0';
            }
            //符号位
            p[i]=p[i]*sig;
        }
        return i+1;
    }
    
    //读入二维数组作为矩阵,p为二维数组名
    crosslist getarray(crosslist p,int v[]){
        int i,j;
        //表示获取的输入的值
        int c;
        //对v数组计数
        int k=0;
        ol *pwork;
        ol *ppoint;
        for(i=0;i<p.mu;i++){
            for(j=0;j<p.nu;j++){
                scanf("%d",&c);
                if(c==1){
                    //addnode(p,i,j,k,v);
                    ppoint=lalloc();
                    ppoint->i=i;
                    ppoint->j=j;
                    ppoint->e=v[k];
                    //此处应初始化为null不然扫描时可能会出错吧
                    ppoint->down=NULL;
                    ppoint->right=NULL;
    
                    //先完成行插入
                    pwork=p.rhead[i];
                    while(pwork->right!=NULL){
                    pwork=pwork->right;
                }
                    pwork->right=ppoint;
    
                    //完成列插入
                    pwork=p.chead[j];
                    while(pwork->down!=NULL){
                    pwork=pwork->down;
                }
                pwork->down=ppoint;
        
                    k++;
                }
            }
        }
        return p;
    }
    
    //在十字链表中增加结点,i,j为行,k为va中的位置
    
    //行和列的头初始化
    crosslist initialhead(crosslist p){
        int i;
        ol *pwork;
        //将行的头结点初始化
        for(i=0;i<p.mu;i++){
            pwork=lalloc();
            pwork->down=NULL;
            pwork->right=NULL;
            p.rhead[i]=pwork;
        }
        //将列的头结点初始化
        for(i=0;i<p.nu;i++){
            pwork=lalloc();
            pwork->down=NULL;
            pwork->right=NULL;
            p.chead[i]=pwork;
        }
        
        return p;
    }
    
    //O(ta+tb),
    //因为输出只要打印所以输出破坏了链表,
    //列并没有连接,只连接了行
    crosslist addarray(crosslist a,crosslist b){
        int i,j;
        ol *pa;
        ol *pb;
        ol *pre;
        //记录pa和pb下一个要处理的结点
        ol *pbnext;
        //ol *panext;
        //逐行扫描
        
        for(i=0;i<a.mu;i++){
            //初始化行
            pa=a.rhead[i]->right;
            pre=a.rhead[i];
            pb=b.rhead[i]->right;
            //扫描pb并将其中行结点插入a中
            while(pb!=NULL){
                pbnext=pb->right;
                if(pa==NULL || pa->j>pb->j){
                    //需要新增结点,pa不需要移动
                    pb->right=pa;
                    pre->right=pb;
                    pre=pb;
                    //处理完当前pb结点,移到下一个
                    pb=pbnext;
                    //多了一个数
                    a.tu++;
                }else if(pa!=NULL && pa->j<pb->j){
                    //pb没有对应结点,不操作,pa需要移动
                    pre=pa;
                    pa=pa->right;
                    //未处理pb结点,不移动
                }else if(pa->j==pb->j){
                    //pa,pb同时有,增加
                    pa->e+=pb->e;
                    //此处pa是否移动都可以吧
                    //不可以!!!
                    //pa=pa->right;
                    //和为0,删除该结点
                    if(pa->e==0){
                        pre->right=pa->right;
                        pa=pa->right;
                        //少了一个数
                        a.tu--;
                    }
                    //pa=pa->right;
                    //处理了pb结点,移动
                    pb=pbnext;
                }
            }
        }
        return a;
    }
    
    //怎么能不输出空格啊
    //有了,记录有多少数
    void printv(crosslist a){
        int i;
        ol *p;
        int count=0;
        if(a.tu==0)
    		printf("\n");
        for(i=0;i<a.mu;i++){
            p=a.rhead[i]->right;
            while(p!=NULL){
                count++;
                if(count<a.tu){
                    printf("%d ",p->e);
                }else if(count==a.tu){
                    printf("%d\n",p->e);
                }else{
                    printf("\n");
                }
                p=p->right;
            }
        }
    }
    
    void printm(crosslist a){
        int i,j;
        ol *p;
    
        for(i=0;i<a.mu;i++){
            p=a.rhead[i]->right;
            for(j=0;j<a.nu-1;j++){
                if(p!=NULL && j<p->j){
                    printf("0 ");
                }else if(p!=NULL && j==p->j){
                    printf("1 ");
                    //打印当前结点,右移
                    p=p->right;
                }else if(p!=NULL && j>p->j){
                    printf("error:j>p->j\n");
                }else if(p==NULL){
                    printf("0 ");
                }
            }
            //打印最后一个结点
            if(p==NULL){
                printf("0\n");
            }else{
                printf("1\n");
            }
            
        }
    }
    

    原本是将addnode单独写为一个函数,但是不知为何一直报错,所以就直接将代码加到getarray中了
    备注写的很详细呀,如果有什么问题欢迎一起讨论~

    展开全文
  • 稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​​1​​,表示接下来要输入的A中的非零元素的个数。...
  • 稀疏矩阵加法(PTA)

    千次阅读 2019-05-29 16:38:43
    稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1,表示接下来要输入的A中的非零元素的个数。 接...
  • /* ... *All rights reserved. *文件名称:xishujuzhen.cpp *作者:朱希康 *完成日期:2015年11月9日 ...*问题描述:稀疏矩阵加法 *输入描述:无 *程序输出:稀疏矩阵的加法 */ #ifndef TUP_H_INCLUDED #define T
  • 7-4 稀疏矩阵加法 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N ​1 ​​ ,表示接下来要输入的A中的非零元素的...
  • 题目:假设稀疏矩阵A和B均以三元组表作为存储结构,试写出矩阵相加和相乘的算法,另设三元组表C存放结果矩阵。 要求: 从键盘输入稀疏矩阵A和B 检测A和B能否相加/相乘 如能,做矩阵相加和相乘运算,并打印运算结果 ...
  • 稀疏矩阵加法,实现C=A+B Description: 输入两个稀疏矩阵,输出它们相加的结果。 Input: 第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的...
  • (c语言)稀疏矩阵加法

    千次阅读 2020-04-17 15:01:38
    实现三元组表示的两个稀疏矩阵加法。相关定义如下 #define MAXSIZE 100 //假设非零元个数的最大值为100 typedef struct { int i,j; //非零元的行下标和列下标,i 和 j 从 1 开始计数,与数学中矩阵元素的...
  • //稀疏矩阵加法 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef struct { int i,j; int e; }Triple; typedef struct { Triple data[MAXSIZE+1]; int mu,nu,tu; }...
  • 稀疏矩阵加法,用十字链表实现C=A+B Input: 第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个矩阵的数据和...
  • [NOJ]数据结构实验2.2 稀疏矩阵加法,实现C=A+B #include<iostream> #include<cstdio> #include<cstdlib> using namespace std; typedef struct { int row,col; int e; }Triple; typedef ...
  • 7-4稀疏矩阵加法(20分) 给定两个矩阵A和B,求其和矩阵C=A+B。 输入格式: 第一行包含两个数Row和Col,分别表示矩阵的行数和列数,A和B的维度是一致的。 第二行只有一个数N​1​​,表示接下来要输入的A中的非零...
  • 7-4 稀疏矩阵加法 (20分) 来都来了点个赞再走呗,一键三连也行,可以点下方链接进入我的bilibili主页转转,也可以关注我的个人公众号~后期公众号会发送一些比较好玩的东西 bilibili:羊卓的杨 公众号:羊卓的杨 ...
  • #include <stdio.h> #include <stdlib.h> typedef struct OLNode { int r,c,v; struct OLNode *right,*down; }Node,*LNode; typedef struct { LNode *Rhead,*Chead;... int mu,n...
  • 稀疏矩阵加法,实现C=A+B

    千次阅读 2018-05-03 22:41:37
    输入两个稀疏矩阵,输出它们相加的结果。第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个矩阵的数据和第二...
  • 稀疏矩阵加法,实现C=A+B

    千次阅读 多人点赞 2018-04-27 20:20:35
    Description输入两个稀疏矩阵,输出它们相加的结果。Input第一行输入四个正整数,分别是两个矩阵的行m、列n、第一个矩阵的非零元素的个数t1和第二个矩阵的非零元素的个数t2。接下来的t1+t2行是三元组,分别是第一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,466
精华内容 1,386
关键字:

稀疏矩阵的加法