Как ускорить операции с разреженной матрицей? ⇐ C++

[Anonymous]

Разреженная матрица — это матрицы, в которых подавляющее большинство элементов имеют значения 0 и лишь несколько ненулевых элементов. Теперь мне нужно заполнить свой класс Sparsematrix так, чтобы матрицы могли складывать ,subtract и умножить.
Я использую COO для хранения своей матрицы.
template
class VecList{
private:
int capacity;
int length;
T* arr;
void doubleListSize(){
T * oldArr = arr;
arr = new T[2*capacity];
capacity = 2 * capacity;
for(int i=0;igetLength() - 1 - i) == a && colIndex->getEleAtPos(colIndex->getLength()-1-i) == b)return rowIndex->getLength()-1 - i;
}
return -1;
}
void setEntry(int rPos, int cPos, T x){ // Set (rPos, cPos) = x
int pos = findPos(rPos,cPos);
//Find if there is a non-zero element at (rPos, cPos).
if(x != 0){
//If the origin matrix does not have an element at(rPos, cPos),insert x to the matrix.
if (pos == -1)
{
rowIndex->insertEleAtPos(rowIndex->getLength(),rPos);
colIndex->insertEleAtPos(colIndex->getLength(),cPos);
values->insertEleAtPos(values->getLength(),x);
}
else{
//If the origin matrix has an element at(rPos, cPos),replace it with x.
rowIndex->setEleAtPos(pos,rPos);
colIndex->setEleAtPos(pos,cPos);
values->setEleAtPos(pos,x);
}
}
else{
//If x == 0 and the origin matrix has an element at(rPos, cPos), delete the element.
if(pos != -1){
rowIndex->deleteEleAtPos(pos);
colIndex->deleteEleAtPos(pos);
values->deleteEleAtPos(pos);
}
}
//If x == 0, and the origin matrix does not have an element at(rPos, cPos), nothing changed.
}
T getEntry(int rPos, int cPos){
//Get the element at (rPos, cPos)
return findPos(rPos,cPos) == -1 ? 0 : values->getEleAtPos(findPos(rPos,cPos));
}
SparseMatrix * add(SparseMatrix * B){
if(rows != B->rows || cols != B->cols)throw "Matrices have incompatible sizes";
SparseMatrix *C = new SparseMatrix(rows,cols);//Create a new matrix C as result.
for (int i = 0; i < rowIndex->getLength(); i++)
{
//I call the two input matrices "A" and "B". I put every elements of A into C, and also put every elements of B into C. But I use "C->setEntry", which means when A[j] has an element and B[j] also has an element, "setEntry" will cover the prior one. So I use C->setEntry(i,j,C->getEntry(i,j) + A[j] or B[j]), in another word, setEntry with (oldvalue + newvalue).That's what I did.
C->setEntry(rowIndex->getEleAtPos(i),colIndex->getEleAtPos(i),C->getEntry(rowIndex->getEleAtPos(i),colIndex->getEleAtPos(i))+values->getEleAtPos(i));
C->setEntry(B->rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(i),C->getEntry(B->rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(i))+B->values->getEleAtPos(i));
}
return C;
}
SparseMatrix * subtract(SparseMatrix * B){
//The same method as add.
if(rows != B->rows || cols != B->cols)throw "Matrices have incompatible sizes";
SparseMatrix *C = new SparseMatrix(rows,cols);
for (int i = 0; i < rowIndex->getLength(); i++)
{
C->setEntry(rowIndex->getEleAtPos(i),colIndex->getEleAtPos(i),C->getEntry(rowIndex->getEleAtPos(i),colIndex->getEleAtPos(i))-values->getEleAtPos(i));
C->setEntry(B->rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(i),C->getEntry(B->rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(i))-B->values->getEleAtPos(i));
}
return C;
}

SparseMatrix * multiply(SparseMatrix * B){
//perform multiplication if the sizes of the matrices are compatible.
if(rows != B->cols || cols != B->rows)throw "Matrices have incompatible sizes";
SparseMatrix *C = new SparseMatrix(rows,B->cols);
//I call the two input matrices as "A" and "B".
//My method is take a row of A first, let this row do the arithmetic with each column of B，then I finish a row in C. Then continue to the next row.
for (int i = 0; i < rowIndex->getLength();i++)
{
for (int j = 0; j < B->colIndex->getLength(); j++)
{
if (B->findPos(colIndex->getEleAtPos(i),B->colIndex->getEleAtPos(j)) != -1)
{
C->setEntry(rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(j),C->getEntry(rowIndex->getEleAtPos(i),B->colIndex->getEleAtPos(j))+(values->getEleAtPos(i)*B->values->getEleAtPos(j)));
}
}
}
return C;
}

void printMatrix(){
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
cout

Подробнее здесь: https://stackoverflow.com/questions/790 ... ons-faster