C++ Strassen算法代码的实现

2023-07-27 21:19:14 159

本文仅代码，无理论解释

实话实说，我觉得这个算法在C系列的语言下，简直垃圾到爆炸……毕竟是一群完全不懂程序数学家对着纸弄出来的，看起来好像非常的有用，实际上耗时是非常爆炸的。

但是《算法导论》里有啊……然后上课又要求手写一个

于是我就手写了一个……我尽可能的减少使用的空间同时加快速度了，当n=512的时候，内存使用量峰值没有超过10mb，而且是通过递归实现Strassen算法

其中，in.txt已经预先准备了3000000个范围在0-100随机数，避免程序在运算过程中爆int（虽然完全可以取1000）

/**
*CreatedbyMauveon3/29/2020.
*Copyright©2020Mauve,AllRightsReserved
*/

#include

usingnamespacestd;

/**
*矩阵相乘
*最终结果耗时结果保存至
*https://www.desmos.com/calculator/gl4tm5i1zu
*/

structmat{
unsignedrow,col;

mat(unsignedr,unsignedc):row(r),col(c){}

virtualint&pos_ref(unsignedi,unsignedj)=0;

virtualintpos(unsignedi,unsignedj)const=0;
};

structbase_mat;
structsub_mat;

stacksub_data;

structbase_mat:mat{
int*data;

base_mat(unsignedr,unsignedc):mat(r,c),data(newint[row*col]){}

~base_mat(){
delete[]data;
}

inlineint&pos_ref(unsignedi,unsignedj)override{
return*(data+i*col+j);
}

inlineintpos(unsignedi,unsignedj)constoverride{
return*(data+i*col+j);
}
};

unsignedmin_mul;

structsub_mat:mat{
mat*a,*b;
boolis_add;
unsignedoffset_ai,offset_aj,offset_bi,offset_bj;

explicitsub_mat(mat*data):mat(data->row,data->col),a(data),b(nullptr),
is_add(false),offset_ai(0),offset_aj(0),
offset_bi(0),offset_bj(0){sub_data.push(this);}

sub_mat(mat*data,boolof_i,boolof_j):mat(data->row>>1u,data->col>>1u),a(data),b(nullptr),
is_add(false),offset_ai(of_i?data->row>>1u:0),
offset_aj(of_j?data->col>>1u:0),
offset_bi(0),offset_bj(0){sub_data.push(this);}

inlineint&pos_ref(unsignedi,unsignedj)override{
assert(b==nullptr);
returna->pos_ref(i+offset_ai,j+offset_aj);
}

inlineintpos(unsignedi,unsignedj)constoverride{
if(b==nullptr)
returna->pos(i+offset_ai,j+offset_aj);
returna->pos(i+offset_ai,j+offset_aj)+(is_add?1:-1)*b->pos(i+offset_bi,j+offset_bj);
}

inlinesub_mat*operator+(sub_mat&other){
autores=newsub_mat(this);
res->b=&other;
res->is_add=true;
returnres;
}

inlinesub_mat*operator-(sub_mat&other){
autores=newsub_mat(this);
res->b=&other;
res->is_add=false;
returnres;
}

mat*operator*(sub_mat&other){
assert(col==other.row);
autores=newbase_mat(row,other.col);
if(col&1u||row&1u||col<=min_mul||row<=min_mul||other.col<=min_mul){
memset(res->data,0,sizeof(int)*res->row*res->col);
for(intk=0;kpos_ref(i,j)+=pos(i,k)*other.pos(k,j);
}else{
size_tsub_data_size=sub_data.size();
#definea(i,j)(*newsub_mat(this,i==2,j==2))
#defineb(i,j)(*newsub_mat(&other,i==2,j==2))
autom1=*(a(1,1)+a(2,2))**(b(1,1)+b(2,2));
autom2=*(a(2,1)+a(2,2))*b(1,1);
autom3=a(1,1)**(b(1,2)-b(2,2));
autom4=a(2,2)**(b(2,1)-b(1,1));
autom5=*(a(1,1)+a(1,2))*b(2,2);
autom6=*(a(2,1)-a(1,1))**(b(1,1)+b(1,2));
autom7=*(a(1,2)-a(2,2))**(b(2,1)+b(2,2));
#undefa
#undefb
unsignedhalf_row=row>>1u,half_col=col>>1u;
#definem(t)(m##t->pos(i,j))
//C11
for(unsignedi=0;ipos_ref(i,j)=m(1)+m(4)-m(5)+m(7);
//C12
for(unsignedi=0;ipos_ref(i,j+half_col)=m(3)+m(5);
//C21
for(unsignedi=0;ipos_ref(i+half_row,j)=m(2)+m(4);
//C22
for(unsignedi=0;ipos_ref(i+half_row,j+half_col)=m(1)-m(2)+m(3)+m(6);
#undefm
deletedynamic_cast(m1);
deletedynamic_cast(m2);
deletedynamic_cast(m3);
deletedynamic_cast(m4);
deletedynamic_cast(m5);
deletedynamic_cast(m6);
deletedynamic_cast(m7);
while(sub_data.size()>sub_data_size){
deletesub_data.top();
sub_data.pop();
}
}
returnres;
}
};

unsignedN=2;

voidsolve(){
cerr<<"N="<>a.pos_ref(i,j);
for(inti=0;i>b.pos_ref(i,j);

for(intt=1;t(z);
while(!sub_data.empty()){
deletesub_data.top();
sub_data.pop();
}
}

autox=newsub_mat(&a),y=newsub_mat(&b);
min_mul=10000;

autotime_1=clock();
autoz=*x**y;
autotime_2=clock();

cerr<<"tradition:"<(z);
while(!sub_data.empty()){
deletesub_data.top();
sub_data.pop();
}
N*=2;
if(N>=1000)exit(0);
}

signedmain(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdefACM_LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
longlongtest_index_for_debug=1;
characm_local_for_debug;
while(cin>>acm_local_for_debug&&acm_local_for_debug!='~'){
cin.putback(acm_local_for_debug);
if(test_index_for_debug>20){
throwruntime_error("Checkthestdin!!!");
}
autostart_clock_for_debug=clock();
solve();
autoend_clock_for_debug=clock();
cout<<"Test"<
到此这篇关于C++Strassen算法代码的实现的文章就介绍到这了,更多相关C++Strassen算法内容请搜索毛票票以前的文章或继续浏览下面的相关文章希望大家以后多多支持毛票票！

C++ Strassen算法代码的实现

热门推荐

随机推荐