算法导论 - 一个递归调用的c++程序,指针传参, delete回收放在下一层递归,为什么没有被释放资源?
PHPz
PHPz 2017-04-17 15:05:32
0
1
596

是Strassen矩阵相乘的算法, 这里有一篇介绍博客: 矩阵乘法Strassen算法,因为太占内存了,想尽可能快地回收内存:

void Strassen(int **A, int **B, int **C, int N, bool delA, bool delB)
    {
        int i, j;
        if (N <= 256 || N % 2 == 1)
        {
            matrixMul(A, B, C, N);
            return;
        }
        int newn = N / 2;
        int ** A11, **A12, **A21, **B11, **B12, **B21;
        int **A22;
        int **B22;
        /*
        int **C11, **C12, **C21, **C22;
        */

        int **P1, **P2, **P3, **P4, **P5, **P7;
        // int **temp1, **temp2, **P6;

        // 申请空间
        A11 = new int *[newn];
        A12 = new int *[newn];
        A21 = new int *[newn];
        A22 = new int *[newn];

        B11 = new int *[newn];
        B12 = new int *[newn];
        B21 = new int *[newn];
        B22 = new int *[newn];

        /*
        C11 = new int *[newn];
        C12 = new int *[newn];
        C21 = new int *[newn];
        C22 = new int *[newn];
        */
        P1 = new int *[newn];
        P2 = new int *[newn];
        P3 = new int *[newn];
        P4 = new int *[newn];
        P5 = new int *[newn];

        P7 = new int *[newn];

        //P6 = new int *[newn];
        /*
        temp1 = new int *[newn];
        temp2 = new int *[newn];
        */

        for (i = 0; i < newn; i++)
        {
            A11[i] = new int[newn];
            A12[i] = new int[newn];
            A21[i] = new int[newn];
            A22[i] = new int[newn];

            B11[i] = new int[newn];
            B12[i] = new int[newn];
            B21[i] = new int[newn];
            B22[i] = new int[newn];

            /*
            C11[i] = new int[newn];
            C12[i] = new int[newn];
            C21[i] = new int[newn];
            C22[i] = new int[newn];
            */
            P1[i] = new int[newn];
            P2[i] = new int[newn];
            P3[i] = new int[newn];
            P4[i] = new int[newn];
            P5[i] = new int[newn];

            P7[i] = new int[newn];

            //P6[i] = new int[newn];
            /*
            temp1[i] = new int[newn];
            temp2[i] = new int[newn];
            */
        }

        // 切分矩阵A、B
        for (i = 0; i < newn; i++)
        {
            for (j = 0; j < newn; j++)
            {
                A11[i][j] = A[i][j];
                A12[i][j] = A[i][j + newn];
                A21[i][j] = A[i + newn][j];
                A22[i][j] = A[i + newn][j + newn];

                B11[i][j] = B[i][j];
                B12[i][j] = B[i][j + newn];
                B21[i][j] = B[i + newn][j];
                B22[i][j] = B[i + newn][j + newn];
            }
        }
        /*
        下面删除已经没有价值的矩阵
        */
        
        if (delA)
        {
            for (i = 0; i < N; i++)
            {
                delete[] A[i];
            }
            delete[] A;
            A = NULL;
        }
        if (delB)
        {
            for (i = 0; i < N; i++)
            {
                delete[] B[i];
            }
            delete[] B;
            B = NULL;
        }
        /*
        上面删除已经没有价值的矩阵
        */
        // S1 = B12 - B22
        // P1 = A11 ? S1
        // * P7 作为 temp
        matrixSub(B12, B22, P7, newn);
        Strassen(A11, P7, P1, newn, false, false);

        // S9 = A11 - A21
        // S10 = B11 + B12
        // P7 = S9 ? S10
        // * P2 P4 作为 temp
        matrixSub(A11, A21, P2, newn);
        matrixAdd(B11, B12, P4, newn);
        Strassen(P2, P4, P7, newn, false, false);
        // * B12 已利用完 可以作为 temp

        // S3 = A21 + A22
        // P3 = S3 ? B11
        matrixAdd(A21, A22, B12, newn);
        Strassen(B12, B11, P3, newn, true, false); //删了B12
        // * A21 已利用完 可以作为 temp

        // S5 = A11 + A22
        // S6 = B11 + B22
        // P5 = S5 ? S6
        // * P2作为 temp
        matrixAdd(A11, A22, A21, newn);
        matrixAdd(B11, B22, P2, newn);
        Strassen(A21, P2, P5, newn, true, false);//删了A21

        // C22 -> P7
        // C22 = P5 + P1 - P3 - P7
        matrixGetC22(P5, P1, P3, P7, P7, newn);
        // * P7 已经利用完,可作 C22 -> P7
        // * 当前可用作为temp的: B12(X),A21(X)

        // S2 = A11 + A12
        // P2 = S2 ? B22
        matrixAdd(A11, A12, A11, newn);
        Strassen(A11, B22, P2, newn, true, false);//删了A11
        // * A11 已被利用完, 可以作为 temp

        // C22 -> P7
        // C12 <- P1 = P1 + P2
        matrixAdd(P1, P2, P1, newn);
        // *P1 已被利用完,可 C12 <- P1 当前temp: A11,B12(X),A21(X)

        // S4 = B21 - B11
        // P4 = A22 ? S4
        matrixSub(B21, B11, B11, newn);
        Strassen(A22, B11, P4, newn, false, true); //删了B11
        // *B11 已被利用完,当前temp: B11(X),A11(X),B12(X),A21(X)

        // C22 -> P7
        // C12 <- P1 = P1 + P2
        // C21 <- P3 = P3 + P4
        matrixAdd(P3, P4, P3, newn);
        // *P3 已被利用完,可 C21 <- P3 当前temp: B11(X),A11(X),B12(X),A21(X)

        // S7 = A12 - A22
        // S8 = B21 + B22
        // P6 <- B22 = S7 ? S8
        matrixSub(A12, A22, A12, newn);
        matrixAdd(B21, B22, B21, newn);
        Strassen(A12, B21, B22, newn, true, true); //删了A12 B21
        // *当前temp: B11(X),A11(X),B12(X),A21(X),A12(X),B21(X)


        // C22 -> P7
        // C12 <- P1 = P1 + P2
        // C21 <- P3 = P3 + P4
        // C11 <- P5 = P5 + P4 - P2 + P6
        matrixGetC11(P5, P4, P2, B22, P5, newn);

        // 合并矩阵C
        for (i = 0; i < newn; i++)
        {
            for (j = 0; j < newn; j++)
            {
                C[i][j] = P5[i][j];
                C[i][j + newn] = P1[i][j];
                C[i + newn][j] = P3[i][j];
                C[i + newn][j + newn] = P7[i][j];
            }
        }
        // 释放内存
        for (i = 0; i < newn; i++)
        {
            /*
            delete[] A11[i];
            delete[] A12[i];
            delete[] A21[i];
            */
            delete[] A22[i];
            
            /*
            delete[] B11[i];
            delete[] B12[i];
            delete[] B21[i];
            */
            delete[] B22[i];

            /*
            delete[] C11[i];
            delete[] C12[i];
            delete[] C21[i];
            delete[] C22[i];
            */

            delete[] P1[i];
            delete[] P2[i];
            delete[] P3[i];
            delete[] P4[i];
            delete[] P5[i];

            delete[] P7[i];
            /*
            delete[] P6[i];
            delete[] temp1[i];
            delete[] temp2[i];
            */
        }
        /*
        delete[] A11;
        delete[] A12;
        delete[] A21;
        */
        delete[] A22;
        /*
        delete[] B11;
        delete[] B12;
        delete[] B21;
        */
        delete[] B22;
        /*
        delete[] C11;
        delete[] C12;
        delete[] C21;
        delete[] C22;
        */
        delete[] P1;
        delete[] P2;
        delete[] P3;
        delete[] P4;
        delete[] P5;

        delete[] P7;
        /*
        delete[] P6;
        delete[] temp1;
        delete[] temp2;*/
    }

省略了无关的代码,通过看任务管理,发现通过传给下一层递归的矩阵并没有成功被回收(和都放在递归调用后面删除的方法相比,占用内存多了,多了的部分是传给下一层递归的矩阵)
表达能力可能不好,先谢谢了

PHPz
PHPz

学习是最好的投资!

Antworte allen(1)
Ty80

delete表示的是这块内存我程序还可以继续用,你说的这个问题就是OS回收不回收的问题了

Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage