【CSP CCF记录】202305-2第30次认证矩阵运算

题目

样例输入

3 2
1 2
3 4
5 6
10 10
-20 -20
30 30
6 5
4 3
2 1
4 0 -5

样例输出

480 240
0 0
-2200 -1100

思路

我的初步想法是按照题目所给计算顺序，分为三步计算，即：

1. $tmp1=Q\times K^{T}$ ，时间复杂度为 $O(n^{2}\cdot d)$

2. $tmp2=W\cdot tmp1$ ，时间复杂度为 $O(n)$

3. $result=tmp2\times V$ ，时间复杂度为 $O(n^{2}\cdot d)$

果不其然内存爆了。。。思考能否通过矩阵的运算性质改变计算顺序，降低时间复杂度。

点乘和矩阵乘法一起运算时，是否可以改变计算顺序呢？即 $(W\cdot (Q\times K^{T}))\times V$ 变为 $W\cdot( (Q\times K^{T})\times V)$ 。网上多半Transformer机制的含义进行解释，但是万一遇到不了解的机制怎么办，所以我还是进行了一个简陋的证明：

有了以上结论且已知矩阵乘法具有结合律，那么，我们可以把运算顺序改为 $W\cdot( Q\times (K^{T}\times V))$ ，这样三步计算分别为：

1. $tmp1=K^{T}\times V$ ，时间复杂度为 $O(d^{2}\cdot n)$

2. $tmp2=Q\times tmp1$ ，时间复杂度为 $O(d^{2}\cdot n)$

3. $result=W\cdot tmp2$ ，时间复杂度为 $O(n)$

由于d比n的数据范围要小得多，很显然我们降低了时间复杂度。

还思路不清的，希望下面对样例的手算可以帮助到你，注意i,j,k变量的遍历

代码

这里注意，由于数组较大，需将数组设置为全局变量（开在main()）之外，否则会导致栈溢出。

#include<bits/stdc++.h>
using namespace std;
int Q[10010][30]={0},K[10010][30]={0},V[10010][30]={0},W[10010]={0};
int Kt[30][10010]={0};
int n,d;
long long tmp1[30][30]={0};
long long tmp2[10010][10010]={0};
long long result[10010][30]={0};
int main()
{cin>>n>>d;//输入Q for(int i=0;i<n;i++){for(int j=0;j<d;j++){cin>>Q[i][j];}}//输入K，再转置为Kt for(int i=0;i<n;i++){for(int j=0;j<d;j++){cin>>K[i][j];Kt[j][i]=K[i][j];}}//输入V for(int i=0;i<n;i++){for(int j=0;j<d;j++){cin>>V[i][j];}}//输入W for(int i=0;i<n;i++){cin>>W[i]; }//tmp1=KtxVfor(int i=0;i<d;i++) {for(int j=0;j<d;j++){for(int k=0;k<n;k++){tmp1[i][j]+=Kt[i][k]*V[k][j];}//cout<<tmp1[i][j]<<" ";}//cout<<endl;}//tmp2=Qxtmp1,result=W·tmp2 for(int i=0;i<n;i++) {for(int j=0;j<d;j++){for(int k=0;k<d;k++){tmp2[i][j]+=Q[i][k]*tmp1[k][j];}result[i][j]=tmp2[i][j]*W[i];}}for(int i=0;i<n;i++){for(int j=0;j<d;j++){cout<<result[i][j]<<" ";}cout<<endl;}return 0;
}