配列におけるメモリへの格納順序とアクセス方法

#概要
配列の要素がメモリにどのように格納されているか、またどのようにその要素にアクセスされるかについてのまとめ。
#予備知識
##そもそも配列とは？
配列は同一型のデータの集まりであり、それぞれのデータは集まり内での場所を一番最初の要素に関連付けて識別される。¹

An array is a homogeneous aggregate of data elements in which an individual
element is identified by its position in the aggregate, relative to the first element

ほとんどのプログラミング言語において、配列は配列名と添え字の二つの部品によって成り立っている。

//　Java
int[] array = new int[3]
array[0] = 1;

//　C++
int array[3]
array[0] = 1;

これらの例では配列名はarrayで添え字は[]で囲まれた数字になる。
また配列は連続してメモリアドレスを確保することによって、それぞれのデータへのアクセスを素早く行うことができる。
また配列にはジャグ配列、連想配列、ArrayListなどいろいろな種類があるが、今回は普通の配列についてのみ扱っていく。

##コンピュータのメモリ構造
細かく話すといろいろな内容があるのだろうが、今回必要なのは主に一つ。ノイマン型コンピュータはそれぞれのアドレスにユニークな値が設定されており、その構造は線形とみなすことができる。

#配列によるメモリ確保
前述の通り配列はメモリアドレスを連続して確保し、その結果処理にかかる時間を短縮している。
##一次元配列
まず初めに一次元配列においてのメモリの確保について考えてみる。
文字通り一次元配列とは線形であり、コンピュータのメモリもまた線形であるため、配列の要素がそのままメモリに格納格納されている。ただし一つの要素が占有するメモリのサイズは配列の型に依存する。例えば整数型は4-bitのため、４つのメモリーアドレスを使用している。

one_dimensional_array_memory_allocation.cpp

int main(){
	int size = 5,
		array[size];
	
	for(int i = 0; i< size; i++){
		std::cout << "address of array[" << i << "]: " << &array[i] << std::endl;
	}
	
	return 0;
}

この画像において、メモリーアドレスは１６進数であらわされており、メモリーアドレスが４ずつ増えていることがわかる。

このとき、メモリアドレスは

addrss(array[i])=addrss(array[min])+\left(i-start\right) \cdot elementSize

の数式で求めることができます。
ここではaddrss(array[0])は配列の始まり、(i-start)が求めたい配列の位置引く配列の始まりの数字(多くの場合は0)、そしてelementSizeがその配列が扱う要素一つの大きさを表しています。
実際にこの式をつかって上のプログラムのarray[3]のアドレスは

addrss(array[3])=(0x6ffdb0)_{16} +\left(\left(3-0\right) \cdot 4\right)_{16}
              \\=(0x6ffdb0)_{16} + (c)_{16}
              \\=(0x6ffdbc)_{16}

と求めることができる。
##二次元配列
二次元配列は行と列、二つの向きがあるため、一次元配列とは異なりメモリに格納するとき行の要素をすべてメモリに入れ次の行の要素を入れ始めるのか、列の要素をすべてメモリに格納し次の列の要素を入れていくのか。
このように行と列どちらをメインにして挿入するのか、これらをRow major order(列優先)、Column major order(行優先)と呼ぶ。

²

Row major orderを導入している言語にはC、C++、Paskalなどが、Column major order採用している言語にはFortran、MATLAB、Rなどがある。

以下が実際のC++の二次元配列でのメモリ使用の例である。

two_dimentional_array_memory_alloation.cpp

int main(){
	int rowSize = 5,
		colSize = 5,
		array[rowSize][colSize];
	
	std::cout << "The addrss of " << rowSize << " by " << colSize << " array is below:\n\n";
	
	std::cout << "\t";
	for(int i = 0; i < colSize; i++)	
		std::cout << "Column " << i << " ";
	std::cout << std::endl;
	
	for(int i = 0; i < rowSize; i++){
		std::cout << "Row " << i << ":  "; 
		
		for(int j = 0; j < colSize; j++)
			std::cout << &array[i][j] << " ";
			
		std::cout << std::endl;
	}
	
	return 0;
}

この画像からわかるようにC++ではすべての列を一直線に並べることで、線形であるメモリへのデータの格納を可能としている。

C++とは異なり、MATLABなどのColumn-major orderを採用している言語では、すべての行を直線に並べメモリへとデータを保存している。

これらのRow major order(列優先)、Column major order(行優先)も一次元配列と同様に数式によって特定の要素のアドレスを求めることができる。

Row-major

addrss(array[i][j])\\
=addrss(array[min(1)][min(2)])\\
+\left(\left(i-min(1)\right) \cdot size(2) + j-min(2)\right) \cdot elementSize

min(1)、min(2)がi,jそれぞれの取りうる最小の値、size(2)が行の取りうる最大の値、そしてelementSizeが要素一つの大きさを表す。
この計算式は一次元配列に比べ若干複雑なため、説明を受けようと思う。
まずはaddrss(array[min(1)][min(2)])だが、これは単純に配列の始まりのアドレスを指定している。
((i−min(1))⋅size(2)+j−min(2))⋅elementSizeでは(i−min(1))⋅size(2)でiの真上の列までの要素の数を、j−min(2)でiの列のjの直前までの要素の数をカウントし、その二つを足し要素の大きさをかけることで、addrss(array[i][j])の位置を求めている。

Column major

addrss(array[i][j])\\=addrss(array[min(1)][min(2)])+\left(\left(i-min(1)\right) \cdot size(2) + j-min(2)\right) \cdot elementSize

##三次元配列
言語によって差があるかもしれないが、今回はC++の場合について解説していく。
三次元配列ではZ軸方向にある要素を手前からメモリに格納していき、Row majorの動きに従いメモリを割り当てていく。

three_dimentional_array_memory_alloation.cpp

#include <iostream>
using namespace std;

int main(){
	int row = 3,
		col = 3,
		dep = 3;
	int array[row][col][dep];
	
	cout << " The addrss of 3D array is below:\n\n";
	
	for(int k = 0; k < dep; k++){
		cout << " Depth" << k << "\n\t";
		
		// Display the Column number
		for(int n = 0; n < col; n++)	
			cout << "Column " << n << " ";
		
		cout << endl;
		
		for(int i = 0; i < row; i++){
			// Display the Row number
			cout << " Row " << i << ": ";
		
			for(int j = 0; j < col; j++){
				cout << &array[i][j][k] << "  ";
			}
			
			cout << "\n\n";
		}
	}
	return 0;
}

この画像よりわかるようにC++では0.0.0(Row, Column, Depth)が最初に、次に0.0.1、そして0.0.2とメモリが確保されていることがわかる。このメモリ確保を視覚的にわかりやすくしたものが以下の図である。³

addrss(array[i][j][k])\\
=addrss(array[min(1)][min(2)][min(3)])\\
+\left(\left(\left(i-min(1)\right) \cdot size(3) + j-min(2)\right) \cdot size(2) + (k-min(3)\right) \\
 \cdot elementSize

#まとめ
プログラムが配列のメモリを確保する際にここで示した、またはそれに近しい式を用いることで、メモリアドレスを求めスペースを取得することを可能にしている。
注釈の使い方がよくわからない。

1. Sebesta, Robert W. Concepts of Programming Languages. Pearson, 2016. ↩

2. https://en.wikipedia.org/wiki/Row-_and_column-major_order ↩

3. https://eli.thegreenplace.net/2015/memory-layout-of-multi-dimensional-arrays/
   このとき配列のメモリアドレスは、以下の式を用いることで求めることができる。 ↩