Mengoptimalkan algoritma perkalian matriks
Saya telah menerapkan versi algoritme saya sendiri untuk menggandakan dua matriks bersama-sama dan saya membutuhkan seseorang yang tahu apa yang mereka lakukan untuk melihat apakah ada sesuatu yang dapat dilakukan dengan cara yang lebih optimal. Saya juga tertarik untuk memahami bagaimana saya bisa membuatnya kuat sehingga tidak macet ketika matriks non-persegi panjang diteruskan sebagai argumen yaitu matriks yang memiliki jumlah elemen yang tidak merata di berbagai Vds yang dimilikinya.
Saya sangat tertarik dengan fungsi matrixDotdalam kode di bawah ini, yang lainnya hanya untuk menunjukkan bagaimana saya menggunakannya dalam proyek saya).
#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;
}
Jawaban
Saya melihat beberapa hal yang mungkin ingin Anda gunakan untuk meningkatkan kode Anda.
Gunakan usingjika sesuai
Kode saat ini berisi ini:
struct Vd
{
std::vector<double> v;
};
Ini mungkin lebih baik diungkapkan seperti ini sebagai gantinya:
using Vd = std::vector<double>;
Jadi sekarang, daripada menulis ini:
out << mat.m[i].v[j] << ", ";
Kita dapat menggunakan sintaks yang lebih bersih ini:
out << mat.m[i][j] << ", ";
Pahami header include paths
Ada perbedaan halus antara #include "iostream"dan #include <iostream>. Meskipun implementasinya ditentukan, sebagian besar implementasi compiler adalah bahwa bentuk tanda kutip mencari secara lokal terlebih dahulu (misalnya direktori saat ini) dan kemudian sistem pencarian menyertakan direktori jika gagal. Bentuk braket sudut biasanya mencari di sistem termasuk direktori. Lihat pertanyaan ini untuk lebih lanjut. Oleh karena itu, kode ini mungkin harus digunakan #include <iostream>.
Jangan gunakan std::endljika Anda tidak benar-benar membutuhkannya
Perbedaan antara std::endldan '\n'itu '\n'hanya memancarkan karakter baris baru, sementara std::endlbenar-benar menyiram aliran. Ini dapat memakan waktu dalam program dengan banyak I / O dan jarang benar-benar dibutuhkan. Sebaiknya gunakan hanyastd::endl jika Anda memiliki alasan bagus untuk mengosongkan streaming dan ini tidak terlalu sering diperlukan untuk program sederhana seperti ini. Menghindari kebiasaan menggunakan std::endlkapan '\n'akan dilakukan akan memberikan keuntungan di masa depan saat Anda menulis program yang lebih kompleks dengan lebih banyak I / O dan di mana kinerja perlu dimaksimalkan.
Gunakan fungsi standar jika sesuai
Daripada menulis ostream& operator<<seperti yang Anda miliki, alternatif yang rapi adalah menggunakan std::copydan std::experimental::ostream_joinerseperti ini:
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";
}
Lebih suka mengembalikan nilai ke parameter keluaran
Tampaknya jauh lebih logis untuk matrixDotmengembalikan matriks baru, daripada menggunakan parameter ketiga sebagai parameter keluaran. Lihat F.20 untuk lebih jelasnya.
Pertimbangkan representasi alternatif
Kode ini agak rapuh karena Mddan Vddiimplementasikan sebagai struct, dengan semua anggota publik. Lebih buruk lagi, kita bisa memiliki array bergerigi di mana setiap baris tidak memiliki jumlah item yang sama. Ini mungkin tidak akan menghasilkan sesuatu yang baik. Untuk kedua alasan tersebut, saya sarankan menggunakan classdan menggunakan satu vectoruntuk menampung semua item. Lihat pertanyaan ini untuk beberapa ide dan saran tentang bagaimana melakukannya. Anda mungkin juga melihat std::valarraysebagai tipe yang mendasari.
Sediakan implementasi kelas penuh
Selain konstruktor yang mengambil std::initializer_listargumen, saya juga menyarankan beberapa operator lain seperti operator==untuk kelas ini.
Saya harus mengakui bahwa saya agak bingung, Anda melakukan bagian yang sulit dan memiliki pertanyaan tentang bagian yang mudah? Saya mungkin salah paham dengan pertanyaan Anda.
Saya juga tertarik untuk memahami bagaimana saya bisa membuatnya kuat sehingga tidak macet ketika matriks non-persegi panjang dilewatkan sebagai argumen yaitu matriks yang memiliki jumlah elemen yang tidak merata dalam Vds berbeda yang dimilikinya.
Anda dapat memvalidasi bahwa Anda memiliki matriks yang dibentuk dengan baik
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;
}
dan menggabungkannya ke dalam matrixDotfungsi untuk validasi yang mirip dengan validasi bentuk yang Anda miliki sekarang
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();
}
Pengoptimalan apa pun yang dapat saya pikirkan adalah menggunakan std::arrayalih-alih std::vectorseperti yang Anda ketahui tentang panjang baris dan kolom pada saat pembuatan.
Secara pribadi saya akan memperluas struct Md (class) sehingga merangkum matriks sepenuhnya. Ini akan memiliki:
-> Variabel anggota untuk:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Pembuat yang memungkinkan pembuatan matriks dengan ukuran yang tepat (baris, kolom).
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.
-> Dapatkan fungsi untuk mendapatkan jumlah baris / kolom
-> Get / Set berfungsi untuk mendapatkan / mengatur nilai data matriks.
Get/Set functions implement bounds checking.
Saya kemudian akan mendapatkan kelas mathMatrix yang akan menambahkan fungsionalitas perkalian matriks. Ini akan memerlukan penggantian sebagian besar akses langsung ke fungsi ukuran / item data dll dengan panggilan dari atas yang akan membuatnya lebih mudah untuk dibaca dan karenanya dipelihara.
Kemudian seperti poster sebelumnya menyarankan menambahkan fungsi isValid atau canMultiply akan membantu membuat solusi lebih kuat.