2重forループのプログラムを書く時に注意すべきこと

forループって便利ですよね！
2次元配列を処理するときなんかに、2重forループがよく使われますね。
今回はそのforループの意外な仕組みを紹介します。

同じことをした筈なのに…？

こちらに、ごく簡単な2重forループのコードを用意しました。

ForTestClass1.java

public class ForTestClass1 {

	public static final int _arrSize = 3000;
	
	public static long test(){
		
		int[][] array = new int[_arrSize][_arrSize];
		
		long start = System.currentTimeMillis();
		// 2重forループを使い、配列に0をひたすら代入
		for(int x=0; x<_arrSize; x++){
			for(int y=0; y<_arrSize; y++){
				array[x][y] = 0;
			}
		}
		long stop = System.currentTimeMillis();

		// 2重forループの作業にかかった時間を返却
		return (stop-start);
		
	}
	
	public static void main(String[] args){
		
		long sum = 0;
		
		// テストを10回行う
		for (int i=0; i<10; i++){
			long time = test();
			System.out.println(time + "ms かかりました。");
			sum += time;
		}
		
		// 平均時間を表示
		System.out.println("平均 " + (sum/10) + "ms でした。");
		
	}
	
}

3000×3000の2次配列の各要素に、0を代入する作業を10セット行い、
かかった時間の計測を行うプログラムです。

実行結果はこのようになりました。

38ms かかりました。
23ms かかりました。
22ms かかりました。
23ms かかりました。
22ms かかりました。
23ms かかりました。
22ms かかりました。
22ms かかりました。
22ms かかりました。
23ms かかりました。
平均 24ms でした。

では、以下のように編集するとどうでしょう。

ForTestClass1.java（編集）

public class ForTestClass1 {

	public static final int _arrSize = 3000;
	
	public static long test(){
		
		int[][] array = new int[_arrSize][_arrSize];
		
		long start = System.currentTimeMillis();
		// 2重forループを使い、配列に0をひたすら代入
		for(int x=0; x<_arrSize; x++){
			for(int y=0; y<_arrSize; y++){
				array[y][x] = 0;  // !! x と y を逆にしました
			}
		}
		long stop = System.currentTimeMillis();

		// 2重forループの作業にかかった時間を返却
		return (stop-start);
		
	}
	
	public static void main(String[] args){
		
		long sum = 0;
		
		// テストを10回行う
		for (int i=0; i<10; i++){
			long time = test();
			System.out.println(time + "ms かかりました。");
			sum += time;
		}
		
		// 平均時間を表示
		System.out.println("平均 " + (sum/10) + "ms でした。");
		
	}
	
}

2重forループの中身を、

array[x][y] = 0;

から

array[y][x] = 0;

に変えただけです。
x と y の順番が逆になっただけで、作業内容自体は変わっていません。

編集後のプログラムの実行結果は以下のようになりました。

119ms かかりました。
100ms かかりました。
100ms かかりました。
100ms かかりました。
99ms かかりました。
100ms かかりました。
99ms かかりました。
101ms かかりました。
101ms かかりました。
100ms かかりました。
平均 101ms でした。

結果的には同じことを行ったはずなのに、
平均 24ms→平均 101ms と、約4倍になってしまいました！

キャッシュの扱い方がミソ

キャッシュというものをご存知ですか？
プログラムがメインメモリにアクセスするのは時間がかかるので、
容量は少ないけれど高速なキャッシュメモリというものを活用して
CPUは効率よく、素早くプログラムを実行します。

イメージとしてはこのような感じです。
なるべく、キャッシュ⇔メインメモリ間の通信を減らし、
高速な作業をするような仕組みになっています。

そのため、築一メインメモリへの書き込みは行わず、
キャッシュメモリに書きこむ内容をある程度溜めておき、
一気にキャッシュから複数のデータをメインメモリに転送します。

しかしこの裏技が使えるのは、メインメモリ上で書き込み先のアドレスが連続している場合のみなのです。

3000×3000の配列 array の要素は、今回の場合、以下のような配置で格納されていたとイメージできます。
（Javaの場合、実行環境のJava VMの仕様で格納の仕方は変化するそうです）

このように、
array[x][0], array[x][1]… は連続していますが、
array[0][y], array[1][y]… は離れて格納されています。

そのため、あとから実行したプログラムはキャッシュをうまく使うことができず、
結果、実行内容は同じなのに、非効率的なプログラムになっていたわけです。

もちろん読み込む場合も一緒

先程のプログラムはデータの書き込みを行うものでしたが、
もちろんデータを読み込む場合も一緒です。
近くに格納されているデータは一気にまとめてキャッシュにロードすることができます。

先ほどのプログラムを少しだけいじって、読み込む例のプログラムにしてみました。
配列の要素を合計していくプログラムです。
（配列の全要素には初期値として 0 が入っているので、意味のないプログラムですが……）

まずは連続してアクセスする方から。

ForTestClass2.java

public class ForTestClass2 {
	
	public static final int _arrSize = 3000;
	
	public static long test(){

		int[][] array = new int[_arrSize][_arrSize];
		int tmp=0;
		
		long start = System.currentTimeMillis();
		// 2重forループを使い、配列に0をひたすら代入
		for(int x=0; x<_arrSize; x++){
			for(int y=0; y<_arrSize; y++){
				tmp += array[x][y];
			}
		}
		long stop = System.currentTimeMillis();

		// 2重forループの作業にかかった時間を返却
		return (stop-start);
		
	}
	
	public static void main(String[] args){
		
		long sum = 0;
		
		// テストを10回行う
		for (int i=0; i<10; i++){
			long time = test();
			System.out.println(time + "ms かかりました。");
			sum += time;
		}
		
		// 平均時間を表示
		System.out.println("平均 " + (sum/10) + "ms でした。");
		
	}

}

実行結果

47ms かかりました。
22ms かかりました。
22ms かかりました。
23ms かかりました。
23ms かかりました。
22ms かかりました。
22ms かかりました。
23ms かかりました。
23ms かかりました。
22ms かかりました。
平均 24ms でした。

最初の例の時と一緒のように、
2重forループの中の x と y を逆にして実行してみます。

ForTestClass2.java（編集）

public class ForTestClass2 {
	
	public static final int _arrSize = 3000;
	
	public static long test(){

		int[][] array = new int[_arrSize][_arrSize];
		int tmp=0;
		
		long start = System.currentTimeMillis();
		// 2重forループを使い、配列に0をひたすら代入
		for(int x=0; x<_arrSize; x++){
			for(int y=0; y<_arrSize; y++){
				tmp += array[y][x];  // !! x と y を逆にしました
			}
		}
		long stop = System.currentTimeMillis();

		// 2重forループの作業にかかった時間を返却
		return (stop-start);
		
	}
	
	public static void main(String[] args){
		
		long sum = 0;
		
		// テストを10回行う
		for (int i=0; i<10; i++){
			long time = test();
			System.out.println(time + "ms かかりました。");
			sum += time;
		}
		
		// 平均時間を表示
		System.out.println("平均 " + (sum/10) + "ms でした。");
		
	}

}

実行結果

117ms かかりました。
109ms かかりました。
108ms かかりました。
107ms かかりました。
108ms かかりました。
108ms かかりました。
107ms かかりました。
108ms かかりました。
107ms かかりました。
109ms かかりました。
平均 108ms でした。

最初の例ほぼ同じく、平均 24ms→平均 108ms と約4倍になりました。

わざわざそんなプログラム書かないけど……

まあ普通、わざわざ x と y を逆にするようなわかりにくいプログラムは書きませんよね。
しかし「意識して書かないようにする」ことが大事だと思います。

論文の式を実装する時や、学校の課題を解くとき、
ついつい参照している文の通りに書いてしまいませんか？
その文が不連続なforループを導くものだったらどうしますか？
そういう時に、わざわざ実行時間のかかる書かないようにしましょう。

また、記事中でも書きましたがプログラムの動きは実行環境によって変わります。
今回は array[x][y] の方が高速でしたが、別の実行環境では、array[y][x] と書く方が高速になる可能性はあります。
大切なのは、自分の実行環境で最適なプログラムを書くことです。
その中で、このような些細なことでも実行時間が大きく変わることもあるのだなあ、というような理解をしていただけたら幸いです。