行索引稀疏矩阵查找某一列的元素没那么方便,所以在做矩阵乘法时(这里以M乘N=Q为例),严书的做法是:在求Q的某一行的值是,用M的一行去遍历N的每一行,对结果中同列的值进行累加,最后稀疏化存入Q的当前行中,这个过程还原成正常矩阵比较容易理解:
求Q(2,2)的第一行时,肯定是M的第一行和N的第一列逐乘再累加,然后再M的第一行和N的第二列逐乘累加
M(2,3)* N(3,2):
直接算的话就是:
Q[1,1] = 1*1 + 2*0 + 3*1 = 1+0+3 = 4
Q[1,2] = 1*0 + 2*1 + 3*1 = 0+2+3 = 5
这回我们直接同时求两列的值,其实就是改变一下计算顺序:
这个就相当于严书代码中ctemp的作用,只不过ctemp是直接累加.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_E = 1e+4+5, MAX_R = 105;
//严版特色,下标从1开始
struct Triple{
int i,j,e;};
struct RLSMatrix{
Triple data[MAX_E];
int rpos[MAX_R];//行首索引, rpos[i]指向第i行中的首元素在data中的序号, 则rpos[i+1]-1指向第i行中最后一个非0元素在N.data中的序号.
int rows, cols, elems;
};
int ctemp[MAX_R];//Q的第i行元素结果累加器,算完一行就压缩存储进Q.data中
RLSMatrix mul(RLSMatrix M, RLSMatrix N){
RLSMatrix Q;
Q.rows = M.rows;Q.cols = N.cols;Q.elems = 0;
if(M.elems * N.elems != 0){
// Q是非零矩阵
for(int arow = 1; arow <= M.rows; arow++){
memset(ctemp, 0, sizeof(ctemp)); //到了下一行,清零
Q.rpos[arow] = Q.elems+1; //新一行的行首索引是当前data中元素个数+1,从该处继续向data中存三元组
int tp; //用tp指向data中该行行末的下一个位置,方便遍历
if(arow < M.rows) tp = M.rpos[arow+1]; //如果不是最后一行, tp指向下一行行首
else tp = M.elems+1; //最后一行, tp直接指向data中最后一个+1
for(int p = M.rpos[arow];p < tp; p++){
//对当前行找到的每一个非零元
int brow = M.data[p].j; //找到对应元在N中的行号(M中某行第三列的元素, 肯定和N中第三行某列的元素相乘)
int t;//和tp同样的套路
if(brow < N.rows) t = N.rpos[brow+1];
else t = N.elems+1;
for(int q = N.rpos[brow]; q < t; q++){
//这里不是直接算出M的某行乘N的某列的值
//而是用M的某行,去遍历N的所有行,然后对每行的应该在同列的值进行累加
int ccol = N.data[q].j;
ctemp[ccol] += M.data[p].e * N.data[q].e;//累加器
}
}//求得Q中第crow(=arow)行的非零元
for(int ccol = 1; ccol <= Q.cols; ++ccol){
//用M的一行遍历完了整个N矩阵
if(ctemp[ccol]){
Q.data[++Q.elems] = {
arow, ccol, ctemp[ccol]};//压缩存储
}
}
}
}
return Q;
}
RLSMatrix makeMat(){
/*
* 输入rows, cols, 三元组个数
* 输入三元组
*/
RLSMatrix A;
cin>>A.rows>>A.cols>>A.elems;
for(int i = 1;i <= A.elems;i++){
int x,y,e;
cin>>x>>y>>e;
A.data[i] = {
x,y,e};
}
/*
根据乘法中这段代码写的初始化rpos数组:
int tp; //用tp指向data中该行行末的下一个位置,方便遍历
if(arow < M.rows) tp = M.rpos[arow+1]; //如果不是最后一行, tp指向下一行行首
else tp = M.elems+1; //最后一行, tp直接指向data中最后一个+1
for(int p = M.rpos[arow];p < tp; p++) ...
可以看出如果某行没有元素,则让tp = M.rpos[arow]则可不进行遍历,也就是M.rpos[arow] = M.rpos[arow+1]
而当最后几行为空时,并不会执行else tp = M.elems+1;这时应该把rpos最后几行空的填成M.elems+1
*/
int row = 1;
for(int e = 1;e <= A.elems; e++){
int arow = A.data[e].i;
while(row <= arow){
A.rpos[row++] = e;
}
}
while(row <= A.rows){
//如果最后几行没有元素,让索引指到elems+1的位置
A.rpos[row++] = A.elems+1;
}
return A;
}
void printMat(RLSMatrix A){
cout<<"rows:"<<A.rows<<" cols:"<<A.cols<<" elems:"<<A.elems<<endl;
cout<<"-------------------------"<<endl;
cout<<"data:"<<endl;
for(int i = 1;i <= A.elems;i++) {
cout<<setw(4)<<A.data[i].i<<setw(4)<<A.data[i].j<<setw(4)<<A.data[i].e<<endl;
}
cout<<"-------------------------"<<endl;
cout<<"rpos: ";
for(int j = 1;j <= A.rows; j++){
cout<<A.rpos[j]<<' ';
}
cout<<endl<<endl;
}
int main(){
ios::sync_with_stdio(false);
RLSMatrix A = makeMat();
printMat(A);
RLSMatrix B = makeMat();
printMat(B);
RLSMatrix C = mul(A, B);
printMat(C);
return 0;
}
/*
严书上的例子
3 4 4
1 1 3
1 4 5
2 2 -1
3 1 2
4 2 4
1 2 2
2 1 1
3 1 -2
3 2 4
*/
文章浏览阅读3.5k次,点赞2次,收藏2次。在HTML5中,新增了两个元素---video元素与audio元素。video元素专门用来播放网络上的视频或电影,而audio元素专门用来播放网络上的音频数据。使用这两个元素,就不在需要使用其他插件了,只需要支持HTML5的浏览器即可。今天,我们在这里就详细的说说video元素它(video)的作用是用于播放视频。它所主要支持的文件格式有webm、ogg、MP4、MP3、WAVE。它的用法..._html5 前端 video 兼容 格式转换插件
文章浏览阅读625次。基本思想:简单学习了一下移植Google的日志包,以备后续跨平台直接使用;首先编译生成静态包,如果需要夸平台需要修改对应的编译器ubuntu@ubuntu:git clone https://github.com/gflags/gflags.gitubuntu@ubuntu:cd gflags/ubuntu@ubuntu:~/gflags$ mkdir buildubuntu@ubuntu:~/gflags/build$ cmake ..ubuntu@ubuntu:~/gflags/bui_clion自动导入包
文章浏览阅读1.7w次。原创: 思齐大神 来源:蚁开源社区很多同学会问,IT行业在中国并不是特别差的行业,而程序员的工资也并不低,但为什么中国的程序员总被称作码农或者说是苦逼的程序员?中国的程序员生活和欧美的有什么不一样?先说两个小段子街边,一对情侣在吵架。女孩对男孩说,“我们分手吧!”男孩沉默半天,开口问道,“我能再说最后一句话吗?”“说吧,婆婆妈妈的。”“我会编程……”“会编程有个屁用啊,现在到处都是会编程的人!”男孩涨红了脸,接着说道,“我会编程……我会变成…童话里,你爱的那个天使……”【程序._码农
文章浏览阅读259次。Java初学者也能看的懂的AQS学习AQS之前,你需要了解以下内容,如果不是很清楚,那么理解本文会有点吃力。(Java初学者得会一下内容)synchronizedCASLock前言synchronized首先我们知道synchronized是Java关键字,上锁释放锁等一切操作都是由JVM控制的。我们只能通过虚拟机的C++才能去研究其底层实现。我们除了判断synchronized是作为方法的修饰符,还是当做同步代码块使用以外,没什么需要我们程序员操作的。cas一种自旋的原子操作,也是J_aqs对接
文章浏览阅读460次。DescriptionSolution首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],_gdoi2018省选模拟树
文章浏览阅读2.8k次,点赞4次,收藏28次。我们进行简单的运算即可实现倒序。_字符串替换pta
文章浏览阅读3.3k次。不能删除。看看文件夹下的内容就知道:1、me_tcat:是MyEclipse记录的当前工作空间中的配置,比如当前工作空间中有哪些工程,打开了哪些文件java类,编辑了哪些文件和Java类,MyEclipse会在启动时加载这个文件夹下的内容。如果删除了,再次打开MyEclipse会发现工作空间是空的,需要重新导入工程。2、plugins:当前工作空间用到了哪些IDE插件,和程程序无关_metadata可以删除吗
文章浏览阅读4.1k次。SeetaFace2 Android 平台编译项目地址:https://github.com/seetafaceengine/SeetaFace2SeetaFace2 人脸识别引擎包括了搭建一套全自动人脸识别系统所需的三个核心模块,即:人脸检测模块 FaceDetector、面部关键点定位模块 FaceLandmarker 以及人脸特征提取与比对模块 FaceRecognizer。面部关键点定位支持 5 点 和 81 点定位,两个辅助模块 FaceTracker 和 QualityAssessor 用_seetafacerecognizer2.0.ats
文章浏览阅读3.2w次,点赞4次,收藏34次。1.删除约束语句:alter table 表名 drop constraint 约束名;alter table mz_sf4 drop constraint pk_id1;2.删除主键语句:alter table 表名 drop primary key;alter table mz_sf3 drop primary key;如果出错:ORA-02273:此唯一主键已_oracle删除主键的sql语句
文章浏览阅读989次,点赞9次,收藏13次。这份面试题几乎包含了他在一年内遇到的所有面试题以及答案,甚至包括面试中的细节对话以及语录,可谓是细节到极致,甚至简历优化和怎么投简历更容易得到面试机会也包括在内!也包括教你怎么去获得一些大厂,比如阿里,腾讯的内推名额!某位名人说过成功是靠99%的汗水和1%的机遇得到的,而你想获得那1%的机遇你首先就得付出99%的汗水!你只有朝着你的目标一步一步坚持不懈的走下去你才能有机会获得成功!成功只会留给那些有准备的人!《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》点击传送门即可获取。
文章浏览阅读2k次。关于Vertectorization哪些是正确的( )相对于其他编程模型,sql在大数据领域有哪些好处( )哪些部分适合做codegen( )关于内存计算描述不正确的有( )_vertectorization
文章浏览阅读306次。百度找到了某论坛高人写的java(具体论坛记不清了),直接用来调用,再次非常感谢,基本上实现了我的需求package MD5;import java.util.Scanner;public class ChineseToPinYin {/*** 汉字转拼音缩写** @param str* 要转换的汉字字符串* @return String 拼音缩写*/public Strin..._java生成拼音码