質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

キャッシュ

キャッシュはドキュメントやデータを一時的に保管するもので、アクセス処理時間を短くするために使用されます。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

Q&A

解決済

3回答

1605閲覧

行列の回転における高速化

akaevaka

総合スコア8

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

キャッシュ

キャッシュはドキュメントやデータを一時的に保管するもので、アクセス処理時間を短くするために使用されます。

最適化

最適化とはメソッドやデザインの最適な処理方法を選択することです。パフォーマンスの向上を目指す為に行われます。プログラミングにおける最適化は、アルゴリズムのスピードアップや、要求されるリソースを減らすことなどを指します。

0グッド

0クリップ

投稿2021/07/24 02:18

編集2021/07/24 06:15

###質問内容
行列の回転(転置させてあと,行の順序の反転)をなるべく効率よく行いたいと考えているのですが,愚直な方法しか思い浮かびません,効率化の方法としてはどのようなものが考えられますでしょうか.

二回転置していて,一回目のほうはCPUとキャッシュを温めるために行っています.

現状のコードは次のようになっています.

C

1#include<stdio.h> 2#include <stdlib.h> 3#include <time.h> 4#include "clock.h" 5#define N 64 6#define data_t double 7 8 9 int src[N][N], dst[N][N]; 10 11void naive_rotate(int n, int src[n][n], int dst[n][n]) 12{ 13 int i, j; 14 for (i = 0; i < n; i++) 15 for (j = 0; j < n; j++) 16 dst[n-1-j][i] = src[i][j]; 17 return; 18} 19 20 21int main(void){ 22 double t; 23 srand((unsigned int)time(NULL)); 24 25 for(int i = 0; i < N; i++){ 26 for(int j = 0; j < N; j++){ 27 src[i][j] = rand() % 10; 28 //printf("%d ",src[i][j]); 29 } 30 //printf("\n"); 31 } 32 33 naive_rotate(N, src, dst); 34 35 start_counter(); 36 naive_rotate(N, src, dst); 37 t = get_counter(); 38 printf("%7.4f\n", t); 39 40 41 return 0; 42 43}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

episteme

2021/07/24 02:41

転置行列になってますか?
akaevaka

2021/07/24 06:14

すいません,転置だけではなく反転もしているので回転でした, 修正させていただきます
guest

回答3

0

一般論で言うと、不連続書込みのペナルティは不連続読み出しのペナルティよりも大きいので

C

1 for (i = 0; i < n; i++) 2 for (j = 0; j < n; j++) 3 dst[n-1-j][i] = src[i][j]; 4

C

1 for (j = 0; j < n; j++) 2 for (i = 0; i < n; i++) 3 dst[n-1-j][i] = src[i][j]; 4

とした方が速くなります。
ただし、コンパイラの最適化が、前者のコードを後者に変換して機械命令を生成している場合は性能は変わりません。

投稿2021/07/25 00:01

ppaul

総合スコア24666

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

akaevaka

2021/07/25 02:13

ペナルティの大きさも考慮すべきなのですね 後ほど計測してみたいと思います. ありがとうございます.
guest

0

ベストアンサー

dst[n-1-j][i] = src[i][j]; だと転置ではなく回転です。

転置なら、det[j][i] = src[i][j]; です。

愚直なら、二重ループで、これは (n* n)回実行されます。
しかし次のようにするとループの回数が約半分になります。

C

1 for (i = 0; i < n; i++) 2 for (j = 0; j <= i; j++) { 3 dst[j][i] = src[i][j]; 4 dst[i][j] = src[j][i]; 5 }

代入回数は対角成分の分だけ増えますが、
ループ回数の減少のほうが大きく効いてくるでしょう。

配列をポインタに置き換えると高速になることがありますが、
最近のコンパイラは最適化でこれを勝手にやってくれたりします。

追記
回転なら愚直に (n*n)回ループするしかないでしょう。

ただ、dst[n-1-j][i] = src[i][j]; のように
dst を飛び飛びにして、src を連続にするよりも、
dst[i][j] = src[j][n-1-i]; のように
dst を連続にして、src を飛び飛びにするほうがほんのわずか速いかもしれません。

追記2
ポインタにしてみました。添字の計算で掛け算がなくなり速くなるかもしれません。
配列のアドレスより前を指すので規格違反ですが、そこはアクセスしません。

C

1void naive_rotate(int n, int src[n][n], int dst[n][n]) 2{ 3 int *dp = dst[0], *sp = src[0] - 1, m = n*n + 1; 4 for (int i = 0; i < n; i++) { 5 for (int j = 0; j < n; j++) 6 *dp++ = *(sp += n); 7 sp -= m; 8 } 9}

もちろん、コンパイル時には最適化オプションを指定してください。

追記3

今回はN=64~2048の2の冪乗の数で計測しようとしています.

それなら、可変長配列なんか使わず、次のようにすれば速くなるのではありませんか?

#define N 64 void naive_rotate(int n, int src[N][N], dst[N][N]) { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dst[i][j] = src[j][N-1-i]; }

引数の int n は使っていないので不要ですが、呼び出し元を変更しないで済む
ように残しています。

投稿2021/07/24 04:32

編集2021/07/25 13:48
kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

akaevaka

2021/07/24 06:17

説明が不十分でした,転置と反転の操作を行っているので,おっしゃる通り回転で,私が行いたいものも回転です. 回転についても転置でおっしゃっていただいた上記のような結果になりますでしょうか.
episteme

2021/07/24 07:17 編集

代入回数は変わらんけど条件判定は半分になるから多少は速くなりそう... せやけどNが小さいとほとんど変わらんだろなー O(N^2) を O(N)とかO(√N)とかにしたいんですよね?
akaevaka

2021/07/24 11:07

計算量はできるだけ小さくはしたいですね キャッシュなども考慮するのが良いのでしょうか. ひとまず,教えていただいたように,srcの方で飛ばしてみます.
HogeAnimalLover

2021/07/24 11:38

>>オーダの話。これ、オーダ下げられますか?オーダを下げることができるとは思えないです。データ列がランダムなので省く余地があると思えません。
Zuishin

2021/07/24 11:50

遅延評価(つまりデータのメモリ上の位置と行列の各要素との対応についてはフラグで管理し、実際に行列演算をする段階になってから処理する)すれば処理によっては下げられるくらいでしょうか。 こんなチューニングしても差が出るかどうかわからないようなところをいじるより、他にいじるところがありそうです。
Zuishin

2021/07/24 11:59 編集

たとえば、二つの行列をそれぞれ回転させてから加算する場合、回転を二回行ってから加算するという順番だと、演算が回転、回転、加算の三回行われます。 これを、加算してから回転するという順番に変えると、演算が加算、回転の二回に抑えられます。 私が先ほどコメントした遅延評価というのは、実際には回転させず、回転したというフラグだけ付与します。 すると、回転、回転、加算の順番で行っても、回転にはほとんど処理時間がかからないため、実際の演算は加算のみの一回で済みます。
akaevaka

2021/07/24 12:02

>>これ、オーダ下げられますか?オーダを下げることができるとは思えないです。データ列がランダムなので省く余地があると思えません。 私もオーダーを小さくできる方法は一切思い浮かばないのですが,もしあるのならばその方が好ましいです,くらいのニュアンスです.確かに完全にランダムなので,厳しいとは思います.
akaevaka

2021/07/24 12:04

>>たとえば、二つの行列をそれぞれ回転させてから加算する場合、回転を二回行ってから加算するという順番だと、演算が回転、回転、加算の三回行われます。 考慮するのは回転までで,演算についての高速化は現状考量しないつもりです.ですが,確かにおっしゃる通りの方法で演算時には高速化を図ることが出来そうなので,参考にさせていただきます.
Zuishin

2021/07/24 12:06

回転した後に他の演算を行わないのであれば、何のために回転するんでしょうか? そういう課題ですか?
akaevaka

2021/07/24 12:10

>>回転した後に他の演算を行わないのであれば、何のために回転するんでしょうか? 勉強する際に参考している資料でループの階層構造は階層をいじるなどによって高速化することが出来るといった内容があり,その箇所のやってみよう,みたいな感じのものです.回答例等が載っていないので質問させていただきました.
akaevaka

2021/07/24 12:12

>>dst[i][j] = src[j][n-1-i]; のように dst を連続にして、src を飛び飛びにするほうがほんのわずか速いかもしれません。 この方法で試してみたところ,Nを512にしたくらいから速度の差が出てきて,早くなっていました.
Zuishin

2021/07/24 12:42 編集

> ループの階層構造は階層をいじるなどによって高速化することが出来る この目的を、資料に載っていた具体例とともに質問に書いておいてください。 そうすればそれに沿った回答がつく可能性があります。 この回答は階層を全く変えていません。 たとえば行列のサイズが限られている場合、次のような方法が考えられます。 1 2 3 4 5 6 この行列は二次元配列として表せますが、メモリ上の配置は 1 2 3 4 5 6 になります。 これを回転して次の形にした場合 4 1 5 2 6 3 メモリ上の配置は 4 1 5 2 6 3 になります。 つまり、1 2 3 4 5 6 を 4 1 5 2 6 3 に並べなおすためのテーブル 1 3 5 0 2 4 を用意すれば、元のデータの最初の要素である 1 はテーブルの最初の要素である 1 に従って 0 ベースの二番目の位置に移動し、2 はテーブルの二番目の要素である 3 に従って 4 番目の位置に移動し、のようにシーケンシャルに移動できます。 行列の大きさが決まっているならテーブルは予め作成しておいてもいいし、決まっていないなら同じサイズの行列の大量の回転が必要になる直前に一度作成してもいいでしょう。
Zuishin

2021/07/24 12:54

階層構造をいじらなくてもいいなら、並列処理を採用することによって複数の CPU を同時に使用して処理時間を短くすることができるのではないかと思います。
akaevaka

2021/07/24 13:06

>>この目的を、資料に載っていた具体例とともに質問に書いておいてください 行列の積を具体例にしていて,三つのループijkの順番を変更することで速度が変わるというものなのですが,そのパターンをすべて記載するのは見にくくなるのではないでしょうか. また高速化は階層構造を変える制限は文意にはないと思うので,上記の回答でも問題ないと思われます.
Zuishin

2021/07/24 13:07

文意はここに書いてないので知りません。 私が知りえるのは、あなたが書いたものだけです。
Zuishin

2021/07/24 13:08

あと、テーブルの作成はプログラムでできるので、見にくくはならないでしょう。
episteme

2021/07/24 13:26 編集

3D-graphicsに用いるとかならNは高々4でしょう。 ならばfor-loopをほどいて代入式をN*N個書き並べるのが最速っちゃー最速かも。
akaevaka

2021/07/25 02:14

>>あと、テーブルの作成はプログラムでできるので、見にくくはならないでしょう そうなのですね,行ったことがないので少し調べてみます.
akaevaka

2021/07/25 02:16

>>>3D-graphicsに用いるとかならNは高々4でしょう。 今回はN=64~2048の2の冪乗の数で計測しようとしています. 3D-graphicsはあまりサイズが大きくならないのですね
episteme

2021/07/25 04:17

座標変換(拡大/縮小/回転/移動/etc.)の類なら点(x,y,z,t)に4x4行列を作用させることで実現できますから。
HogeAnimalLover

2021/07/25 04:27

オーダを下げることができないならば、時間利益は大して得られません。機械語レベルでのコーディングをすれば若干の利益は得られるでしょうが、私ならば別の部分での利益を模索します。
Zuishin

2021/07/25 05:00

私の提案したのは、コードの一部ではなく最終的なものを見てオーダーを下げる方法と、並列化して時間短縮することの二つです。
episteme

2021/07/25 07:09

Nがかなり大きいならGPU-computing: cuBLAS あたりを使えばかなり高速になります > 並列化
kazuma-s

2021/07/26 03:20

解決になっていますが、複数の回答からどれを採用して、どのように解決したのですか? どの程度高速化されたのですか?
akaevaka

2021/08/12 07:44

飛び地にすつ添え字を変えてたり,一気に複数行みるなどして4倍程度高速になりました
guest

0

専用命令とかコンパイラの最適化くらいですかね。

データ列がランダムならば、愚直な方法しか存在しません。

投稿2021/07/24 02:45

HogeAnimalLover

総合スコア4830

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

akaevaka

2021/07/24 06:17

専用命令としたら,例えばどのような方針のモノが有効なのか,方針などあったりしますでしょうか.
HogeAnimalLover

2021/07/24 07:00

専用命令は環境依存なので一概には言えません。そして、これはハードウェア的な方法なので、望ましい方法ではないです。(互換性が低下する等のデメリットを伴う)
akaevaka

2021/07/24 11:05

そうなのですね,ご回答ありがとうございます.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問