行列乗算アルゴリズムの最適化
私は2つの行列を乗算する独自のバージョンのアルゴリズムを実装しましたが、より最適な方法で実行できることがあるかどうかを確認するために、彼らが何をしているかを知っている人が必要です。また、非長方形の行列が引数として渡されたときにクラッシュしないように堅牢にする方法、つまりVd、保持する要素の数が不均一な行列を理解することにも熱心です。
私は以下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本当に必要ない場合は使用しないでください
差betweeenstd::endlと'\n'ということである'\n'一方で、単に、改行文字を発しstd::endl、実際のストリームをフラッシュします。これは、I / Oが多いプログラムでは時間がかかる可能性があり、実際に必要になることはめったにありません。ストリームをフラッシュする正当な理由があり、このような単純なプログラムではあまり必要ない場合にのみ使用std::endlすることをお勧めします。より多くのI / Oを備えたより複雑なプログラムを作成し、パフォーマンスを最大化する必要があるstd::endl場合、'\n'いつ実行するかを使用する習慣を回避することで、将来的に利益が得られます。
必要に応じて標準機能を使用する
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";
}
出力パラメーターよりも戻り値を優先する
matrixDot3番目のパラメーターを出力パラメーターとして使用するよりも、新しいマトリックスを返す方がはるかに論理的であるように思われます。詳細については、F.20を参照してください。
別の表現を検討する
このコードは、両方の点で幾分脆弱でMd且つVdとして実装されているstructすべてのメンバーのパブリックと、。さらに悪いことに、各行に同じ数のアイテムがないギザギザの配列が存在する可能性があります。これはおそらく良い結果にはならないでしょう。これらの両方の理由から、すべてのアイテムを保持するためにclassaとsinglevectorを使用することをお勧めします。それを行う方法に関するいくつかのアイデアとアドバイスについては、この質問を参照してください。またstd::valarray、基になる型として見ることもできます。
フルクラスの実装を提供する
std::initializer_list引数を取るコンストラクターに加えて、operator==このクラスなどの他の演算子もいくつか提案します。
私は少し混乱していることを認めなければなりません、あなたは難しい部分をやり、簡単な部分について質問がありますか？私はあなたの質問を誤解しているかもしれません。
また、非長方形の行列が引数として渡されたときにクラッシュしないように堅牢にする方法、つまり、保持するさまざまなVdsに要素の数が不均一な行列を理解することにも熱心です。
次の方法で、整形式のマトリックスがあることを検証できます。
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).
->適切なサイズの行列（rows、cols）を作成できるコンストラクター。
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 functions implement bounds checking.
次に、行列の乗算機能を追加するmathMatrixクラスを導出します。これには、サイズ関数/データ項目などへの直接アクセスのほとんどを上記の呼び出しに置き換える必要があります。これにより、読みやすくなり、保守が容易になります。
次に、以前の投稿者が提案したように、isValidまたはcanMultiply関数を追加すると、ソリューションをより堅牢にするのに役立ちます。