Optymalizacja algorytmu mnożenia macierzy
Zaimplementowałem własną wersję algorytmu do mnożenia dwóch macierzy razem i potrzebuję kogoś, kto wie, co robią, aby zobaczyć, czy jest coś, co można zrobić w bardziej optymalny sposób. Zależy mi również na zrozumieniu, w jaki sposób mogę uczynić go solidnym, tak aby nie ulegał awarii, gdy nieprostokątne macierze są przekazywane jako argument, tj. Macierz, która ma nieparzystą liczbę elementów w różnych Vdsach.
Szczególnie interesuje mnie funkcja matrixDotw poniższym kodzie, reszta to tylko pokazanie, jak ją wykorzystuję w moim projekcie).
#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;
}
Odpowiedzi
Widzę kilka rzeczy, których możesz chcieć użyć do ulepszenia kodu.
Użyj w usingodpowiednich przypadkach
Kod zawiera obecnie:
struct Vd
{
std::vector<double> v;
};
Jest to prawdopodobnie lepiej wyrażone w ten sposób:
using Vd = std::vector<double>;
Więc teraz, zamiast pisać to:
out << mat.m[i].v[j] << ", ";
Możemy użyć tej czystszej składni:
out << mat.m[i][j] << ", ";
Zrozumienie nagłówka zawiera ścieżki
Istnieje subtelna różnica między #include "iostream"i #include <iostream>. Chociaż jest zdefiniowana w implementacji, większość implementacji kompilatora polega na tym, że formularz cudzysłowu najpierw przeszukuje lokalnie (np. Bieżący katalog), a następnie przeszukuje system, uwzględniając katalogi, jeśli to się nie powiedzie. Forma nawiasów ostrych zwykle przeszukuje w systemowych katalogach. Zobacz to pytanie, aby uzyskać więcej informacji. Z tego powodu ten kod powinien prawdopodobnie używać #include <iostream>.
Nie używaj, std::endljeśli naprawdę tego nie potrzebujesz
Różnica między std::endli '\n'polega na tym, że '\n'po prostu emituje znak nowej linii, podczas gdy w std::endlrzeczywistości opróżnia strumień. Może to być czasochłonne w programie z dużą liczbą operacji we / wy i rzadko jest faktycznie potrzebne. Najlepiej używać tylkostd::endl wtedy, gdy masz dobry powód, aby opróżnić strumień, a nie jest to często potrzebne w przypadku prostych programów, takich jak ten. Unikanie nawyku używania std::endlwhen '\n'will przyniesie korzyści w przyszłości, gdy będziesz pisać bardziej złożone programy z większą liczbą operacji we / wy i gdzie wydajność musi zostać zmaksymalizowana.
W razie potrzeby używaj funkcji standardowych
Zamiast pisać ostream& operator<<tak, jak masz, fajną alternatywą byłoby użycie std::copyi std::experimental::ostream_joinertak:
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";
}
Preferuj wartości zwracane zamiast parametrów wyjściowych
O wiele bardziej logiczne wydaje się matrixDotzwrócenie nowej macierzy, zamiast używania trzeciego parametru jako parametru wyjściowego. Zobacz F.20 więcej szczegółów.
Rozważ alternatywną reprezentację
Ten kod jest nieco kruchy, ponieważ zarówno Mdi Vdsą zaimplementowane jako struct, ze wszystkimi członkami publicznymi. Co gorsza, możemy mieć tablicę postrzępioną, w której każdy wiersz nie ma takiej samej liczby elementów. To prawdopodobnie nie przyniesie niczego miłego. Z obu tych powodów sugerowałbym użycie classi użycie pojedynczego vectordo przechowywania wszystkich przedmiotów. Zobacz to pytanie, aby uzyskać kilka pomysłów i porad, jak to zrobić. Możesz również spojrzeć na std::valarraytyp podstawowy.
Zapewnij pełną implementację klasy
Oprócz konstruktora pobierającego std::initializer_listargumenty, zasugerowałbym również niektóre inne operatory, takie jak operator==dla tej klasy.
Muszę przyznać, że jestem trochę zdezorientowany, zrobiłeś trudne części i masz pytanie dotyczące łatwych części? Mogę źle zrozumieć twoje pytanie.
Zależy mi również na zrozumieniu, w jaki sposób mogę uczynić go solidnym, tak aby nie ulegał awarii, gdy jako argument są przekazywane nieprostokątne macierze, tj. Macierz, która ma nieparzystą liczbę elementów w różnych Vds, które przechowuje.
Możesz potwierdzić, że masz dobrze uformowaną macierz, korzystając z
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;
}
i włączenie go do matrixDotfunkcji walidacji podobnej do walidacji kształtu, którą masz teraz
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();
}
Wszelkie optymalizacje, które przychodzą mi do głowy, są używane, std::arraya nie, std::vectorponieważ jesteś świadomy długości wierszy i kolumn w momencie tworzenia.
Osobiście rozszerzyłbym strukturę Md (klasę) tak, aby w pełni hermetyzowała macierz. To miałoby:
-> Zmienne składowe dla:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Konstruktor, który pozwoliłby na utworzenie macierzy o odpowiednim rozmiarze (wiersze, kolumny).
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.
-> Pobierz funkcje, aby uzyskać liczbę wierszy / kolumn
-> Funkcje Get / Set, aby pobrać / ustawić wartości danych macierzy.
Get/Set functions implement bounds checking.
Następnie wyprowadziłbym klasę mathMatrix, która dodałaby funkcję mnożenia macierzy. Wymagałoby to zastąpienia większości bezpośredniego dostępu do funkcji rozmiaru / elementów danych itp. Wywołaniami z powyższego, co ułatwiłoby ich odczytanie, a tym samym utrzymanie.
Następnie, jak sugerował wcześniejszy plakat, dodanie funkcji isValid lub canMultiply pomogłoby w ulepszeniu rozwiązania.