2次元配列

高速化プログラミング   
トップ  >  メモリジャンプと高速化  > 2次元配列

2次元配列

■ 概要

どの言語でも2次元配列(マトリックス)を簡単に定義できます。しかしコンピューター内のメモりのアドレスは1次元に定義されているので、実は1次元配列しか受け付けていません。そのため、2次元配列を定義したときはそれを1次元配列に組み直す必要があります。幸いその組み直しはコンパイラーが自動的にやってくれますので、プログラマーはその組み直しを意識する必要なく、2次元配列を使用できます。しかし組み直し方に注意しないと、思わぬ不効率なコードを書いてしまいかねません。しかも言語によっては組み直し方が違うので、特に注意が必要。

2次元配列から1次元配列に組み直し方は2通りあります。今図1のようなサイズがm×nの2次元配列Aij(i=1, ..., m, j=1, ..., n)を定義したとします。図1では見やすくするために行別に色付けしてあります。

2次元配列
図1 サイズがm×nの2次元配列Aij

さてm×nの2次元配列Aij行単位で1次元配列に組みなおすと、図2のようになります。

行単位で組みなおされた1次元配列
図2 行単位で組みなおされた1次元配列

一方、列単位で組みなおすと、図3のようになります。

列単位で組みなおされた1次元配列
図3 列単位で組みなおされた1次元配列

2次元配列を処理するときは一般的に2重ループを用います。その2重ループの順番を組みなおされた1次元配列に合わせないと、メモリアクセスのジャンプが起こりかねません。つまり、内側のループのカウンターは、行単位の場合は配列の行、列単位の場合は列を指すようにしなければなりません。具体的には以下のサンプルをご覧ください。

C言語では行単位、FORTRAN言語では列単位の組み直し方が採用されますので、同じ動作のプログラムでもCとFORTRANとでは2重ループの順番は異なります。CからFORTRANにまたはその逆にコード書き換えようとするときに注意しなければなりません。

■ サンプル

○ Sample 1: 2次元配列への代入

- C
- FORTRAN
- JScript

○ Sample 2: マトリックス・ベクトルの掛け算

- C
- FORTRAN
- JScript



はじめに

演算数を減らす

メモリジャンプを減らす

高性能のアルゴリズム

その他



4 8 2 5 5 8