アドレス計算について

多次元データを1次元に埋め込むデータ構造はよく用いられる．例えば画像データなどでは，2次元データを長さ縦×横の1次元データに埋め込んでいる．カラー画像や行列でもしかり．このような幅が一定のデータであれば，次のように1次元に埋め込むことができる．

int data[width*height];

このような1次元のデータから，2次元の座標のデータを取り出すには，次のようなアドレス計算が必要だ．

data[y*width + x]; // 点(x,y)のデータ

今日はこのアドレス計算の最適化について考える．
まずは，全点を走査するような以下のループを考える．

for (int y=0; y<height; ++y)
for (int x=0; x<width; ++x)
  cout << data[y*width +x] << endl;

このコードの場合，ループ内では毎回 y*width +x という添字のアドレス計算が行われる．この計算は1回なら微々たるものであるが，ループ回数が多くなればなるほど計算量は増えていく．だが，このコードは次のように変形することができよう．

for (int x=0; x<width*height; ++x)
  cout << data[x] << endl;

これなら前述のような添字の計算はなくなる．しかし実はまだアドレス計算は残っている．配列の添字は，「あるメモリ上のアドレスからのインデックス」ということになっているからだ．具体的には，data[x] は *(data+x) のことなのである．したがって，さらにまだ以下のような最適化の余地はあろう．

for (int *addr=data; addr<&data[W*H]; ++addr)
  cout << *addr << endl;