행렬 곱셈 알고리즘 최적화
나는 두 개의 행렬을 함께 곱하는 알고리즘의 자체 버전을 구현했으며 더 최적의 방법으로 수행 할 수있는 것이 있는지 확인하기 위해 수행중인 작업을 아는 사람이 필요합니다. 또한 직사각형이 아닌 행렬이 인수로 전달 될 때 충돌하지 않도록 강력하게 만들 수있는 방법을 이해하고 있습니다. 즉, 서로 다른 Vds 의 요소 수가 고르지 않은 행렬입니다 .
특히 matrixDot아래 코드의 기능 에 관심이 있습니다 . 다른 모든 것은 프로젝트에서 어떻게 사용하고 있는지 보여주는 것입니다.)
#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;
}
답변
코드를 개선하기 위해 사용할 수있는 몇 가지 사항이 있습니다.
를 사용하여 using적절한
현재 코드에는 다음이 포함됩니다.
struct Vd
{
std::vector<double> v;
};
이것은 아마도 다음과 같이 더 잘 표현 될 것입니다.
using Vd = std::vector<double>;
이제 다음을 작성하는 대신 :
out << mat.m[i].v[j] << ", ";
이 깔끔한 구문을 사용할 수 있습니다.
out << mat.m[i][j] << ", ";
헤더 포함 경로 이해
#include "iostream"와 사이에는 미묘한 차이가 #include <iostream>있습니다. 구현이 정의되어 있지만 대부분의 컴파일러 구현은 인용 부호 형식이 로컬에서 먼저 (예 : 현재 디렉터리) 검색 한 다음 실패 할 경우 시스템 포함 디렉터리를 검색하는 것입니다. 꺾쇠 괄호 형식은 일반적으로 시스템 포함 디렉터리에서 검색합니다. 자세한 내용은 이 질문 을 참조하십시오 . 따라서이 코드는 #include <iostream>.
std::endl정말로 필요 하지 않으면 사용하지 마십시오.
차이의 betweeen std::endl하고 '\n'있다는 것입니다 '\n'반면 다만, 개행 문자를 방출 std::endl실제로 스트림을 플러시합니다. I / O가 많은 프로그램에서는 시간이 많이 걸릴 수 있으며 실제로는 거의 필요하지 않습니다. 스트림을 플러시 할 합당한 이유가있을 때만 사용하는 것이 가장 std::endl좋으며 이와 같은 간단한 프로그램에는 자주 필요하지 않습니다. 사용하는 습관을 방지 std::endl할 때 '\n'더 많은 I / O 및 성능 요구 사항을 극대화 할 수있는 더 복잡한 프로그램을 작성할 때 미래에 배당금을 지불 할 것입니다.
적절한 경우 표준 기능 사용
ostream& operator<<당신이 가진대로 작성하는 대신 깔끔한 대안은 다음 std::copy과 std::experimental::ostream_joiner같이 사용하는 것입니다 .
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";
}
출력 매개 변수보다 반환 값 선호
matrixDot세 번째 매개 변수를 출력 매개 변수로 사용하는 것보다 새 행렬 을 반환하는 것이 훨씬 더 논리적으로 보입니다 . 자세한 내용은 F.20 을 참조하십시오.
대체 표현 고려
이 코드는 모든 멤버가 공개 된 상태 에서 Md및 Vd으로 구현 된다는 점에서 다소 취약 struct합니다. 더 나쁜 것은 각 행에 동일한 수의 항목이없는 들쭉날쭉 한 배열을 가질 수 있다는 것입니다. 이것은 아마도 좋은 결과를 얻지 못할 것입니다. 이 두 가지 이유로 모든 항목을 보관하려면 a class및 단일 vector을 사용하는 것이 좋습니다 . 이를 수행하는 방법에 대한 몇 가지 아이디어와 조언을 보려면 이 질문 을 참조하십시오 . std::valarray기본 유형으로 볼 수도 있습니다 .
전체 클래스 구현 제공
std::initializer_list인수 를받는 생성자 외에도이 operator==클래스 와 같은 다른 연산자도 제안 합니다.
좀 헷갈 린다는 걸 인정해야 겠네요. 어려운 부분을했고 쉬운 부분에 대한 질문이 있으신가요? 귀하의 질문을 오해하고있을 수 있습니다.
또한 직사각형이 아닌 행렬이 인수로 전달 될 때 충돌하지 않도록 강력하게 만들 수있는 방법을 이해하고 있습니다. 즉, 보유하고있는 서로 다른 Vd에서 요소 수가 고르지 않은 행렬입니다.
다음을 통해 잘 구성된 행렬이 있는지 확인할 수 있습니다.
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;
}
matrixDot현재 가지고있는 모양 검증과 유사한 검증 을 위해 함수에 통합합니다.
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();
}
내가 생각할 수있는 모든 최적화 는 생성시 행과 열 길이를 알고있는 std::array대신 활용하는 것입니다 std::vector.
개인적으로 Md 구조체 (클래스)를 확장하여 행렬을 완전히 캡슐화합니다. 다음과 같습니다.
-> 멤버 변수 :
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> 올바른 크기의 행렬을 만들 수있는 생성자 (행, 열).
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.
-> 행 / 열 수를 가져 오는 함수 가져 오기
-> Get / Set 함수는 매트릭스 데이터 값을 가져 오거나 설정합니다.
Get/Set functions implement bounds checking.
그런 다음 행렬 곱셈 기능을 추가하는 mathMatrix 클래스를 파생 시켰습니다. 이것은 크기 함수 / 데이터 항목 등에 대한 대부분의 직접 액세스를 위의 호출로 대체하여 읽기 쉽고 유지 관리가 더 쉬워야합니다.
그런 다음 이전 포스터에서 isValid 또는 canMultiply 함수 추가를 제안했듯이 솔루션을 더 강력하게 만드는 데 도움이됩니다.