Optimización del algoritmo de multiplicación de matrices
He implementado mi propia versión de algoritmo para multiplicar dos matrices juntas y necesito a alguien que sepa lo que están haciendo para ver si hay algo que se pueda hacer de una manera más óptima. También estoy interesado en comprender cómo puedo hacerlo robusto para que no se bloquee cuando se pasan matrices no rectangulares como argumento, es decir, una matriz que tiene un número impar de elementos en diferentes Vds que contiene.
Estoy particularmente interesado en la función matrixDoten el código a continuación, todo lo demás es solo para mostrar cómo lo estoy usando en mi proyecto).
#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;
}
Respuestas
Veo algunas cosas que es posible que desee utilizar para mejorar su código.
Usar usingdonde sea apropiado
El código contiene actualmente esto:
struct Vd
{
std::vector<double> v;
};
Esto probablemente se exprese mejor así en su lugar:
using Vd = std::vector<double>;
Así que ahora, en lugar de escribir esto:
out << mat.m[i].v[j] << ", ";
Podemos usar esta sintaxis más limpia:
out << mat.m[i][j] << ", ";
Comprender las rutas de inclusión del encabezado
Existe una sutil diferencia entre #include "iostream"y #include <iostream>. Aunque está definida por la implementación, la mayoría de las implementaciones del compilador es que el formulario de comillas busca primero localmente (por ejemplo, el directorio actual) y luego busca los directorios incluidos en el sistema si eso falla. La forma de corchetes angulares generalmente busca en directorios de inclusión del sistema. Consulte esta pregunta para obtener más información. Por esa razón, este código probablemente debería usar #include <iostream>.
No lo use std::endlsi realmente no lo necesita
La diferencia entre std::endly '\n'es que '\n'solo emite un carácter de nueva línea, mientras que en std::endlrealidad vacía la secuencia. Esto puede llevar mucho tiempo en un programa con muchas E / S y rara vez se necesita. Es mejor usarlo solostd::endl cuando tenga una buena razón para descargar la transmisión y no es muy necesario para programas simples como este. Evitar el hábito de usar std::endlwhen '\n'will do pagará dividendos en el futuro a medida que escriba programas más complejos con más E / S y donde el rendimiento debe maximizarse.
Utilice funciones estándar cuando sea apropiado
En lugar de escribir el ostream& operator<<como lo ha hecho, una buena alternativa sería usar std::copyy std::experimental::ostream_joinerasí:
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";
}
Prefiere los valores de retorno a los parámetros de salida
Parece mucho más lógico matrixDotdevolver una nueva matriz, en lugar de utilizar el tercer parámetro como parámetro de salida. Consulte F.20 para obtener más detalles.
Considere una representación alternativa
Este código es algo frágil en el sentido de que tanto el Mdy Vdse implementan como struct, con todos los miembros públicos. Lo peor es que podríamos tener una matriz irregular en la que cada fila no tenga el mismo número de elementos. Esto probablemente no resultará en nada bueno. Por ambas razones, sugeriría usar una classy una única vectorpara contener todos los elementos. Consulte esta pregunta para obtener algunas ideas y consejos sobre cómo hacerlo. También puede considerarlo std::valarraycomo un tipo subyacente.
Proporcionar una implementación de clase completa
Además de que un constructor tome std::initializer_listargumentos, también sugeriría algunos de los otros operadores, como operator==para esta clase.
Tengo que admitir que estoy un poco confundido, ¿hiciste las partes difíciles y tienes una pregunta sobre las partes fáciles? Puede que esté malinterpretando tu pregunta.
También estoy interesado en comprender cómo puedo hacerlo robusto para que no se bloquee cuando se pasan matrices no rectangulares como argumento, es decir, una matriz que tiene un número impar de elementos en diferentes Vds que contiene.
Podrías validar que tienes una matriz bien 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ándolo a la matrixDotfunción de validación similar a la validación de forma que tiene ahora
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();
}
Cualquier optimización que se me ocurra se basa std::arrayen la utilización en lugar de std::vectoren el conocimiento de las longitudes de filas y columnas en el momento de la creación.
Personalmente, ampliaría la estructura Md (clase) para que encapsule la matriz por completo. Tendría:
-> Variables de miembro para:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Constructor que permitiría crear una matriz del tamaño adecuado (filas, columnas).
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.
-> Obtener funciones para obtener el número de filas / columnas
-> Obtener / Establecer funciones para obtener / establecer valores de datos de matriz.
Get/Set functions implement bounds checking.
Luego derivaría una clase mathMatrix que agregaría la funcionalidad de multiplicación de matrices. Esto requeriría reemplazar la mayor parte del acceso directo a funciones de tamaño / elementos de datos, etc.con llamadas de lo anterior, lo que facilitaría la lectura y, por lo tanto, el mantenimiento.
Luego, como sugirió el póster anterior, agregar las funciones isValid o canMultiply ayudaría a hacer que la solución sea más sólida.