Matris çarpım algoritmasını optimize etme
İki matrisi çarpmak için kendi algoritma versiyonumu uyguladım ve daha optimal bir şekilde yapılabilecek bir şey olup olmadığını görmek için ne yaptıklarını bilen birine ihtiyacım var. Ayrıca, dikdörtgen olmayan matrisler bağımsız değişken olarak, yani Vdtuttuğu farklı dillerde eşit olmayan sayıda öğeye sahip matris olarak geçildiğinde çökmeyecek şekilde onu nasıl sağlam yapabileceğimi anlamaya da meraklıyım .
Özellikle matrixDotaşağıdaki koddaki işlevle ilgileniyorum , diğer her şey sadece onu projemde nasıl kullandığımı göstermek içindir).
#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;
}
Yanıtlar
Kodunuzu geliştirmek için kullanmak isteyebileceğiniz bazı şeyler görüyorum.
Uygun olan usingyerlerde kullanın
Kod şu anda bunu içeriyor:
struct Vd
{
std::vector<double> v;
};
Bu muhtemelen bunun yerine daha iyi ifade edilir:
using Vd = std::vector<double>;
Şimdi bunu yazmak yerine:
out << mat.m[i].v[j] << ", ";
Bu daha temiz sözdizimini kullanabiliriz:
out << mat.m[i][j] << ", ";
Üstbilgi içerme yollarını anlama
#include "iostream"Ve arasında ince bir fark var #include <iostream>. Uygulama tanımlı olmasına rağmen, çoğu derleyici uygulaması, tırnak işareti formunun önce yerel olarak (örneğin mevcut dizin) araması ve ardından başarısız olursa sistemdeki dizinleri aramasıdır. Açılı ayraç formu genellikle sistemdeki aramalar dizinleri içerir. Daha fazlası için bu soruya bakın . Bu nedenle, bu kod muhtemelen kullanılmalıdır #include <iostream>.
std::endlGerçekten ihtiyacın yoksa kullanma
Fark betweeen std::endlve '\n'olmasıdır '\n'çıkarırken sadece bir satır karakteri yayar std::endlaslında akışı temizler. Bu, çok fazla G / Ç içeren bir programda zaman alıcı olabilir ve gerçekte nadiren gereklidir. Yalnızcastd::endl akışı temizlemek için iyi bir nedeniniz olduğunda kullanmak en iyisidir ve bunun gibi basit programlar için çok sık gerekli değildir. Daha fazla G / Ç ile ve performansın en üst düzeye çıkarılması gereken yerlerde daha karmaşık programlar yazdıkça, std::endlne '\n'zaman işe yarayacağını kullanma alışkanlığından kaçınmak, gelecekte size fayda sağlayacaktır.
Uygun olduğunda standart işlevleri kullanın
Aksine yazı daha ostream& operator<<var gibi düzgün bir alternatif kullanımına olacağını std::copyve std::experimental::ostream_joinerbunun gibi:
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";
}
Çıktı parametrelerine dönüş değerlerini tercih et
matrixDotÜçüncü parametreyi bir çıktı parametresi olarak kullanmak yerine, yeni bir matris döndürmek çok daha mantıklı görünüyor . Daha fazla ayrıntı için F.20'ye bakın.
Alternatif bir temsil düşünün
Bu kod biraz kırılgan olduğunu hem Mdve Vdgibi uygulandığı structtüm üyeler kamuoyu ile. Daha da kötüsü, her satırın aynı sayıda öğeye sahip olmadığı pürüzlü bir dizimiz olabilir. Bu muhtemelen güzel bir şeyle sonuçlanmayacak. Bu iki nedenden ötürü, tüm öğeleri tutmak için bir classve tek bir tane kullanmanızı öneririm vector. Bunun nasıl yapılacağına dair bazı fikirler ve tavsiyeler için bu soruya bakın . std::valarrayAltta yatan bir tür olarak da bakabilirsiniz .
Tam bir sınıf uygulaması sağlayın
Bir kurucu std::initializer_listargüman alan ek olarak operator==, bu sınıf için olduğu gibi diğer operatörlerden bazılarını da öneririm .
Biraz kafam karıştığını itiraf etmeliyim, zor kısımları sen yaptın ve kolay kısımlar hakkında bir sorum mu var? Sorunuzu yanlış anlıyor olabilirim.
Ayrıca, dikdörtgen olmayan matrisler bağımsız değişken olarak, yani tuttuğu farklı Vds'de eşit olmayan sayıda öğeye sahip matris olarak geçirildiğinde çökmeyecek şekilde onu nasıl sağlam yapabileceğimi anlamaya da meraklıyım.
İyi oluşturulmuş bir matrisiniz olduğunu doğrulayabilirsiniz.
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;
}
ve matrixDotşu anda sahip olduğunuz şekil doğrulamasına benzer şekilde doğrulama için işleve dahil etmek
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();
}
Düşünebildiğim herhangi bir optimizasyon , oluşturma sırasında satır ve sütun uzunluklarının farkında olmanız std::arrayyerine kullanmaktır std::vector.
Kişisel olarak, matrisi tam olarak kapsayacak şekilde Md yapısını (sınıfını) genişletirdim. Şunlara sahip olacaktır:
-> Üye değişkenleri:
The number of rows and columns.
Vector to hold the data. (Consider one dimensional array here).
-> Doğru boyutta bir matrisin (satırlar, sütunlar) oluşturulmasına izin veren kurucu.
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.
-> Satır / sütun sayısını elde etmek için işlevler alın
-> Matris veri değerlerini almak / ayarlamak için Get / Set işlevleri.
Get/Set functions implement bounds checking.
Daha sonra matris çarpma işlevini ekleyecek bir mathMatrix sınıfı türetirdim. Bu, boyut işlevlerine / veri öğelerine vb. Doğrudan erişimin çoğunun, okumayı ve dolayısıyla bakımını kolaylaştıracak şekilde yukarıdakilerden gelen çağrılarla değiştirilmesini gerektirecektir.
Daha önceki posterin önerdiği gibi, isValid veya canMultiply işlevlerinin eklenmesi, çözümü daha sağlam hale getirmeye yardımcı olacaktır.