我正在开发一个小型项目,在其中实现矩阵链乘法。我的实现是构建一棵树,其中节点定义为
struct Node
{
char* seq;
Node* left;
Node* right;
};
其中 seq 是数字序列,指示要计算的矩阵链。另一部分是有一个称为矩阵的结构,定义为
struct matrix
{
std::tuple<int, int> dimension;
std::vector<std::vector<int>> values;
};
我使用 2D 向量来存储值。
总体思路是我将创建一个字典,其中的 {"char" : 矩阵},其中 char 是一个数值,并将该字典存储到一个类中。
以下代码片段展示了我如何创建矩阵
matrix *A1 = new matrix;
matrix *A2 = new matrix;
A1->dimension = std::make_tuple(4,10);
A2->dimension = std::make_tuple(10,3);
setValues(A1, 1);
setValues(A2, 2);
Node *n = new Node;
n->left = nullptr;
n->right = nullptr;
n->seq = static_cast<char*>(malloc(3 * sizeof(char)));
n->seq[0] = '0' + 1;
n->seq[1] = '0' + 2;
n->seq[2] = '\0';
其中 setValue 定义为
void setValues(matrix *x,int value)
{
int row = std::get<0>(x->dimension);
int col = std::get<1>(x->dimension);
x->values.resize(row);
for (int i = 0; i < row; ++i)
{
x->values[i].resize(col);
}
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
x->values[i][j] = value;
}
}
}
然后我创建了
std::unordered_map<char, matrix*> dict;
dict['1'] = A1;
dict['2'] = A2;
在此之后,我调用类 Sequence 的构造函数,其定义为
class Sequence
{
private:
Node root;
std::vector<std::vector<int>> s_table;
std::unordered_map<char,matrix*> str_matrix_dict;
public:
Sequence(std::vector<std::vector<int>> temp_table, std::unordered_map<char,matrix*> &str_matrix_dict);
matrix* compute(Node* n);
}
构造函数定义为
Sequence::Sequence(
std::vector<std::vector<int>> temp_table,
std::unordered_map<char,matrix*> &temp_dict) : s_table(temp_table), str_matrix_dict(temp_dict)
{
并像
那样调用构造函数 Sequence seq(s_table, dict);
其中 s_table 是一个二维向量。我的问题出在名为compute(Node* n) 的类函数之一内,并定义如下
matrix* Sequence::compute(Node* n)
{
/*
code before
*/
if(n->left == nullptr && n->right == nullptr && n->seq[2] == '\0')
{
matrix* matrix_A = str_matrix_dict[n->seq[0]];
matrix* matrix_B = str_matrix_dict[n->seq[1]];
matrix* matrix_C = new matrix;
int m = std::get<0>(matrix_A->dimension);
int n = std::get<1>(matrix_B->dimension);
int z = std::get<1>(matrix_A->dimension);
matrix_C->dimension = std::make_tuple(m,n);
matrix_C->values.resize(m);
for (int i = 0; i < m; ++i)
{
matrix_C->values[i].resize(n);
}
matrix_mult(matrix_A,matrix_B,matrix_C,m,n,x);
return matrix_C;
}
matrix* left_res = compute(n->left);
matrix* right_res = compute(n->right);
//code after (same computation as above)
这个想法是递归地遍历二叉树并计算节点矩阵的每一侧并将其返回到父节点进行计算。
我在matrix_mult中遇到段错误,其定义为
void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
for(int col = 0; row < y; y++)
{
for(int k = 0; k < z; k++)
{
c->values[row][col] += (a->values[row][k] * b->values[k][col]);
}
}
}
}
我在三重 for 循环的第一遍出现了段错误。在“计算”内部,当我尝试打印出矩阵的值时,我没有得到任何值。我猜这与我如何通过引用传递和取消引用有关,但并不完全确定。我使用指针的原因是我听说通过引用传递矩阵是一种很好的做法,因为它可以节省空间和时间,而不是通过值传递,尤其是在处理非常大的矩阵时。我认为将矩阵存储在字典中然后将字典存储在类私有变量中以在函数计算(这是一个类函数)中访问是很简单的。感谢您的任何建议/指导。
这也是我的编译器。我使用 nvcc 作为这个迷你项目的一部分,以合并 GPU 计算。
CXX = nvcc
CPP = gcc
CFLAGS = -std=c++11 -g
LDFLAGS = -lcudart -lcudadevrt
main: main.o sequence.o
$(CXX) $(CFLAGS) -o main main.o sequence.o $(LDFLAGS)
main.o: main.cu
$(CXX) $(CFLAGS) -c main.cu
sequence.o: sequence.cpp
$(CXX) $(CFLAGS) -c sequence.cpp
clean:
rm -f main main.o sequence.o
您提供代码的方式使得很难查明问题,但matrix_mult函数显然存在一些潜在的问题:
void Sequence::matrix_mult(matrix *a, matrix *b, matrix *c, int x, int y, int z)
{
std::cout << "calculating " << std::endl;
for(int row = 0; row < x; x++)
{
for(int col = 0; row < y; y++)
{
for(int k = 0; k < z; k++)
{
c->values[row][col] += (a->values[row][k] * b->values[k][col]);
}
}
}
在第一个循环中,您检查 row 小于 x,然后递增 x 而不是 row。如果 x 的初始值 >= 0,这将导致无限循环
同样的问题也适用于第二个循环,即迭代 y 的循环。
最后,这只是一个观察结果,该函数中只有一个可能的段错误原因,那就是对越界矩阵索引的访问。由于 row 和 col 始终为 0,我猜测在某些时候您正在使用超出范围的 k 访问
a->values[0][k]
或 b->values[k][0]
。
如果您使用 gcc 和标志
-fsanitize=address -g3
编译代码,您可以获得有关段错误原因的详细信息。您可以在这里找到更多信息
https://www.cse.unsw.edu.au/%7Elearn/debugging/modules/asan/