重庆SEO深度解析
实战草根,野蛮生长,向阳而生

seo具体怎么优化矩阵系统蜘蛛屯 矩阵乘法的优化

主题地址:

为了优化昨晚的话题,我已经两点多了。我今天早上写博客。我对此不太确定,哈哈。

作为OJ的每个人都知道快速取幂,所以我不会罗talking,我所说的主要是矩阵乘法的优化。

一开始,我的代码用了1156毫秒,代码如下:

void  mat_mul( int (*a)[MAXN], int (*b)[MAXN], int (*c)[MAXN], int n ) {
        int  i, j, k;
        ULL  sum;
        for( i = 0; i < n; ++i ) {
                for( j = 0; j < n; ++j ) {
                        sum = 0;
                        for( k = 0; k < n; ++k ) sum = ( sum + (ULL)a[i][k] * (ULL)b[k][j] ) % P;
                        c[i][j] = sum;
                }
        }
}

因为结果需要取模,所以为了节省内存,我使用一个int数组存储矩阵(如果使用long long,则将内存加倍)。

我的想法是模拟笔的计算,每次确定c的位置,然后使用与a对应的行和与b对应的列来累加积。

使用局部变量sum来存储和,最后将其分配给c [i] [j],以便将和优化为寄存器。

该代码的问题是:1.每个计算都必须是模,并且是在最内层的循环中,在该循环中程序的计算量最大。 2. b的值是按列取的,增加了cpu缓存我们都知道顺序读取内存是最有效的。

我认为,也许数据不是那么强大,您可以采取一些技巧,在累加时不要采用模数(假设总和永远不会溢出),最后采用模数,这样模运算将为O (n ^3),还原为O(n ^2)。

结果为WA,即数据累积超过无符号long long的最大范围(2 ^ 64-1,大约18 * 10 ^ 18),代码如下:

void  mat_mul( int (*a)[MAXN], int (*b)[MAXN], int (*c)[MAXN], int n ) {
        int  i, j, k;
        ULL  sum;
        for( i = 0; i < n; ++i ) {
                for( j = 0; j < n; ++j ) {
                        sum = 0;
                        for( k = 0; k < n; ++k ) sum += (ULL)a[i][k] * (ULL)b[k][j];
                        c[i][j] = sum % P;
                }
        }
}

接下来,我做了更多尝试,包括:1在输出部分之前有一个if判断,并且打开了分支; 2我试图用long long代替unsigned long long; 3我将代码与顶级网民(比我快100毫秒)进行了比较,只是暂时发现他使用很长的时间来存储矩阵。

结果,时间没有改变,甚至3点也使我的记忆力加倍。我想哭。这都是三个循环。为什么生活差异如此之大?

所以我仔细研究了风店网民的密码,为什么它比我快,最后让我发现他的循环顺序与我的不同。

根据修改,我得到了一个828ms的代码:

void  mat_mul( int (*a)[MAXN], int (*b)[MAXN], int (*c)[MAXN], int n ) {
        int  i, j, k, *p1, *p2, *end;
        ULL  tmp;
        memset( c, 0, sizeof( A[0] ) );
        for( i = 0; i < n; ++i ) {
                for( k = 0; k < n; ++k ) {
                        tmp = a[i][k];
                        for( p1 = c[i], p2 = b[k], end = p1 + n; p1 != end; ++p1, ++p2 )
                                *p1 = ( *p1 + tmp * (*p2) ) % P;  // c[i][j] = ( c[i][j] + a[i][k] * b[k][j] ) % P;
                }
        }
}

此代码将k循环移到中间,最内层变成j循环(我用指针重写了它,其含义是带注释的句子,其效率不应低于二维的效率参考,这有待确定)。

此代码的重要性在于:在最内部的循环中,对c和b的访问是顺序的,并且在此循环中a [i] [k]不变,这可以更好地利用cpu缓存。矩阵越大,加速效果越明显。

这个想法也应该在未来的实际项目中使用。

最后一件事是优化模量。由于所有的累积都不够,因此我将进行部分累积,然后取一次模。最终将减少最耗时的模数运算。

分析数据并假定a和b矩阵的数据接近最大可能值(对于P模,最大值为P-1,并且P的值约为10 ^9),然后第一个乘积是10 ^ 18,然后一个无符号的long long可以容纳大约18个累加。我取了16个,每个累加是16次(一方面,16是因为它已经接近18了,另一方面,位运算可以很好地使用),取一个模数,这样取模的次数大约是原始取模数的1/16。当然,判断次数为16增加了一个分支,但是相对于模数的这种优化可以几乎被忽略了,耗时484ms,代码如下(有点难看):

void  mat_mul( int  (*a)[MAXN], int (*b)[MAXN], int  (*c)[MAXN], int n ) {
        int  i, j, k, L, *p2;
        ULL  tmp[MAXN], con;
        //memset( c, 0, sizeof( A[0] ) );
        for( i = 0; i < n; ++i ) {
                memset( tmp, 0, sizeof( tmp ) );
                for( k = 0, L = (n & ~15); k < L; ++k ) {
                        con = a[i][k];
                        for( j = 0, p2 = b[k]; j < n; ++j, ++p2 )
                                tmp[j] += con * (*p2);
                        if( ( k & 15 ) == 15 ) {
                                for( j = 0; j < n; ++j ) tmp[j] %= P;
                        }
                }
                
                for( ; k < n; ++k ) {
                        con = a[i][k];
                        for( j = 0, p2 = b[k]; j < n; ++j, ++p2 )
                                tmp[j] += con * (*p2);
                }
                 for( j = 0; j < n; ++j )
                        c[i][j] = tmp[j] % P;
        }
}

代码变长了,L是16的整数倍,下面的循环只处理不到16个。使用tmp数组进行优化(根据我的理解,堆栈变量的访问速度将比全局变量快) )。

当然,这个问题也可以针对IO进行优化,因为输入和输出量很大,但是由此带来的速度提高意义不大,因此未进行修改。

我以为我不需要写它,但是我刚才做了优化,它达到了265ms。在这种情况下,让我们再写一次。 。

代码如下:

void  mat_mul( int  (*a)[MAXN], int (*b)[MAXN], int  (*c)[MAXN], int n ) {
        int  i, j, k, L, *p2;
        ULL  tmp[MAXN], con;
        //memset( c, 0, sizeof( A[0] ) );
        for( i = 0; i < n; ++i ) {
                memset( tmp, 0, sizeof( tmp ) );
                for( k = 0, L = (n & ~15); k < L; ) {
#define  OP  do { for( con = a[i][k], p2 = b[k], j = 0; j < n; ++j, ++p2 ) \
						tmp[j] += con * (*p2); \
					++k; } while(0)
                        OP; OP; OP; OP;
                        OP; OP; OP; OP;
                        OP; OP; OP; OP;
                        OP; OP; OP; OP;
                        
                        for( j = 0; j < n; ++j ) tmp[j] %= P;
                }
                
                for( ; k < n; ) {
                        OP;
                }
                 for( j = 0; j < n; ++j )
                        c[i][j] = tmp[j] % P;
        }
}

此代码等效于删除分支预测并手动展开16个操作,但效果非常明显。

未经允许不得转载:狠人SEO » seo具体怎么优化矩阵系统蜘蛛屯 矩阵乘法的优化

本文链接: http://www.henrenseo.com/seowt/14345.html

版权声明:本文著作权归原作者狠人SEO所有,转载请注明出处,感谢!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

狠人SEO-网站优化排名操作步骤分享

联系我们联系我们

友情链接


#