精华内容
下载资源
问答
  • 稀疏矩阵的乘法
    2021-04-20 19:00:52

    title: 稀疏矩阵乘法
    date: 2020-11-09 19:31:44
    tags: 稀疏矩阵运算
    categories: 数据结构


    在本算法中,两个稀疏矩阵的特性都有用到

    规定

    规定以下变量名称,本文讲述 矩阵A × 矩阵B = 矩阵C 的运算过程

    需要用到的存储结构有:

    1. 矩阵A,矩阵 B 的原始二维数组(2个)
    2. 矩阵A,矩阵B 的三元组数组(2个)
    3. 存储 矩阵A,矩阵B 每行有多少个非零元的数组(2个,分别存A、B矩阵)
    4. 存储 矩阵B每行首个非零元在三元组数组中的位置的数组(1个)
    5. 需要开一个中间数组用于存矩阵C的每一行 (这个中间数组的长度等于B的列数,它只负责在一次循环中记录矩阵C的原始的一行,注意不是稀疏矩阵表示的一样,而是原始矩阵C的一行)
    6. 矩阵C 的三元组数组,将稀疏矩阵还原以后的 C的二维数组

    综上,本算法需要 5 种,9 个数组

    思路

    首先,将上述1 - 4 中的 7 个数组均求出来

    一切准备妥当后,且听我慢慢道来

    遍历A的三元组数组, 将位于同一行的每个非零元分别与 该非零元的列数 对应到B中的行数,对B中行数是 非零元列数的每个非零元依次求乘法运算并存到中间数组的对应下标位置处,当遍历完A的一行的所有非零元之后,也就求出了C的一行(存在中间数组中,这个中间数组存的不是稀疏的,而是原始矩阵C的一行),然后再对C进行压缩处理,因为在这个过程中,可能原来不是非零元,在计算完之后成了非零元,压缩完之后存到C的三元组数组中

    代码

    此代码仅仅是将每次内层for循环得到的temp数组(即C矩阵的每一行)打印了出来,还没有做对C矩阵的录入工作,和前面所说稍有出入,还缺个尾巴,但核心算法问题已经解决。

    #include <stdio.h>
    #include <stdlib.h>
    /*
        矩阵 a    4 × 7   8个非零元
        0 8 0 0 6 0 0 
        0 1 0 3 0 0 0 
        7 0 0 2 0 4 0 
        0 0 8 0 0 0 5
    
        矩阵 b    7 × 3   6个非零元
        1  0  0
        0  0  2
        0  0  0
        0  9  0 
        3  0  0
        0  0  6
        0  4  0
    */
    
    // 定义非零元的结构体(三元组的基本结构)
    typedef struct member
    {
        // 矩阵中非零元的 行,列,值
        int row, col, x;
        
    } Member;
    
    // 定义稀疏矩阵
    typedef struct matrix
    {
        // 三元组数组
        Member *arr;
        // 矩阵的行数、列数、非零元个数
        int rows, cols, counts;
        
    } Matrix;
    
    // 初始化矩阵A的三元组数组
    void InitMatrixA(Matrix *);
    // 初始化矩阵B的三元组数组
    void InitMatrixB(Matrix *);
    // 初始化一个三元组数组(在本算法中用于初始化矩阵C的压缩矩阵表示)
    void InitMatrix(Matrix *);
    // 以原始形式打印矩阵
    void PrintMatrix(Matrix);
    
    // 求存储了矩阵每一行的第一个非零元在三元组数组中的下标是多少的数组
    int *getIndexArr(Matrix);
    int *getCountArr(Matrix);
    // 求每一行有多少个非零元
    int *getNotZeroSuchRow(Matrix);
    // 矩阵乘法
    void Multiply(Matrix, Matrix, int *, int *, int *, int *);
    
    int main(void)
    {
        Matrix a, b;
        InitMatrixA(&a);
        int *arrA1 = getIndexArr(a);
        int *arrA2 = getNotZeroSuchRow(a);
        InitMatrixB(&b);
        int *arrB1 = getIndexArr(b);
        int *arrB2 = getNotZeroSuchRow(b);
        Multiply(a, b, arrA1, arrB1, arrA2, arrB2);
        return 0;
    }
    
    void InitMatrixA(Matrix *pMatrix)
    {
        pMatrix->cols = 7;
        pMatrix->rows = 4;
        pMatrix->counts = 9;
        Member *p = (Member *)malloc(sizeof(Member) * pMatrix->counts + 1);
        p[1].row = 1; p[1].col = 2; p[1].x = 8;
        p[2].row = 1; p[2].col = 5; p[2].x = 6;
        p[3].row = 2; p[3].col = 2; p[3].x = 1;
        p[4].row = 2; p[4].col = 4; p[4].x = 3;
        p[5].row = 3; p[5].col = 1; p[5].x = 7;
        p[6].row = 3; p[6].col = 4; p[6].x = 2;
        p[7].row = 3; p[7].col = 6; p[7].x = 4;
        p[8].row = 4; p[8].col = 3; p[8].x = 8;
        p[9].row = 4; p[9].col = 7; p[9].x = 5;
        pMatrix->arr = p;
        printf("矩阵A:\n");
        PrintMatrix(*pMatrix);
    }
    
    void InitMatrixB(Matrix *pMatrix)
    {
        pMatrix->rows = 7;
        pMatrix->cols = 3;
        pMatrix->counts = 6;
        Member *p = (Member *)malloc(sizeof(Member) * pMatrix->counts + 1);
        p[1].row = 1; p[1].col = 1; p[1].x = 1;
        p[2].row = 2; p[2].col = 3; p[2].x = 2;
        p[3].row = 4; p[3].col = 2; p[3].x = 9;
        p[4].row = 5; p[4].col = 1; p[4].x = 3;
        p[5].row = 6; p[5].col = 3; p[5].x = 6;
        p[6].row = 7; p[6].col = 2; p[6].x = 4;
        pMatrix->arr = p;
        printf("矩阵B:\n");
        PrintMatrix(*pMatrix);
    }
    
    void PrintMatrix(Matrix matrix)
    {
        int index = 1;
        for (int i = 1; i <= matrix.rows; i++)
        {
            for (int j = 1; j <= matrix.cols; j++)
            {
                if (i == matrix.arr[index].row && j == matrix.arr[index].col)
                    printf("%d ", matrix.arr[index++].x);
                else
                    printf("0 ");
            }
            printf("\n");
        }
    }
    
    int *getIndexArr(Matrix matrix)
    {
        // 要返回的目的数组
        int *p = (int *)malloc(sizeof(int) * matrix.rows);
        // 求每一行有多少个非0元的数组
        int arr[100] = {0};
        for (int i = 1; i <= matrix.counts; i++)
            arr[matrix.arr[i].row]++;
        p[1] = 1;
        for (int i = 2; i <= matrix.rows; i++)
            p[i] = p[i - 1] + arr[i - 1];
        return p;
    }
    int *getNotZeroSuchRow(Matrix matrix)
    {
        int *p = (int *)malloc(sizeof(int) * (matrix.rows + 1));
        // 将每个数组元素初始化为0
        for (int i = 0; i < matrix.rows + 1; i++)
            p[i] = 0;
        for (int i = 1; i <= matrix.counts; i++)
            p[matrix.arr[i].row]++;
        return p;
    }
    void Multiply(Matrix a, Matrix b, int *arr1, int *brr1, int *arr2, int *brr2)
    {
        int *temp = (int *)malloc(sizeof(int) * (b.cols + 1));
        for (int i = 0; i < b.cols + 1; i++)
            temp[i] = 0;
        int index = 1;
        printf("矩阵 C = A × B:\n");
        // arr和brr分别存储了矩阵A矩阵B每行首个非零元在三元组数组中的下标
        for (int i = 1; i <= a.rows; i++)
        {
            for (int j = 1; j <= arr2[i]; j++)
            {
                // a的三元组数组中每个元素的列数
                Member aMember = a.arr[index];
                int colOfSuchMemberA = aMember.col;
                // 去b矩阵的brr数组中找到行为上面得到的列数的第一个非零元的下标
                int indexOfNotZeroOfRowOfB = brr1[colOfSuchMemberA];
                for (int i = 1; i <= brr2[colOfSuchMemberA]; i++)
                {
                    Member bMember = b.arr[indexOfNotZeroOfRowOfB + i - 1];
                    temp[bMember.col] += bMember.x * aMember.x;
                }
                index++;
            }
            // 内层循环一次,代表C矩阵的一行已经被计算出来
            for (int i = 1; i <= b.cols; i++)
            {
                printf("%d ", temp[i]);
                temp[i] = 0;
            }
            printf("\n");
        }
    }
    
    更多相关内容
  • python稀疏矩阵乘法

    2018-12-04 10:51:27
    稀疏矩阵是机器学习中的重要工具。本代码为自己编写。初学者,希望大家批评指正。
  • 大型稀疏矩阵之间的乘法可能会导致内存不足错误。 这个简单的函数分解了两个非常大的稀疏矩阵相乘的问题。 无论该函数对稀疏矩阵还是稠密矩阵都适用,它的实用性仅在稀疏矩阵的情况下才明显。
  • [2]2带行表的矩阵相乘算法在用矩阵表示的图形中,可以发现矩阵中的零元素非常多,通常认为δ时称为稀疏矩阵(δ=非零元素个数/元素总数)。用上面的算法中,不论M(i,k)和N(k,j)的值是否为零,都要进行一次乘法运算,而实际...
  • 数据结构 稀疏矩阵乘法

    千次阅读 2019-03-18 16:29:08
    【数据结构】稀疏矩阵乘法 1.传统矩阵相乘的算法使用三个嵌套循环实现,算法复杂度为O(m * n1 * n2) 2.使用三元组顺序表存储稀疏矩阵时,实现 Q= M * N,对于M中M(i,j)元素来说,只需要与N中第j行元素N(j,q)...

    【数据结构】稀疏矩阵乘法

    1.传统矩阵相乘的算法使用三个嵌套循环实现,算法复杂度为O(m * n1 * n2)
    2.使用三元组顺序表存储稀疏矩阵时,实现 Q= M * N,对于M中M(i,j)元素来说,只需要与N中第j行元素N(j,q)相乘,再存入Q(i,q)中。为了实现这一操作,增加一个向量rpos,表示每一行的第一个非零元在三元组中的位置,rpos作用相当于快速转置中的cpot向量。
    这种结构叫做 行链接的顺序表

    typedef struct {
    	Triple data[MAXSIZE + 1]; //非零三元组表,data0未用
    	int rpos[MAXRC + 1];	  //各行第一个非零元的位置表
    	int mu, nu, tu;			  //三元组行数,列数,非零元素值
    }RLSMatrix;
    

    在创建矩阵时,需要求得矩阵的rpos向量,求法与cpot一致。

    Status CreateRLSMatrix(RLSMatrix &M) {
    	cout << "输入矩阵行数,列数,非零元素个数:" << endl;
    	cin >> M.mu >> M.nu >> M.tu;
    	cout << "依次输入" << M.tu << "个元素的行数,列数,元素值:" << endl;
    	for (int i = 1; i <= M.tu; i++)
    	{
    		cin >> M.data[i].i >> M.data[i].j >> M.data[i].e;
    	}
    	int* num = (int*)malloc(M.mu * sizeof(int));
    	int arow;
    	int q;
    	if (M.tu) {
    		for ( arow = 1; arow <= M.mu; ++arow) num[arow] = 0;
    		for (int t = 1; t <= M.tu; ++t) ++num[M.data[t].i];//求M中每一行含非零元个数
    		M.rpos[1] = 1;
    		//求第col列中第一个非零元在b.data 中的序号
    		for (arow = 2; arow <= M.mu; ++arow)M.rpos[arow] = M.rpos[arow - 1] + num[arow - 1];
    	}
    		cout << "矩阵构造完成" << endl;
    	return OK;
    }
    

    稀疏矩阵乘法
    算法思路:
    大循环是对M中的每一行进行。
    rpos向量用来确定每行元素个数
    再对该行每个元素M(i,j)进行处理,找到N中对应的第 j 行,将这一行所有元素与M(i,j)相乘,结果存入ctemp累加器中,该行元素都处理完成后,ctemp中所存储的便是Q中第 i 行数据

    Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
    	//求稀疏矩阵乘积 Q = M x N  采用行逻辑链接存储表示
    	if (M.nu != N.mu)return ERROR;
    	Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;
    	int arow,tp,p,brow,t,q,ccol;
    	int* ctemp = (int*)malloc((M.mu+1) * sizeof(int));
    	if (M.tu * N.tu != 0) {
    		for (arow = 1; arow <= M.mu; ++arow) {
    		//对M的每行进行处理
    			for (int i = 0; i <= M.mu; i++)ctemp[i] = 0;//累加器清零
    			Q.rpos[arow] = Q.tu + 1;
    			if (arow < M.mu)tp = M.rpos[arow + 1];
    			else tp = M.tu + 1;//确定M中该行元素个数
    			for ( p = M.rpos[arow]; p < tp; p++)
    			{//M中对该行的每个元素进行处理
    				brow = M.data[p].j;
    				if (brow < N.mu) t = N.rpos[brow + 1];
    				else t = N.tu + 1;
    				for (q = N.rpos[brow]; q < t; ++q) {
    				//将该元素与矩阵N中对应行的元素进行相乘,结果存入累加器
    					ccol = N.data[q].j;
    					ctemp[ccol] += M.data[p].e *N.data[q].e;
    				}
    			}
    			for(ccol =1;ccol<=Q.nu;++ccol)
    				if (ctemp[ccol]) {
    				//第arow行处理完毕,将累加器中值存入Q中
    					if (++Q.tu > MAXSIZE)return ERROR;
    					Q.data[Q.tu] = { arow, ccol, ctemp[ccol] };
    				}//if
    		}//for arow
    	}//if
    }
    

    该算法总的时间复杂度为O(M.mu * N.nu + M.tu * N.tu/N.mu)
    ctemp初始化 O(M.mu * N.nu
    求Q中所有非零元 O(M.tu * N.tu / N.mu
    压缩存储 O(M.mu * N.nu

    展开全文
  • Java 和 Scala 中的一些旧的稀疏矩阵乘法内容。 Java 在我们比较的 C(或者是 C++)基准测试中表现良好。 Scala 版本需要工作,我在对集合库没有牢牢把握的时候写的; 它可以大大改进。 去做 并行版本测试 使 Scala ...
  • 稀疏矩阵乘法matlab

    2012-06-04 11:16:56
    稀疏矩阵乘法matlab实现,三元法实现函数,代码附上
  • ##稀疏矩阵向量乘法与 MPI 并行###Design 使用 MPI 并行化稀疏矩阵向量乘法: 在步骤 1 中使用一维行分解读取文件并将数据分发到所有处理器,这需要 O(n) 然后 O(nnz) 其中 n 是行数,nnz 是矩阵。 矩阵 A 数据以 ...
  • 稀疏矩阵乘法(C语言)

    万次阅读 2021-03-30 20:06:34
    代码: #include<stdio.h> #include<stdlib.h> #define MAXSIZE 1000 typedef struct{ int row;//第几行 ...//稀疏矩阵的行,列,非零元素的个数 }TSMatrix; void createTSMatrix(TSM.

    在这里插入图片描述
    在这里插入图片描述

    代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 1000
    typedef struct{
    int row;//第几行
    int col;//第几列
    int e;//存储的值
    }Triple;
    
    typedef struct
    {
        Triple data[MAXSIZE];
        int m,n,len;//稀疏矩阵的行,列,非零元素的个数
    }TSMatrix;
    
    void createTSMatrix(TSMatrix *A)//创建矩阵
    {    int i=0;     //data【0】未用
        scanf("%d?%d",&A->m,&A->n);
        int flag = 1;
        int a,b,c;
        char c1,c2,c3;
        while(flag)
        {
            scanf("%d?%d?%d",&a,&b,&c);
    
    
              if(a==0&&b==0&&c==0)
                break;
                i++;
              A->data[i].row=a;
              A->data[i].col=b;
              A->data[i].e=c;
    
    
        }
        A->len=i;
    }
    
    void printMatrix(TSMatrix *B)//输出矩阵
    {
        for(int i=1;i<=B->len;i++)
        {
            printf("%d?%d?%d\n",B->data[i].row,B->data[i].col,B->data[i].e);
        }
    
    }
    
    void MulTSMatrix(TSMatrix *A,TSMatrix *B,TSMatrix *C)//矩阵相乘
    {
        C->len=0;
        int p,q,x,cnt;
        int i1,j1;
        int sum;
        cnt=1;
        for(int i=1;i<=A->m;i++)
        {
    
            for(int j=1;j<=B->n;j++)//遍历每行每列
            {
               sum=0;
                for(int k=1;k<=A->n;k++)//每个行与每个列单个数的遍历
                {    p=0;q=0;
                    for(i1=1;i1<=A->len;i1++){  //遍历A找符合i行k列的数
                        if(A->data[i1].row==i&&A->data[i1].col==k) p=A->data[i1].e;
                       }
                       for(j1=1;j1<=B->len;j1++){//遍历B找符合k行j列的数
                        if(B->data[j1].row==k&&B->data[j1].col==j) q=B->data[j1].e;
                       }
                    sum=sum+(p*q);
    
                }
                if(sum!=0) {cnt++;
                C->data[cnt].e=sum;
                C->data[cnt].row=i;
                C->data[cnt].col=j;}
    
            }
        }
        C->len=cnt;
    
    }
    
    int main()
    {
        TSMatrix A,B,C;
        createTSMatrix(&A);
        createTSMatrix(&B);
        MulTSMatrix(&A,&B,&C);
        printMatrix(&C);
        return 0;
    
    }
    
    

    第二个程序:
    首先将矩阵每行的非0元个数记下来,那么矩阵每行第一个非0元在三元表的位置就是上一行非0元个数加上上一行首个非0元位置之和。这样就可以不用遍历三元表,就可以快速找到相应的三元组表元素。相乘时先将结果存入一个数组中,然后取其中非0元素存入新的三元组表。最后输出新三元组表即可。

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Triple
    {
        int ti;
        int tj;
        int value;
    };
    
    struct tripleList
    {
        struct Triple T[2000];
        int li;
        int lj;
        int ln;
    };
    
    void createNewTripleList (struct tripleList *list);
    void getRowPot (struct tripleList *list,int rowPot[]);
    void clear (struct tripleList *list);
    void printTripleList (struct tripleList *list);
    void mul (struct tripleList *list1,struct tripleList *list2,struct tripleList *list3,int rowPot1[],int rowPot2[]);
    void run ();
    
    int main()
    {
        run ();
    
        return 0;
    }
    
    void run ()
    {
        int rowPot1[2000]={0},rowPot2[2000]={0};
        struct tripleList list1,list2,list3;
    
        createNewTripleList (&list1);//输入两个三元组表
        createNewTripleList (&list2);
        getRowPot (&list1,rowPot1);//得到它们的位置数组
        getRowPot (&list2,rowPot2);
    
        mul (&list1,&list2,&list3,rowPot1,rowPot2);//相乘
        printTripleList (&list3);//输出
    }
    void createNewTripleList (struct tripleList *list)
    {
        int i=0,a,b,c;
        scanf ("%d?%d",&(list->li),&(list->lj));//输入行数列数
        while (1)
        {
            scanf ("%d?%d?%d",&a,&b,&c);//输入行 列 数据
            if (a==0&&b==0&&c==0)//都为0时停止输入
            {
                break;
            }
            list->T[i].ti=a-1;//赋值,因为题目输入的行列数据是从1开始的,这里将它转为以0开始,最后输出时在加上1
            list->T[i].tj=b-1;
            list->T[i].value=c;
            i++;
        }
        list->ln=i;//得到三元组表元素个数
    }
    
    void printTripleList (struct tripleList *list)
    {
        int i;
        for (i=0;i<=list->ln-1;i++)//输出三元组表的所有元素
        {
            printf ("%d?%d?%d\n",list->T[i].ti+1,list->T[i].tj+1,list->T[i].value);
        }
    }
    
    void mul (struct tripleList *list1,struct tripleList *list2,struct tripleList *list3,int rowPot1[],int rowPot2[])
    {
        int i,j,k,l,no,max,n,len1,len2,A[2000]={0};
        list3->li=list1->li;//得到行列
        list3->lj=list2->lj;
        for (i=0,n=0;i<=list1->li-1;i++)//遍历第一个矩阵的行
        {
            len1=rowPot1[i+1]-1;//得到这一行的所有非0元在三元组表的位置区间的右端
            for (j=rowPot1[i],max=0;j<=len1;j++)//在这一行所有非0元在三元组表中的位置区间中遍历
            {
                len2=rowPot2[list1->T[j].tj+1]-1;//得到第二个矩阵中列号与上一个for中的行号相等的所有非0元在三元组表的位置区间的最左端
                for (k=rowPot2[list1->T[j].tj];k<=len2;k++)//在这一行所有非0元在三元组表中的位置区间遍历
                {
                    no=list2->T[k].tj;
                    A[no]+=list1->T[j].value*list2->T[k].value;//在数组中添加相乘结果
                    max=no>max?no:max;
                }
            }
            for (l=0;l<=max;l++)
            {
                if (A[l]!=0)//将非0的结果存入新的三元组表中
                {
                    list3->T[n].ti=list1->T[j-1].ti;
                    list3->T[n].tj=l;
                    list3->T[n].value=A[l];
                    ++n;
                    A[l]=0;
                }
            }
        }
        list3->ln=n;//得到新三元组表的元素个数
    }
    
    void getRowPot (struct tripleList *list,int rowPot[])
    {
        int n[2000]={0};
        int i,pre1=0,pre2=0;
        for (i=0;i<=list->ln-1;i++)//得到矩阵每行的非0元个数
        {
            (n[list->T[i].ti])++;
        }
        for (i=0;i<=list->li;i++)
        {
            rowPot[i]=pre1+pre2;//本行第一个非0元素在三元组表中的位置,上一行的非0元个数加上上一行第一个非0元在三元组表中的位置
            pre1=n[i];
            pre2=rowPot[i];
        }
    }
    
    

    运行截图:

    在这里插入图片描述

    展开全文
  • [数据结构]稀疏矩阵乘法算法实现

    千次阅读 2018-06-21 20:19:56
    作者zhonglihao算法名稀疏矩阵乘法 Sparse Matrix Multiply Method分类数据结构复杂度O(n^2)形式与数据结构C++代码 一维结构体存储特性极简封装 不使用链表 不需要转置 计算过程容易理解具体参考出处《算法导论》(写...


    作者zhonglihao
    算法名稀疏矩阵乘法 Sparse Matrix Multiplication
    分类数据结构
    复杂度O(n^2)
    形式与数据结构C++代码 一维结构体存储
    特性极简封装 不使用链表 不需要转置 计算过程容易理解
    具体参考出处《算法导论》(写的不想看)
    备注

    // ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    //稀疏矩阵存储结构体 第一个元素为矩阵头,包含行列长度,元素总个数
    typedef struct
    {
    	int row;
    	int col;
    	int element;
    }sparse_mat;
    
    void SparseMatrixRectPrint(sparse_mat* s_mat);
    void SparseMatrixTriPrint(sparse_mat* s_mat);
    sparse_mat* SparseMatrixMul(sparse_mat* s_mat_A, sparse_mat* s_mat_B);
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int i, j, k;
    	const int mat_A_row = 4;
    	const int mat_A_col = 4;
    	const int mat_B_row = 4;
    	const int mat_B_col = 4;
    
    	//原矩阵
    	int mat_A[mat_A_row][mat_A_col] = { 1, 1, 0, 0,
    										0, 0, 1, 0, 
    										0, 1, 0, 0, 
    										0, 0, 1, 0 };
    
    	int mat_B[mat_B_row][mat_B_col] = { 1, 0, 0, 0,
    										0, 1, 0, 0, 
    										0, 0, 1, 0, 
    										0, 0, 0, 1 };
    
    	//计算有效元素数量
    	int mat_A_ele_count = 0;
    	int mat_B_ele_count = 0;
    
    	for (i = 0; i < mat_A_row; i++)
    	{
    		for (j = 0; j < mat_A_col; j++)
    		{
    			if (mat_A[i][j] != 0) mat_A_ele_count++;
    		}
    	}
    
    	for (i = 0; i < mat_B_row; i++)
    	{
    		for (j = 0; j < mat_B_col; j++)
    		{
    			if (mat_B[i][j] != 0) mat_B_ele_count++;
    		}
    	}
    
    	//动态分配
    	sparse_mat* sparse_m_A = (sparse_mat*)malloc((mat_A_ele_count + 1)*sizeof(sparse_mat));
    	sparse_mat* sparse_m_B = (sparse_mat*)malloc((mat_B_ele_count + 1)*sizeof(sparse_mat));
    
    	//存入稀疏矩阵信息
    	sparse_m_A[0].row		= mat_A_row;
    	sparse_m_A[0].col		= mat_A_col;
    	sparse_m_A[0].element	= mat_A_ele_count;
    	sparse_m_B[0].row		= mat_B_row;
    	sparse_m_B[0].col		= mat_B_col;
    	sparse_m_B[0].element	= mat_B_ele_count;
    
    	for (i = 0, mat_A_ele_count = 0; i < mat_A_row; i++)
    	{
    		for (j = 0; j < mat_A_col; j++)
    		{
    			if (mat_A[i][j] != 0)
    			{
    				mat_A_ele_count++;
    				sparse_m_A[mat_A_ele_count].element = mat_A[i][j];
    				sparse_m_A[mat_A_ele_count].row = i;
    				sparse_m_A[mat_A_ele_count].col = j;
    			}
    		}
    	}
    
    	for (i = 0, mat_B_ele_count = 0; i < mat_B_row; i++)
    	{
    		for (j = 0; j < mat_B_col; j++)
    		{
    			if (mat_B[i][j] != 0)
    			{
    				mat_B_ele_count++;
    				sparse_m_B[mat_B_ele_count].element = mat_B[i][j];
    				sparse_m_B[mat_B_ele_count].row = i;
    				sparse_m_B[mat_B_ele_count].col = j;
    			}
    		}
    	}
    
    	//打印原数组
    	SparseMatrixRectPrint(sparse_m_A);
    	SparseMatrixRectPrint(sparse_m_B);
    	//SparseMatrixTriPrint(sparse_m_A); 
    	//SparseMatrixTriPrint(sparse_m_B);
    
    	//计算稀疏矩阵乘法
    	sparse_mat* sparse_m_C = (sparse_mat*)SparseMatrixMul(sparse_m_A, sparse_m_B);
    	SparseMatrixRectPrint(sparse_m_C);
    
    	system("Pause");
    	return 0;
    }
    
    //三元组稀疏矩阵乘法函数 极简封装 需要花费一点时间计算申请的内存 但是肯定比链表省空间啦
    //Method Written By Zhonglihao
    sparse_mat* SparseMatrixMul(sparse_mat* s_mat_A, sparse_mat* s_mat_B)
    {
    	int i, j, k;
    	int s_mat_C_row			= s_mat_A[0].row;
    	int s_mat_C_col			= s_mat_B[0].col;
    	int s_mat_A_ele_count	= s_mat_A[0].element;
    	int s_mat_B_ele_count   = s_mat_B[0].element;
    
    	//判断是否能够相乘 或 有一个全为0 那就不用乘啦
    	if (s_mat_A[0].col != s_mat_B[0].row) return NULL;
    	if (s_mat_A_ele_count == 0 || s_mat_B_ele_count == 0)
    	{
    		sparse_mat* s_mat_C	= (sparse_mat*)malloc((1)*sizeof(sparse_mat));
    		s_mat_C[0].row		= s_mat_C_row;
    		s_mat_C[0].col		= s_mat_C_col;
    		s_mat_C[0].element	= 0;
    		return s_mat_C;
    	}
    
    	//申请一个长度为B列宽的缓存 两个用途 计算输出大小时做列封禁,计算相乘时做和缓存
    	int* col_buffer = (int*)malloc(s_mat_C_col*sizeof(int));
    	//清空缓存区
    	for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;
    
    	//判断需要输出的三元大小申请内存
    	int malloc_element_count = 0;
    	for (i = 1; i <= s_mat_A_ele_count; i++)
    	{
    		if (i >= 2 && s_mat_A[i].row != s_mat_A[i - 1].row) //换行解禁
    		{
    			for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;
    		}
    
    		for (j = 1; j <= s_mat_B_ele_count; j++)
    		{
    			if ((s_mat_A[i].col == s_mat_B[j].row) && col_buffer[s_mat_B[j].col] != 1)//没有列封禁
    			{
    				col_buffer[s_mat_B[j].col] = 1;//列封禁
    				malloc_element_count++;
    			}
    		}
    	}
    
    	sparse_mat* s_mat_C		= (sparse_mat*)malloc((malloc_element_count + 1)*sizeof(sparse_mat));
    	s_mat_C[0].row			= s_mat_C_row;
    	s_mat_C[0].col			= s_mat_C_col;
    	s_mat_C[0].element		= malloc_element_count;
    	int s_mat_C_ele_count	= 0;//用于存入元素时做指针
    
    	//开始进行乘法相乘
    	for (k = 0; k < s_mat_C_col; k++) col_buffer[k] = 0;//清理列缓存
    	for (i = 1; i <= s_mat_A_ele_count; i++)
    	{
    		for (j = 1; j <= s_mat_B_ele_count; j++)
    		{
    			if (s_mat_A[i].col == s_mat_B[j].row)//有效用 压入缓存区
    				col_buffer[s_mat_B[j].col] += s_mat_A[i].element * s_mat_B[j].element;
    		}
    
    		//如果要换行或者是最后一行
    		if (((i != s_mat_A_ele_count) && (s_mat_A[i].row != s_mat_A[i + 1].row)) || i == s_mat_A_ele_count)
    		{
    			//扫描缓存组
    			for (k = 0; k < s_mat_C_col; k++)
    			{
    				//如果该点不是0 压入三元组 清零缓存
    				if (col_buffer[k] != 0)
    				{
    					s_mat_C_ele_count++;
    					s_mat_C[s_mat_C_ele_count].row = s_mat_A[i].row;
    					s_mat_C[s_mat_C_ele_count].col = k;
    					s_mat_C[s_mat_C_ele_count].element = col_buffer[k];
    					col_buffer[k] = 0;
    				}
    			}
    		}
    	}
    
    	//释放缓存 返回结果
    	free(col_buffer);
    	return s_mat_C;
    }
    
    //稀疏矩阵打印 按矩形打印 需要确定三元组按Z排列有序
    void SparseMatrixRectPrint(sparse_mat* s_mat)
    {
    	//获取行列信息
    	int i, j;
    	int row = s_mat[0].row;
    	int col = s_mat[0].col;
    
    	//打印元素递增 前提是三元组按照行列顺序排好,就只需要递增下标
    	int ele_count = 1;
    
    	//按矩阵扫描打印
    	for (i = 0; i < row; i++)
    	{
    		for (j = 0; j < col; j++)
    		{
    			if (i == s_mat[ele_count].row && j == s_mat[ele_count].col)
    			{
    				printf("%d\t", s_mat[ele_count].element);
    				ele_count++;
    			}
    			else
    			{
    				printf("0\t");
    			}
    		}//for
    		printf("\n");
    	}//for
    	
    	//跳空换行 返回
    	printf("\n");
    	return;
    }
    
    //稀疏矩阵打印 按三元组结构打印
    void SparseMatrixTriPrint(sparse_mat* s_mat)
    {
    	int i, j;
    	int ele_count = s_mat[0].element;
    
    	//按顺序打印
    	for (i = 1; i <= ele_count; i++)
    	{
    		printf("%d\t%d\t%d\n", s_mat[i].row, s_mat[i].col, s_mat[i].element);
    	}
    
    	//跳空换行 返回
    	printf("\n");
    	return;
    }
    


    展开全文
  • (五)1.1_稀疏矩阵乘法的快速运算

    万次阅读 多人点赞 2018-11-30 01:01:41
      有矩阵M和N,都是用三元组压缩存储,设计高效率算法求矩阵M*N得到的矩阵Q(也用三元组压缩存储). 二.思路分析 假设矩阵M*N=Q 如下 那么得到的矩阵Q有三行三列,第一列中的元素有这样的关系 所以我们可以...
  • 矩阵乘法简单,但是这个压缩方法,大家的博客对我来说有点难以理解,先留个坑,稍后补全 https://www.pianshen.com/article/86351046178/ https://www.cnblogs.com/YangZnufe/p/8413374.html
  • SpMV_CSR 使用压缩稀疏行格式的稀疏矩阵矢量乘法来编译代码,请使用gcc CSR.c mmio.c -o csr ./csr [filename.mtx]
  • 状态:活动(在活动开发中,可能会发生重大更改)稀疏blocksparse软件包包含TensorFlow Ops和用于块稀疏矩阵乘法的相应GPU内核。 还包括相关操作,例如边缘偏差,稀疏权重规范和图层规范。 要了解更多信息,请参阅。...
  • 用C++编写的稀疏矩阵乘法运算,稀疏矩阵采用十字链表存储及计算
  • 稀疏矩阵乘法.cpp

    2014-02-14 17:50:43
    稀疏矩阵乘法.cpp
  • 稀疏矩阵乘法

    2019-10-25 12:53:11
    稀疏矩阵 1、定义稀疏矩阵的数据结构,是个三元组 #include<stdio.h> #define MAXSIZE 12500 typedef struct{ int i,j; int e; }Triple; typedef struct{ Triple data[MAXSIZE+1]; int mu,nu,tu; //mu行数...
  • Matlab 的内置稀疏矩阵乘法函数会在不应该发生的情况下导致内存不足异常。 这个文件可以节省一天! 用“mex mex_amub.cpp”编译它。
  • 高效简洁的三元组稀疏矩阵乘法.pdf
  • 1 import threading, time 2 import numpy as np 3 res = [] 4 class MyThread(threading.Thread): 5 def __init__(self,i,j,m1,m2): 6 threading.Thread.__init__(self) 7 se...
  • 稀疏矩阵乘法 稀疏矩阵乘法
  • I want to multiply a sparse matrix A, with a matrix B which has 0, -1, or 1 as elements. To reduce the complexity of the matrix multiplication, I can ignore items if they are 0, or go ahead and add th...
  • pytorch中,sparse中的稀疏矩阵乘法。A是一个(10,10)的稀疏矩阵,B是一个(2,10,6)的普通多维矩阵。 # batch 是一个 (2,10, 8)的三维矩阵,w1 是一个(8,6)的二维矩阵 support = torch.matmul(batch, w1) # ...
  • 稀疏矩阵乘法运算

    千次阅读 2020-10-28 15:42:14
    稀疏矩阵乘法运算题目信息输入输出测试样例解答想法 题目信息 数据压缩是提高传输、存储效率一种技术。 本实验要求实现两个稀疏矩阵相乘积的算法。其中稀疏矩阵非零元素数量小于100. 输入 第1个稀疏矩阵的行数,列...
  • 数据结构实验2.4:稀疏矩阵乘法

    千次阅读 2020-05-31 20:43:16
    //稀疏矩阵乘法(三元组) #include <stdio.h> #include <stdlib.h> #define max 200 typedef struct Triple{ int i,j;//i行j列 int e; }Triple; typedef struct TSMaTrix{ Triple elem[max]; int ...
  • 最近由于研究需要和兴趣看了很多稀疏矩阵乘法的算法,这方面的研究千奇百怪,研究人员真的是十八般武艺全都用上了,好吧,就让我来说说这个东西吧,由于这个东西实在方法太多,所以请容许我一节一节地去完善。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,902
精华内容 4,360
关键字:

稀疏矩阵的乘法

友情链接: 123key.rar