我试着用Strassen的算法来写矩阵乘法的代码，代码可以用，但是当我试着用随机生成的平方矩阵与天真的算法(n^3)比较结果时。代码可以工作，但当我试图用随机生成的平方矩阵与天真的算法(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);
}
}
我已经尝试过删除多余的定义，这些定义在没有使用的情况下会被覆盖。
你所遇到的内存泄漏的直接原因是你没有通过子操作释放分配的内存，例如在那一行。
int** p1 = MatrixMultiply(q1_1, SubtractMatrix(q2_2, q2_4, l2), l2);
例如在那行： SubtractMatrix 将为结果分配内存，但你并没有保留指向该矩阵的指针，也没有办法调用删除该内存。也就是说，我认为你会从阅读以下内容中受益匪浅。 善本，并熟悉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;
}
在你的 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) 或 AddMatrix(q2_3, q2_4, l2), l2). 但这些临时输入矩阵是不会被删除的。你应该把它们也删除。