マトリックスの転置のアルゴリズムといくつかの簡単なプラス、マイナス、乗算
1873 ワード
マトリクスの回転は,正方行列の回転と非正方行列の回転に分けられ,正方行列はその場での回転をサポートし,非正方行列はサポートしない.
方程式のその場での転置アルゴリズム:
方陣の回転前後の形状は変わらないので、その場で変換することができます.
一般マトリクスの転置方法:
一般的なマトリクスでは、転送後のスペースが異なるので、事前にスタックの中で転送後のマトリクスのためにスペースを申請してから賦値演算を行い、最後に転送後のマトリクスに戻りますが、申請したスペースは使用後、手動で分析しないとメモリ漏れが発生することに注意してください.
2つの行列の加算:
この足し算は簡単でしょう.
m*n行列とn*p行列の乗算:
この関数は3つのforループがあり、一見頭を回しているが、よく見ると簡単で、m*n行列とn*p行列を乗算するとm*p行列になるので、まず2つのforループでm*pのフレームワークを構築し、次に2番目のforループで行列の行と列の乗算と加算を行う.
上記の書き方は分かりやすいですが、この書き方は最も速いアルゴリズムではありません.コンピュータがデータにアクセスするメカニズムを考慮すると、その中のforサイクルを交換すると、その速度は小幅に向上します.私たちの前のサイクル順序はi,j,kです.私たちはi,k,jに交換した後、同じコンピュータで、同じ実行ステップ数ですが、速度は違います.
これはなぜですか.単純なコンピュータ構造には、1つのプライマリメモリ、1つの2次キャッシュ、1つの1次キャッシュ、およびいくつかのレジスタ、および1つのALUがあり、データの一般的な流れは、プライマリメモリ->2次キャッシュ->1次キャッシュ->レジスタ->ALUであり、それぞれに必要な時間は100マシンサイクル、10マシンサイクル、2マシンサイクル、1マシンサイクルである.したがって、データがプライマリ・ストレージにある場合は、計算のたびにプライマリ・ストレージからデータを呼び出すので、速度が非常に遅くなります.コンピュータは速度を高めるためにいくつかの戦略を取った.配列を例にとると、必要なデータとその同行する隣接配列をキャッシュに予めロードして加速させ、ijk順序ではaとc配列の順序で行ごとにデータを取り、bは列ごとにデータを取るので、bが演算する際にデータを取るのが遅い.ikjは行ごとにデータを取るので、速度がずっと速くなります.
方程式のその場での転置アルゴリズム:
template
void transpose(T **a,int rows)
{
for(int i=0;i 方陣の回転前後の形状は変わらないので、その場で変換することができます.
一般マトリクスの転置方法:
template
void transpose(T **a,int rows,int cols)
{
T **b=new T*[cols];
for(int k=0;k 一般的なマトリクスでは、転送後のスペースが異なるので、事前にスタックの中で転送後のマトリクスのためにスペースを申請してから賦値演算を行い、最後に転送後のマトリクスに戻りますが、申請したスペースは使用後、手動で分析しないとメモリ漏れが発生することに注意してください.
2つの行列の加算:
template
void matrixAdd(T **a,T **b,T **c,int numberOfRows,int numberOfCols)
{
for (int i=0;i この足し算は簡単でしょう.
m*n行列とn*p行列の乗算:
template
void matrixMultiply(T **a,T **b,T **c,int m,int n,int p)
{
for(int i=0;i この関数は3つのforループがあり、一見頭を回しているが、よく見ると簡単で、m*n行列とn*p行列を乗算するとm*p行列になるので、まず2つのforループでm*pのフレームワークを構築し、次に2番目のforループで行列の行と列の乗算と加算を行う.
上記の書き方は分かりやすいですが、この書き方は最も速いアルゴリズムではありません.コンピュータがデータにアクセスするメカニズムを考慮すると、その中のforサイクルを交換すると、その速度は小幅に向上します.私たちの前のサイクル順序はi,j,kです.私たちはi,k,jに交換した後、同じコンピュータで、同じ実行ステップ数ですが、速度は違います.
これはなぜですか.単純なコンピュータ構造には、1つのプライマリメモリ、1つの2次キャッシュ、1つの1次キャッシュ、およびいくつかのレジスタ、および1つのALUがあり、データの一般的な流れは、プライマリメモリ->2次キャッシュ->1次キャッシュ->レジスタ->ALUであり、それぞれに必要な時間は100マシンサイクル、10マシンサイクル、2マシンサイクル、1マシンサイクルである.したがって、データがプライマリ・ストレージにある場合は、計算のたびにプライマリ・ストレージからデータを呼び出すので、速度が非常に遅くなります.コンピュータは速度を高めるためにいくつかの戦略を取った.配列を例にとると、必要なデータとその同行する隣接配列をキャッシュに予めロードして加速させ、ijk順序ではaとc配列の順序で行ごとにデータを取り、bは列ごとにデータを取るので、bが演算する際にデータを取るのが遅い.ikjは行ごとにデータを取るので、速度がずっと速くなります.