个人中心
gpt4 book ai didi

c - 如何提高此 Strassen 算法实现的速度？

转载 作者：塔克拉玛干 更新时间：2023-11-03 03:31:37 26 4
gpt4 key购买 nike

<分区>

我正在努力确定为什么我的 Strassen 实现如此缓慢。它会在每次迭代时分配内存，但我会酌情将其全部释放。

int** multiply(int** a, int** b, int size)
{
int row,col,i,j;

if(size == 1)
{
    int** c = allocate(size);
    c[0][0] = (a[0][0] * b[0][0])%2;
    return c;
}

if(size <= 2)
{
    int a11,a12,a21,a22,b11,b12,b21,b22;    
    int** c = allocate(size);
    a11 = a[0][0];
    a12 = a[0][1];
    a21 = a[1][0];
    a22 = a[1][1];
    b11 = b[0][0];
    b12 = b[0][1];
    b21 = b[1][0];
    b22 = b[1][1];

    c[0][0] = (a11*b11 + a12*b21)%2;
        c[0][1] = (a11*b12 + a12*b22)%2;
        c[1][0] = (a21*b11 + a22*b21)%2;
    c[1][1] = (a21*b12 + a22*b22)%2;
        return c;
}

int** c = allocate(size);
size = size/2;

int** A11 = allocate(size);
int** A12 = allocate(size);
int** A21 = allocate(size);
int** A22 = allocate(size);
int** B11 = allocate(size);
int** B12 = allocate(size);
int** B21 = allocate(size);
int** B22 = allocate(size);

for(i=0;i<size;i++)
{
    for(j=0;j<size;j++)
    {
        A11[i][j] = a[i][j];    
        A12[i][j] = a[i][j+size];
        A21[i][j] = a[i+size][j];
        A22[i][j] = a[i + size][j + size];
        B11[i][j] = b[i][j];
        B12[i][j] = b[i][j + size];
        B21[i][j] = b[i + size][j];
        B22[i][j] = b[i + size][j + size];
    }
}

int** S1 = subtract(B12,B22,size);
int** S2 = add(A11,A12, size);
int** S3 = add(A21,A22, size);
int** S4 = subtract(B21,B11, size);
int** S5 = add(A11,A22, size);
int** S6 = add(B11,B22, size);
int** S7 = subtract(A12,A22, size);
int** S8 = add(B21,B22, size);
int** S9 = subtract(A11,A21, size);
int** S10 = add(B11,B12, size);

int** P1 = multiply(A11, S1, size);
int** P2 = multiply(S2, B22, size);
int** P3 = multiply(S3, B11, size);
int** P4 = multiply(A22, S4, size);
int** P5 = multiply(S5, S6, size);
int** P6 = multiply(S7, S8, size);
int** P7 = multiply(S9, S10,size);

int** c11 = subtract(add(P5,P4,size), add(P2,P6,size), size);
int** c12 = add(P1,P2,size);
int** c21 = add(P3,P4,size);
int** c22 = subtract(add(P5,P1,size), subtract(P3,P7,size), size);

int** temp = add(P5,P4,size);
int** temp2 = add(P2,P6, size);

for(i=0; i< size; i++)
{
    for(j=0; j< size; j++)
    {
        c[i][j] = abs(c11[i][j] % 2);           
        c[i][j+size] = abs(c12[i][j] % 2);
        c[i+size][j] = abs(c21[i][j] % 2);
        c[i+size][j+size] = abs(c22[i][j] % 2);
    }
}

deallocate(A11, size);
deallocate(A12, size);
deallocate(A21, size);
deallocate(A22, size);
deallocate(B11, size);
deallocate(B12, size);
deallocate(B21, size);
deallocate(B22, size);
deallocate(c11, size);
deallocate(c12, size);
deallocate(c21, size);
deallocate(c22, size);
deallocate(P1, size);
deallocate(P2, size);
deallocate(P3, size);
deallocate(P4, size);
deallocate(P5, size);
deallocate(P6, size);
deallocate(P7, size);
deallocate(S1, size);
deallocate(S2, size);
deallocate(S3, size);
deallocate(S4, size);
deallocate(S5, size);
deallocate(S6, size);
deallocate(S7, size);
deallocate(S8, size);
deallocate(S9, size);
deallocate(S10, size);
deallocate(temp, size);
deallocate(temp2, size);
return c;
}

26 4 0
文章推荐： algorithm - 修改二进制搜索以查找下一个比键更大的项目
文章推荐： java - Sonar :sonar work?如何
文章推荐： java - 如何让 chromedriver 检测不到
文章推荐： java - 在 Java 语言的许多元素的集合中找到最小的 e1-e2
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com