Otimizando o algoritmo de multiplicação da matriz
Implementei minha própria versão de algoritmo para multiplicar duas matrizes e preciso de alguém que saiba o que está fazendo para ver se há algo que pode ser feito de maneira mais otimizada. Também estou interessado em entender como posso torná-lo robusto de forma que não trave quando matrizes não retangulares são passadas como argumento, ou seja, uma matriz que possui um número ímpar de elementos em diferentes Vds que contém.
Estou particularmente interessado na função matrixDotdo código abaixo, todo o resto é apenas para mostrar como estou usando no meu projeto).
#include "iostream"
#include <vector>
#define LOG(m) std::cout << m << std::endl
struct Vd
{
std::vector<double> v;
};
struct Md
{
std::vector<Vd> m;
//fill matrix with num
void fill(unsigned const int rows, unsigned const int cols, const double num)
{
m.clear();
for (unsigned int i = 0; i < rows; i++)
{
Vd tempVec;
for (unsigned int j = 0; j < cols; j++)
{
tempVec.v.push_back(num);
}
m.push_back(tempVec);
}
}
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[" << std::endl << std::endl;
for (unsigned int i = 0; i < mat.m.size(); i++)
{
out << "[";
for (unsigned int j = 0; j < mat.m[i].v.size(); j++)
{
if (j % mat.m[i].v.size() == mat.m[i].v.size() - 1)
out << mat.m[i].v[j] << "]" << std::endl << std::endl;
else
out << mat.m[i].v[j] << ", ";
}
}
out << "]" << std::endl;
return out;
}
};
inline void matrixDot(const Md& m1, const Md& m2, Md& outm)
{
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
unsigned int m1x = 0; unsigned int m1y = 0; unsigned int m2y = 0; //m2x = m1y
while (outm.m.size() < m1.m.size())
{
Vd tempv;
while (tempv.v.size() < m2.m[0].v.size())
{
double total = 0.0;
while (m1x < m1.m[0].v.size())
{
total += m1.m[m1y].v[m1x] * m2.m[m1x].v[m2y];
m1x++;
}
tempv.v.push_back(total);
m1x = 0;
m2y < m2.m[0].v.size() - 1 ? m2y++ : m2y = 0;
}
m1y < m1.m.size() - 1 ? m1y++ : m1y = 0;
outm.m.push_back(tempv);
}
}
int main()
{
Md mat1;
mat1.fill(5, 2, 1.0);
Md mat2;
mat2.fill(2, 6, 2.0);
Md mat3;
matrixDot(mat1, mat2, mat3);
std::cout << mat3;
}
Respostas
Eu vejo algumas coisas que você pode querer usar para melhorar seu código.
Use usingquando apropriado
O código atualmente contém isto:
struct Vd
{
std::vector<double> v;
};
Isso provavelmente é melhor expresso assim:
using Vd = std::vector<double>;
Então agora, em vez de escrever isto:
out << mat.m[i].v[j] << ", ";
Podemos usar esta sintaxe mais limpa:
out << mat.m[i][j] << ", ";
Entenda os caminhos de inclusão de cabeçalho
Há uma diferença sutil entre #include "iostream"e #include <iostream>. Embora seja uma implementação definida, a maioria das implementações do compilador é que a forma de aspas pesquisa primeiro localmente (por exemplo, o diretório atual) e, em seguida, pesquisa os diretórios de inclusão do sistema se isso falhar. O formulário de colchetes angulares geralmente pesquisa em diretórios de inclusão do sistema. Veja esta pergunta para mais. Por esse motivo, este código provavelmente deve ser usado #include <iostream>.
Não use std::endlse você realmente não precisar
A diferença entre std::endle '\n'é que '\n'apenas emite um caractere de nova linha, enquanto std::endlrealmente libera o fluxo. Isso pode ser demorado em um programa com muito I / O e raramente é realmente necessário. É melhor usá- lo apenasstd::endl quando você tiver um bom motivo para liberar o fluxo e não for necessário com frequência para programas simples como este. Evitar o hábito de usar o std::endlquando '\n'fará vai render dividendos no futuro, conforme você escreve programas mais complexos com mais E / S e onde o desempenho precisa ser maximizado.
Use funções padrão quando apropriado
Em vez de escrever ostream& operator<<como você fez, uma alternativa interessante seria usar std::copye std::experimental::ostream_joinerassim:
friend std::ostream& operator << (std::ostream& out, const Md& mat)
{
out << "[\n";
for (const auto& row : mat.m) {
out << "\t[";
std::copy(row.begin(), row.end(), std::experimental::make_ostream_joiner(out, ", "));
out << "]\n";
}
return out << "]\n";
}
Prefira valores de retorno para parâmetros de saída
Parece muito mais lógico matrixDotretornar uma nova matriz, em vez de usar o terceiro parâmetro como um parâmetro de saída. Veja F.20 para mais detalhes.
Considere uma representação alternativa
Este código é um tanto frágil porque Mde Vdsão implementados como struct, com todos os membros públicos. Pior, poderíamos ter uma matriz irregular em que cada linha não tivesse o mesmo número de itens. Isso provavelmente não vai resultar em nada de bom. Por ambas as razões, sugiro usar um classe um vectorpara conter todos os itens. Veja esta pergunta para algumas idéias e conselhos sobre como fazer isso. Você também pode olhar std::valarraycomo um tipo subjacente.
Fornece uma implementação de classe completa
Além de um construtor receber std::initializer_listargumentos, também sugiro alguns dos outros operadores, como operator==para esta classe.
Tenho que admitir que estou um pouco confuso, você fez as partes difíceis e tem uma pergunta sobre as partes fáceis? Posso estar interpretando mal sua pergunta.
Também estou interessado em entender como posso torná-lo robusto de modo que não trave quando matrizes não retangulares são passadas como argumento, ou seja, uma matriz que possui um número ímpar de elementos em diferentes Vds que contém.
Você pode validar que tem uma matriz bem formada por
inline bool isValid(const Md& mat)
{
if (mat.m.size())
{
int size = mat.m[0].v.size();
for (int i = 1; i < mat.m.size(); i++) {
if (size != mat.m[i].v.size())
{
return false;
}
}
}
return true;
}
e incorporá-lo à matrixDotfunção de validação semelhante à validação de forma que você tem agora
if (m1.m[0].v.size() && m2.m.size())
if (m1.m[0].v.size() != m2.m.size())
{
LOG("Shape mismatch: " << "matrix1 columns: " << m1.m[0].v.size() << ", " << "matrix2 rows: " << m2.m.size());
throw std::exception();
}
if (!isValid(m1))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m1;
throw std::exception();
}
if (!isValid(m2))
{
LOG("Invalid matrix :: " << std::endl);
std::cout << m2;
throw std::exception();
}
Quaisquer otimizações que eu possa pensar são em torno da utilização em std::arrayvez de std::vectorcomo você conhece os comprimentos de linha e coluna no momento da criação.
Pessoalmente, eu estenderia a estrutura Md (classe) para que ela encapsulasse a matriz totalmente. Teria:
-> Variáveis de membro para:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Construtor que permitiria a criação de uma matriz com o tamanho certo (linhas, colunas).
This would allow you to use vector resize and reserve which will give you
a more performant implementation, especially if the matrices are re-used.
So avoid using push_back and instead set values directly.
-> Obter funções para obter o número de linhas / colunas
-> Funções Get / Set para obter / definir valores de dados de matriz.
Get/Set functions implement bounds checking.
Eu, então, derivaria uma classe mathMatrix que adicionaria a funcionalidade de multiplicação de matriz. Isso exigiria a substituição da maior parte do acesso direto às funções de tamanho / itens de dados, etc., pelas chamadas acima, o que tornaria mais fácil ler e manter.
Então, como o autor anterior sugeriu, adicionar as funções isValid ou canMultiply ajudaria a tornar a solução mais robusta.