配列をまわるループの回し方

プログラミングの基本事項なのではないかと思いますが、例えば３次元の配列a(100,100,100)があったとき、
do i=1,100
do j=1,100
do k=1,100
a(i,j,k)=.......
enddo; enddo; enddo

とするか、

do k=1,100
do j=1,100
do i=1,100
a(i,j,k)=.......
enddo; enddo; enddo

とするか、を考える場合、基本的にはどちらかのほうが有利である（処理が早くなる）ということだったと思います。a(i,j,k)=...の右辺の式にも依存するかもしれませんが、基本こうしなさいという作法があったと思います。どうだったでしょうか。多次元配列でも、メモリの格納方法は１次元となっており、あちこちに飛ばない方がいいという原理から来るのだと思いますが。言語依存ではないと思いますが。
また、これだけの工夫でどれくらい早くなるものでしょうか。(ルート２)倍ぐらいかにならないでしょうか。

どうだったでしょうか。よろしくお願いします。

No.2 回答者： Tacosan 回答日時： 2015/07/02 02:19

C には「多次元配列」というものは本来存在しない (2次元配列は「配列の配列」として処理する) わけですがそこは目をつむることにして.

C で
int a[2][3];
とあると, これは「int [3] の配列」となるのでメモリ上
a[0][0], a[0][1], a[0][2], a[1][0], a[1][1], a[1][2]
と並びます (「a[0][0]～a[0][2]」の部分が a[0] ). 一方 Fortran で
integer :: a(2, 3)
とすると, メモリ上の並びは
a(1, 1), a(2, 1), a(1, 2), a(2, 2), a(1, 3), a(2, 3)
となります.

ここでは 2次元配列で書きましたが, 任意の次元の配列でも同様に
・C では右の添字から先に変化する
・Fortran では左の添字から先に変化する
ので, 添字の動く順序がまったく反対になります.

単純な処理だとこれで速度が実際に変わる (数字もどこかで見た記憶はあるけど忘れた) のですが右辺が複雑だとそっちのせいであまり変わらないかも.

No.1 回答者： Tacosan 回答日時： 2015/07/02 00:47

参照の局所性の話であれば, どの順で添字をまわすと速くなる (可能性がある) かは言語に依存します. 有名なのは

Fortran と C では逆
ってやつだな.

この回答へのお礼

回答有難うございます。参照するときにアチコチに飛ぶな、ということですよね。
CとFortranが逆とのことですが、どのように逆なのでしょうか。片方だけ教えて頂ければと思いますが。

また、速くなる可能性はあるが、遅くなる可能性はない、ということであれば、ダメ元でそうするべきとは言えますね。どうでしょうか。
あるいは速くなる可能性４０％、変わらない可能性３０％、遅くなる可能性３０％だとしたら、まあ、そのほうがいいよねとも言えそうですが。

お礼日時：2015/07/02 00:57