【卡常Tips】关于矩阵乘法的玄妙优化

常规的矩阵乘法：

CPP

for(int i=0;i<M;i++)
			for(int j=0;j<M;j++) //<-
			{
				for(int k=0;k<M;k++) //<-
				{
					if(!b.a[k][j]||!a.a[i][k]) continue;
					c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
				} 
			}

如果我们将第二层和第三层循环交换，变成：

CPP

for(int i=0;i<M;i++)
			for(int k=0;k<M;k++) //<-
			{
				if(!a.a[i][k]) continue;
				for(int j=0;j<M;j++) //<-
				{
					if(!b.a[k][j]) continue;
					c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
				} 
			}

可以快上许多（实测39.67s -> 27.37s )

（可能的）原因：（本人猜测）

稀疏矩阵优化可以跳过更多判断的点
a[i][k]和b[k][j]调用连续，不需在内存中左右横跳

【卡常Tips】关于矩阵乘法的玄妙优化

讨论操作

回复

相关推荐

【卡常Tips】关于矩阵乘法的玄妙优化