プログラムの高速化について語る
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
NGNG速いプログラムをつくるテクニックを教えて下さい。
0204妄想君
NGNGこれと妄想matrix.hの m1 = m2*m3を比べてみようかと。
0205妄想君
NGNGclass matrix
{
private:
int m_row, m_col;
public:
T *m_pMatrix;
explicit matrix(int row = 0, int col = 0) : m_row(row), m_col(col) { NewMatrix(); } // デフォルトコンストラクタ
matrix(const matrix<T> &m) // コピーコンストラクタ
{
m_row = m.GetRow(), m_col = m.GetCol();
NewMatrix();
int n = m_row*m_col;
T *p1 = m_pMatrix, *p2 = m.m_pMatrix;
for (int i = 0; i < n; i++, p1++, p2++) {
*p1 = *p2;
}
}
~matrix() { DelMatrix(); } // デストラクタ
void NewMatrix() { m_pMatrix = new T[m_row*m_col], assert(m_pMatrix != 0); } // 行列の領域確保
void DelMatrix() { delete [] m_pMatrix; } // 行列の領域開放
int GetRow(void) const { return m_row; } // プライベートメンバへのアクセス
int GetCol(void) const { return m_col; }
void SetSize(const int row, const int col) { DelMatrix(), m_row = row, m_col = col, NewMatrix(); }
T &operator () (int row, int col) // 配列演算子
{
assert(row >= 0 && col >= 0 && row < m_row && col < m_col);
return m_pMatrix[row*m_col + col];
}
const T &operator () (int row, int col) const
{
assert(row >= 0 && col >= 0 && row < m_row && col < m_col);
return m_pMatrix[row*m_col + col];
}
matrix<T> &operator = (const matrix<T> &);
};
0206妄想君
NGNGmatrix<T> &matrix<T>::operator = (const matrix<T> &m) // 行列 ＝行列
{
assert((m_row == m.m_row) && (m_col == m.m_col));
if (&m != this) {
if (m_row == 0 && m_col == 0) SetSize(m.m_row, m.m_col);
int n = m_row*m_col;
T *p1 = m_pMatrix, *p2 = m.m_pMatrix;
for (int i = 0; i < n; i++, p1++, p2++) *p1 = *p2;
}
return *this;
}
template<typename T>
matrix<T> operator * (const matrix<T> &m1, const matrix<T> &m2) // 行列×行列
{
int row1 = m1.GetRow(), col1 = m1.GetCol(), row2 = m2.GetRow(), col2 = m2.GetCol();
int n1 = row2*col2 - 1, n2 = col2*(row2 - 1);
matrix<T> m3(row1, col2);
T tmp, *p1 = m1.m_pMatrix, *p2 = m2.m_pMatrix, *p3 = m3.m_pMatrix, *p4 = p2;
assert(col1 == row2);
for (int i = 0; i < row1; i++, p1 += col1, p2 = p4) {
for (int j = 0; j < col2; j++, p1 -= col1, p2 -= n1, p3++) {
tmp = 0;
for (int k = 0; k < col1; k++, p1++, p2 += col2) {
tmp += *p1 * *p2;
}
*p3 = tmp;
}
}
return m3;
}
0207妄想君
NGNGつかれたので高速化したのは明日…
つーかようやく今帰宅
ふと思ったけど連続書き込みで荒らしみたい
0208デフォルトの名無しさん
NGNGでも今は時間がない。(;;)
0209デフォルトの名無しさん
NGNGhttp://www.tietew.jp/cppll/archive/274
0210145
NGNG汎用的なやつに対しては上のようなものを書いて,
2x2, 3x3, 4x4 は別に用意するっていうのが吉かなあと思います.
この方式だと 2x2 とかに関してはクラス + 演算子のオーバーロードを
用いたやつでも結構いい性能がだせます.
あと new/delete を malloc/free に変えてみると, 速度の点で
おもしろいことがおこるかもしれません. これは行列のサイズ依存かも
知れないけど.
0211妄想君
NGNG4*4くらいまでは別に用意するのは禿道、
2*2でオーバーロードで十分なのは作業用の配列が必要ないのが原因と思われ。
ところで行列乗算で乗算回数を減らすアルゴリズムを適用したんだけど
馬鹿でかい(200*200くらい)複素行列くらいじゃないと効き目がないことに落胆の色隠せず。
書き方下手なんじゃろうか。
結局上に書いたのをちょっと書き換えて作業用配列も参照渡しするのが
実用的な行列に対しては自己最速。
>>203 に書いたのと比較したんだけど
203の書きかたがまずいのか妄想Verの方が速かった。
vararray使った速いソースきぼんぬる。
0212145
NGNG>2*2でオーバーロードで十分なのは作業用の配列が必要ないのが原因と思われ。
ってどういうこと? 行列の各要素は配列に入れてるんだけど, ひょっとして
x, y, z, w とかいう変数に入れたほうが速い ?
2x2, 3x3, 4x4 で速い要因としては
1. ループが手動で全部展開できる.
2. コンストラクタも matrix(double a11, double a12, double a21, double a22)
とかいう変態的な形が使える.
3. malloc/free がいらない.
4. インラインも展開 OK
5. 逆行列も, 行列式も決めうち可能.
というところかと(ほんとに当たり前のことばかり書いてごめんなさい).
いくつかは賢いコンパイラがよきに計らってくれるんでしょうが ...
0213デフォルトの名無しさん
NGNG0214デフォルトの名無しさん
NGNG規格上0クリア必須だっけ？＞new
0215デフォルトの名無しさん
NGNGけどmallocもANSI準拠だと明示的に未開放でもexitした時に
OSにメモリを返す機構が必要なんで多少のオーバーヘッドはある
速度稼ぐんであればOSべったりのメモリ関数つかうのが良いと思われ
0216デフォルトの名無しさん
NGNG0217妄想君
NGNG要するに演算後の要素を直接与えられた行列の要素を使って
書き出せるってことだよねん？
でも考えてみりゃ*=使わなければ値返す行列が必要か。
結局高速にしたい場合はコンストラクタ作るオーバーヘッドなくすのに
mulみたいにするんだろうか、あるいはここまで最適化してくれるのかな。
試してないけどしてくれそうだね。
0218デフォルトの名無しさん
NGNG>OSにメモリを返す機構が必要
はつみみです。
0219145
NGNG>要するに演算後の要素を直接与えられた行列の要素を使って
>書き出せるってことだよねん？
ごめんなさい... 日本語が分からない ...
>結局高速にしたい場合はコンストラクタ作るオーバーヘッドなくすのに
>mulみたいにするんだろうか、あるいはここまで最適化してくれるのかな。
>試してないけどしてくれそうだね。
アセンブラのコード見てないへたれだけど, 最適化してくれると思ってる.
最適化してくれないと complex もうまくいかなかっただろうし.
任意の次元の行列はどうしたらいいのか分からないので, 妄想さんに期待.
0220デフォルトの名無しさん
NGNGテンプレートでどうぞ。い
0221デフォルトの名無しさん
NGNG215 にはコテハン「知ったかクン」を贈呈したいと思うが、どうか？
とりあえず Inside the C++ Object Model とエキスパート C プログラミングを
読んで出直して来い。
0222妄想君
NGNG漏れの素人考えでは
要素はmalloc使わずに
double e11, e12, e21, e22;
と書けるし
乗算に限らず逆行列でもmallocで作業用の行列をつくることなく直接
det = 1/(_e11*_e22 - _e12*_e21);
e11 = det*e22;
とかfor文使わずに書けるし、これなら実行速度が速くなるかなぁと。
って>>212に書いてあるまんまじゃん（鬱
一般行列の乗算は
>>206の
matrix<T> operator * (const matrix<T> &m1, const matrix<T> &m2) // 行列×行列
を
matrix<T> &mul(const matrix<T> &m1, const matrix<T> &m2, matrix<T> &m3)
にして
matrix<T> m3(row1, col2);
を消せばいいんじゃないでしょうか。
いろいろやってみたけど、小さい行列は
>>212のように matrix2とかmatrix3とか専用クラス作って
中くらいの行列(n = 5 〜 100)は↑に書いたmulで
大きい行列(n > 100)はブロック化するのでfinal answer。
STLのvalarrayは...速いの組める人教えて下さい、おながいします。
>>203みたいに使うとどうも遅くて。
0225デフォルトの名無しさん
NGNG照れ屋さんな貴方ってステキ
0226145
NGNG>matrix<T> &mul(const matrix<T> &m1, const matrix<T> &m2, matrix<T> &m3)
で, 満足なんですか ? と煽ってみる(w
224 にもあるように一般的な大きさの行列に対してはテンプレートの
再帰的な利用(expression template)になるんですかね ?
ていうか Blitz++ を素直に使え ?
0227煽られている妄想君
NGNG速くなるってことなんだろうか（しったか。）
いや、C++始めたばっかなんでそんな高度なことは考えたこともなかったYO。
時間あれば勉強したいが当分…
ちなみにBlitz++はVC++なので使用不可〜。
0228煽られている妄想君
NGNGもっとテンプレートの勉強にいいページない？
0229デフォルトの名無しさん
NGNGGeneric Programming with C++ Template
http://pc.2ch.net/test/read.cgi/tech/1008593126/l50
のスレでもそのテの話題があるよん。課題は汎用性と効率の両立。
0230!=189
NGNG遅レスですが, Intel コンパイラの valarray って
きわめてふつうな実装に見えます. C++ の入門の本にのっているやつと
あんまり変わらないような ? 違うんかな, 識者のレス求む.
GNU の valarray は遅延評価をやっているみたいです.
全部参照でデータを持っていて, 代入演算子のところでばばっと
演算しているみたい.
>> 227
GNU のやつは add(v3, v1, v2) とかと同じくらいの性能がでるので,
汎用的な行列は遅延評価を組み込んだものにすれば, いいのでは ?
0232デフォルトの名無しさん
NGNG実際に演算結果が必要になった時点で計算するやり方。
配列同士の計算だと、全部が全部必要ってわけでもないでしょ？
0233煽られ妄想
NGNG積を計算する順序でたいぶ計算量が変わりますから
0234デフォルトの名無しさん
NGNGもうすぐ出るCマガに記事が載るんでしょ？
0235デフォルトの名無しさん
NGNG0236数学に弱いプログラマ
NGNGsinは、0<=x<=PI/4のとき 0.99959257 * x - 0.1615350 * x * x * x
ってのは知ってるんだけど、それ以外調べても見つからず。。。
とりあえず、sinとcos、arctanについて知りたいんだけど。
何がやりたいのかと言うと、複素数ベクトルの直行座標<->極座標の変換なんだけど、
特にarctanが重過ぎてお話にならないのです。
誰か高速な手法教えてください。
ちなみに、SIMDで処理したいので、できれば分岐とかないアルゴリズムをキボンヌ。
0237デフォルトの名無しさん
NGNG入力の角度精度によっちゃあ、テーブル持った方がいいんじゃないか？
0238デフォルトの名無しさん
NGNG>ってのは知ってるんだけど
理解せずに使って平気かい。
それの求め方分かっていれば他のも求められるよ。
0239数学に弱いプログラマ
NGNG>>237
うーん、さすがにテーブルだと、実用的なサイズに収まらないので、
たとえ160〜300クロックかかってもfpatan呼んだ方がマシかも。
>>238
テーラー展開くらいなら多少は。
でも、その式はテーラー展開を途中で打ち切った式より精度が良いとか。
ちなみに、IntelのHPみたら、なんかSSEで各種数学関数を
近似計算してくれるとかいうソースコードを見つけたので
それで解決するかも。5倍は速いみたい。
ほぼフルアセンブラだから、そのまま抜き出して使えば、
かなりの速度向上が望めるかも。
0240デフォルトの名無しさん
NGNGまた、テーブルを間引いて補間多項式も併用できる。
区間が短ければ次数の低い補間多項式でも誤差は小さく抑えられる>>239
0241デフォルトの名無しさん
NGNG絶対値の誤差 2%、角度誤差 0.5度程度だったような...で
8087に勝った記憶あり。
0242デフォルトの名無しさん
NGNG＞複素数ベクトルの直行座標<->極座標の変換
自体の回数は減らせないの？
0243デフォルトの名無しさん
NGNGどれくらいの精度でやりたいの？
整数なら分岐有りだけど
ttp://www.infoeddy.ne.jp/~tensyo/prog/ALGO.HTM
整数だけでやればSIMD並の速度が出る場合もあるよ
0244デフォルトの名無しさん
NGNG0245デフォルトの名無しさん
NGNGきゅーすーてんかい
0246デフォルトの名無しさん
NGNGMatrix Inverse()
{
Matrix d;
//行列式計算
f32 d0 = +( (_11*_22*_33)+(_12*_23*_31)+(_13*_21*_32)-(_13*_22*_31)-(_23*_32*_11)-(_33*_12*_21));
f32 d1 = -( (_01*_22*_33)+(_02*_23*_31)+(_03*_21*_32)-(_03*_22*_31)-(_23*_32*_01)-(_33*_02*_21));
f32 d2 = +( (_01*_12*_33)+(_02*_13*_31)+(_03*_11*_32)-(_03*_12*_31)-(_13*_32*_01)-(_33*_02*_11));
f32 d3 = -( (_01*_12*_23)+(_02*_13*_21)+(_03*_11*_22)-(_03*_12*_21)-(_13*_22*_01)-(_23*_02*_11));
f32 s = (_00*d0+_10*d1+_20*d2+_30*d3);
if (s == 0){
//逆行列が存在しない
d.Identity();
return d;
}
//余因子行列計算と係数乗算
s = 1.0f / s;
d._00 = d0 * s;
d._01 = d1 * s;
d._02 = d2 * s;
d._03 = d3 * s;
d._10 = -( (_10*_22*_33)+(_12*_23*_30)+(_13*_20*_32)-(_13*_22*_30)-(_23*_32*_10)-(_33*_12*_20)) * s;
d._11 = +( (_00*_22*_33)+(_02*_23*_30)+(_03*_20*_32)-(_03*_22*_30)-(_23*_32*_00)-(_33*_02*_20)) * s;
d._12 = -( (_00*_12*_33)+(_02*_13*_30)+(_03*_10*_32)-(_03*_12*_30)-(_13*_32*_00)-(_33*_02*_10)) * s;
d._13 = +( (_00*_12*_23)+(_02*_13*_20)+(_03*_10*_22)-(_03*_12*_20)-(_13*_22*_00)-(_23*_02*_10)) * s;
d._20 = +( (_10*_21*_33)+(_11*_23*_30)+(_13*_20*_31)-(_13*_21*_30)-(_23*_31*_10)-(_33*_11*_20)) * s;
d._21 = -( (_00*_21*_33)+(_01*_23*_30)+(_03*_20*_31)-(_03*_21*_30)-(_23*_31*_00)-(_33*_01*_20)) * s;
d._22 = +( (_00*_11*_33)+(_01*_13*_30)+(_03*_10*_31)-(_03*_11*_30)-(_13*_31*_00)-(_33*_01*_10)) * s;
d._23 = -( (_00*_11*_23)+(_01*_13*_20)+(_03*_10*_21)-(_03*_11*_20)-(_13*_21*_00)-(_23*_01*_10)) * s;
d._30 = -( (_10*_21*_32)+(_11*_22*_30)+(_12*_20*_31)-(_12*_21*_30)-(_22*_31*_10)-(_32*_11*_20)) * s;
d._31 = +( (_00*_21*_32)+(_01*_22*_30)+(_02*_20*_31)-(_02*_21*_30)-(_22*_31*_00)-(_32*_01*_20)) * s;
d._32 = -( (_00*_11*_32)+(_01*_12*_30)+(_02*_10*_31)-(_02*_11*_30)-(_12*_31*_00)-(_32*_01*_10)) * s;
d._33 = +( (_00*_11*_22)+(_01*_12*_20)+(_02*_10*_21)-(_02*_11*_20)-(_12*_21*_00)-(_22*_01*_10)) * s;
return d;
}
余因子行列と行列式による4×4逆行列の算出アルゴリズムを書いてみました。
がんばればSIMDで最適化できそうではあるのですが、
ガウス法による算出とどちらが良いと思われますか。
0247デフォルトの名無しさん
NGNG0248デフォルトの名無しさん
NGNG0249デフォルトの名無しさん
NGNG何事もなく過ごせるかと思ったのですが（ｗ
本当は例外投げるべきなんでしょうけど。
0250sage
NGNG47 は読みましたか ?
まさにあなたの知りたいことがのっていると思います.
0251デフォルトの名無しさん
NGNG0252デフォルトの名無しさん
NGNGだって、例外投げるようにしたら少し遅くなっちゃうんですもの。
（by 元の行列を返してる不届き者）
0253246
NGNG今読んだ。うーん流石インテル。
知りたい情報がずばり詳細に。
このやり方は、クラマーっていうのか。
クラマールール英語で言うとかっこｲｲ。
0254煽られ妄想
NGNGVCはﾀﾞﾒ?
■ このスレッドは過去ログ倉庫に格納されています