java 配列　上限解放

##解決したいこと
javaを使って全探索で問題を解くアルゴリズムを作っています。動的計画法との計算時間の比較を行いたいため非効率であることは承知の上で行っています。しかし、要素数が31個以上で全探索を解くとOutof Memory Errerが起き計算ができなくなります。

配列の上限解放について、解決できるよい方法があれば教えていただけるとありがたいです。

java
1static final int N = 30;	// 製品数
2	static final int W = 20;// 重量上限
3	static int[] w = new int[N]; // 製品iの重量
4	static int[] v = new int[N]; // 製品iの価値
5	static int[] b = new int[N]; // 入れるか入れないかの0-1変数
6	static int i = 0;
7static int allCombi(int[] optimal){
8		System.out.println("全組み合わせとその時の価値合計および重量合計");
9//		int i = 0; // 組み合わせ番号
10		for(int i = 0; i < (int)Math.pow(2.0,N); i++){
11			val[i] = 0;
12			wgt[i] = 0;
13			for(int k = 0; k < N; k++){
14				b[N - k - 1] = (i >>> k & 1) == 1 ? 1 : 0;
15				// 目的関数
16				val[i] += b[k]*v[k]; // val[i] = b[0]*v[0]+b[1]*v[1]+b[2]*v[2]+b[3]*v[3]+b[4]*v[4]+b[5]*v[5];
17				// 重量合計
18				wgt[i] += b[k]*w[k]; // wgt[i] = b[0]*w[0]+b[1]*w[1]+b[2]*w[2]+b[3]*w[3]+b[4]*w[4]+b[5]*w[5];
19			}
20			System.out.printf("%2d %d %d %d %d %d %d %2d %2d\n", i + 1, b[0], b[1], b[2], b[3], b[4], b[5], val[i], wgt[i]);
21			if(max[0] < val[i] && wgt[i] <=W){
22				max[0] = val[i];
23				max[1] = wgt[i];
24				max[2] = i + 1;
25				for(int j = 0; j < N; j++){
26					optimal[j] = b[j];
27				}
28			}
29		}
30		System.out.println();
31		return max[0];
32	}
33String str;
34		i = 0;
35		int sol;
36		String[] s = {"詰めない", "詰める"}; // 解表示用文字列
37		// データの読み込み
38		try{
39			File data = new File("C:\Users\fit-user\Desktop\data1.csv");
40			BufferedReader br = new BufferedReader(new FileReader(data));
41			while((str = br.readLine()) != null){
42				String[] st = str.split(",", 0);
43				w[i] = Integer.parseInt(st[0]);
44				v[i] = Integer.parseInt(st[1]);
45				System.out.printf("%2d %2d %2d\n",i, w[i], v[i]);
46				i++;
47			}
48		}catch(FileNotFoundException e){
49			System.out.println("ファイルが見つかりませんでした．");
50		}catch(IOException e){
51			System.out.println("入出力でエラーが発生しました");
52		}
53				// 全組み合わせ列挙で解く場合
54		System.out.println("全組み合わせ列挙で解いた場合");
55		t0 = System.nanoTime();
56		sol = allCombi(optimal); // 全組み合わせ列挙メソッドの呼び出しと最適値の受け取り
57		System.out.println(max[2] + "番目の組み合わせが最適解");
58		// 最適解の表示
59		for(int i = 0; i < N; i++){
60			System.out.println("製品" + i + ":" + s[optimal[i]]);
61		}
62		System.out.println("最適値：" + sol);
63		System.out.println("重　量：" + max[1]);
64		time = System.nanoTime() - t0;
65		System.out.printf("実行時間...%ntime: %f ms.%n", time/1000000.0);
66

開発環境

開発環境としてはequlipseを使っています。

行動規範の内容に同意します

回答5件

ベストアンサー

valとwgtの定義部分がないためforで回している添字からの推測なりますが、N個の要素に対する全ての組合せ数である2^N(2のN乗)個の要素からなる配列を用意しているのだと思います。31個の場合は2^31個の要素の配列、32個の場合は2^32個の要素の配列ということでしょう。

結論から言うとJavaの言語仕様とJavaVMの制限から不可能です。

まず、Javaの言語仕様として配列の添字はintであるという制限があります。intの最大値は2^31-1ですので、どうやっても0～2^31-1、つまり2^31個の要素の配列しか作れません。さらに、new int[X]とするときのXもintです。ここに入る最大の数は2^31-1であり、結局、2^31-1個の配列が限界になります。

ここにJavaVMの制限が加わります。
参考: Java の配列要素数の上限 - 地平線に行く
64bit環境でも2^31-3が最大であり、それ以上は無理となります。定義部分がないため確実なことは言えませんが、Math.powで2^31を計算してもintにキャストすると2^31-1に丸め込まれますので、その大きさで配列を作ろうとしたのでしょう。しかし、上のJavaVMの制限によりOutOfMemoryErrorが発生したと考えられます。

つまり、JavaとJavaVMと配列を使う限り、どんなにメモリを積んだり、オプションでヒープサイズなどを調整しても、2^31個の要素の配列を作ることは不可能になるということです。なお、longを使えばと思うかも知れませんが、Javaの配列は添字アクセス等がintになるため、結局キャストが必要になり、意味がありません。ArrayListもintであり同じです(そもそもArrayListは内部で配列を使って実装されています)。LinkedListであれば実装上の制限がないように思えますが、size()等がintを使うため、同じと思われます(ここら辺は試してません)。

巨大な配列を作らなくても計算できるアルゴリズムに変更するしかないと思われます。または、かなり遅くなりますが、外部ファイルに配列でやろうとしていたことを入れていくという手段ぐらいしかないかと思います(intの2^31個保存するのに8GBのファイルになりますけど)。

投稿2018/07/11 22:24

編集2018/07/11 22:26