0

我尝试使用 Strassen 算法编写矩阵乘法代码。该代码有效，但是当我尝试使用随机生成的方阵将结果与简单算法（n^3）进行比较时。编译时没有警告，但程序使用的内存以某种方式不断增加。我对 C++ 相当陌生，指针对我来说是一个全新的概念。即使经过故障排除，我也找不到内存泄漏。很抱歉发布整个代码。

#include <iostream>
#include <time.h>
#include <string>

int** MakeMatrix(int size);

bool CheckMatrixEquality(int** a, int** b, int size)
{
    bool isEqual = true;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (a[i][j] != b[i][j])
                isEqual = false;
        }
    }
    return isEqual;
}

int** MatrixMultiplicationNaive(int** a, int** b, int size)
{
    int** res = MakeMatrix(size);
    int temp = 0;
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            for (int k = 0; k < size; k++)
            {
                temp += a[i][k] * b[k][j];
            }
            res[i][j] = temp;
            temp = 0;
        }
    }
    return res;
}

void PrintMatrix(int** mat, int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            std::cout << mat[i][j] << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";

}

void DeleteMatrix(int** del, int size)
{
    for (int i = 0; i < size; i++)
    {
        delete[] del[i];
    }
    delete[] del;
}

int** MakeMatrix(int size)
{
    int** mat = new int* [size];
    for (int i = 0; i < size; i++)
    {
        mat[i] = new int[size] { 0 };
    }
    return mat;
}

int** AddMatrix(int** a, int** b, int size)
{
    int** add = MakeMatrix(size);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            add[i][j] = a[i][j] + b[i][j];
        }
    }
    return add;
}

int** SubtractMatrix(int** a, int** b, int size)
{
    int** sub = MakeMatrix(size);
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            sub[i][j] = a[i][j] - b[i][j];
        }
    }
    return sub;
}

int** MatrixMultiply(int** a, int** b , int size)
{
    //base case return
    if (size == 1)
    {
        int** p = MakeMatrix(size);
        p[0][0] = a[0][0] * b[0][0];
        return p;
    }
    int l1 = size / 2;
    int l2 = size - l1;

    //defining new matrices for fragmentation of matrix1
    int** q1_1 = MakeMatrix(l2);

    int** q1_2 = MakeMatrix(l2);

    int** q1_3 = MakeMatrix(l2);

    int** q1_4 = MakeMatrix(l2);

    //defining new matrices for fragmentation of matrix2
    int** q2_1 = MakeMatrix(l2);

    int** q2_2 = MakeMatrix(l2);

    int** q2_3 = MakeMatrix(l2);

    int** q2_4 = MakeMatrix(l2);

    //adding values into smaller matrices from matrix 1 and 2
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i < l1 and j < l1)
            {
                q1_1[i][j] = a[i][j];
                q2_1[i][j] = b[i][j];
            }
            else if (i < l1 and j >= l1)
            {
                q1_2[i][j - l1] = a[i][j];
                q2_2[i][j - l1] = b[i][j];
            }
            else if (i >= l1 and j < l1)
            {
                q1_3[i - l1][j] = a[i][j];
                q2_3[i - l1][j] = b[i][j];
            }
            else if(i >= l1 and j >= l1)
            {
                q1_4[i - l1][j - l1] = a[i][j];
                q2_4[i - l1][j - l1] = b[i][j];
            }
        }
    }

    //multiplications required for strassens algo
    int** p1 = MatrixMultiply(q1_1, SubtractMatrix(q2_2, q2_4, l2), l2);
    int** p2 = MatrixMultiply(AddMatrix(q1_1, q1_2, l2), q2_4, l2);
    int** p3 = MatrixMultiply(AddMatrix(q1_3, q1_4, l2), q2_1, l2);
    int** p4 = MatrixMultiply(q1_4, SubtractMatrix(q2_3, q2_1, l2), l2);
    int** p5 = MatrixMultiply(AddMatrix(q1_1, q1_4, l2), AddMatrix(q2_1, q2_4, l2), l2);
    int** p6 = MatrixMultiply(SubtractMatrix(q1_2, q1_4, l2), AddMatrix(q2_3, q2_4, l2), l2);
    int** p7 = MatrixMultiply(SubtractMatrix(q1_1, q1_3, l2), AddMatrix(q2_1, q2_2, l2), l2);

    //further calculations using p's
    int** q3_1 = SubtractMatrix(AddMatrix(p5, p4, l2), SubtractMatrix(p2, p6, l2), l2);
    int** q3_2 = AddMatrix(p1, p2, l2);
    int** q3_3 = AddMatrix(p3, p4, l2);
    int** q3_4 = SubtractMatrix(AddMatrix(p1, p5, l2), AddMatrix(p3, p7, l2), l2);

    //compiling results
    int** Narr = MakeMatrix(size);

    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i < l1 and j < l1)
            {
                Narr[i][j] = q3_1[i][j];
            }
            else if (i < l1 and j >= l1)
            {
                Narr[i][j] = q3_2[i][j - l1];
            }
            else if (i >= l1 and j < l1)
            {
                Narr[i][j] = q3_3[i - l1][j];
            }
            else if (i >= l1 and j >= l1)
            {
                Narr[i][j] = q3_4[i - l1][j - l1];
            }
        }
    }

    //deleting heap allocated pointers, help!!!
    DeleteMatrix(q1_1, l2);
    DeleteMatrix(q1_2, l2);
    DeleteMatrix(q1_3, l2);
    DeleteMatrix(q1_4, l2);
    DeleteMatrix(q2_1, l2);
    DeleteMatrix(q2_2, l2);
    DeleteMatrix(q2_3, l2);
    DeleteMatrix(q2_4, l2);
    DeleteMatrix(q3_1, l2);
    DeleteMatrix(q3_2, l2);
    DeleteMatrix(q3_3, l2);
    DeleteMatrix(q3_4, l2);
    DeleteMatrix(p1, l2);
    DeleteMatrix(p2, l2);
    DeleteMatrix(p3, l2);
    DeleteMatrix(p4, l2);
    DeleteMatrix(p5, l2);
    DeleteMatrix(p6, l2);
    DeleteMatrix(p7, l2);

    return Narr;
}

int main()
{
    while (true)
    {
        int size = 10;

        srand(time(NULL));

        int** a = MakeMatrix(size);
        int** b = MakeMatrix(size);
        for (int i = 0; i < size; i++)
        {
            for (int j = 0; j < size; j++)
            {
                a[i][j] = rand() % 100;
                b[i][j] = rand() % 100;
            }
        }

        int** resultFast = MatrixMultiply(a, b, size);
        int** resultNaive = MatrixMultiplicationNaive(a, b, size);

        if (CheckMatrixEquality(resultFast, resultNaive, size))
        {
            std::cout << "okie\n";
        }
        else
        {
            PrintMatrix(resultFast, size);
            PrintMatrix(resultNaive, size);
            break;
        }

        DeleteMatrix(a, size);
        DeleteMatrix(b, size);
        DeleteMatrix(resultFast, size);
        DeleteMatrix(resultNaive, size);
    }
}

我已经尝试删除那些在没有被使用的情况下被覆盖的冗余定义。

4

2 回答 2

0

您遇到内存泄漏的直接原因是您没有通过子操作释放分配的内存，例如在该行中：

int** p1 = MatrixMultiply(q1_1, SubtractMatrix(q2_2, q2_4, l2), l2);

函数SubtractMatrix将为结果分配内存，但您没有保留指向该矩阵的指针，也无法在该内存上调用 delete。
话虽如此，我认为您将从阅读 一本好的 c++ 书籍并熟悉 RAII 习语中受益匪浅。std::vector是一个容器，它（除其他外）为动态大小的数组实现了该习惯用法，并且将所有函数更改为返回向量的向量将解决您的内存泄漏问题（并使该问题DeleteMatrixFunction过时），例如您可以编写SubtractMatrix函数这边走：

using MyMatrix = std::vector<std::vector<int>>;
// Creates a size x size matrix with 0 at each position.
MyMatrix MakeMatrix(std::size_t size) {
  MyMatrix result;
  result.reserve(size);
  for (auto i = 0u; i < size; ++i)
    // std::vector<int>(size, 0) creates a vector of length n with each element initalized to 0.
    result.push_back(std::vector<int>(size, 0));
  return result;
}

MyMatrix SubtractMatrix(const MyMatrix& a, const MyMatrix b)
{
    MyMatrix result = MakeMatrix(a.size());
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            result[i][j] = a[i][j] - b[i][j];
        }
    }
    return sub;
}
于 2020-05-25T18:03:08.677 回答
0

在你的MatrixMultiply方法中，你有一些这样的行：

   int** p5 = MatrixMultiply(AddMatrix(q1_1, q1_4, l2), AddMatrix(q2_1, q2_4, l2), l2);
   int** p6 = MatrixMultiply(SubtractMatrix(q1_2, q1_4, l2), AddMatrix(q2_3, q2_4, l2), l2);
   int** p7 = MatrixMultiply(SubtractMatrix(q1_1, q1_3, l2), AddMatrix(q2_1, q2_2, l2), l2);

问题是这些函数（即 MatrixMultiply）的输入参数是一些函数调用的输出，比如SubtractMatrix(q1_1, q1_3, l2)or AddMatrix(q2_3, q2_4, l2), l2)。但是这些临时输入矩阵永远不会被删除。您也应该删除它们。

于 2020-05-25T18:06:24.567 回答