なぜこのコードはあまりにも多くのメモリを必要としますか

Question

現在、オンラインプログラミングコンテストの問題を解決しようとしています。このコンテストでは、プログラムの制限は64メガバイトです。

私はこのように動作しますクラスdeclararationのフィールドの部分を持ってJavaでプログラムを書いた：

private int[] sizes = new int[1024]; // 4096 bytes 
private boolean[][] compat = new boolean[1024][1024]; // 128 kb 
private boolean[][] compat2 = new boolean[1024][1024]; // 128 kb 

private long[][][] dp = new long[29000][51][2]; // About 3*8 = 24 megabytes 
private int [][] masks = new int[29000][2]; // About 240 kb 
private int avail = 0; 
private int avail2 = 0; 
private int[] positions = new int[500000]; // About 2 megabytes 
private int[][] ranges = new int[29000][2]; // About 240 kb 
private int[][] maskToPos = new int[1024][1024]; // About 4 megabytes 
private int[][][] init = new int[29000][51][2]; // About 3*4 = 12 megabytes 

さて、このクラスは、追加せずに、その内部に本体のみの手順と、いくつかのサイクルを持っています配列が宣言されています（サイクルを反復する変数）。しかし、私はローカルマシン上でこのコードを-Xmx64mキーで実行しようとしましたが、OutOfMemoryErrorがあります。それはキー-Xmx128mで実行するだけでした。

また、私はオンラインサーバーを立ち上げようとしましたが、同じエラーが発生し、私のプログラムが約148460 kbで使用したという追加情報も与えました。

なぜそんなに？私が上の部分から計算できる限り、それは約40メガバイトを使うべきです。コメントにこの計算に何か問題はありますか？

Answer 1

これら二つは最大のキラーです：第二を見て

private long[][][] dp = new long[29000][51][2]; // About 3*8 = 24 megabytes 
private int[][][] init = new int[29000][51][2]; // About 3*4 = 12 megabytes 

は、例えば...それは12メガバイトではありません。 29000 int[][]オブジェクト、があり、それぞれには、2つの整数を含む51 int[]オブジェクトへの参照が含まれています。

int[][]オブジェクトのサイズがそれぞれ51 * 4 + 16 = 220バイトであることを意味する配列自体（32ビットの参照サイズと16バイトのオーバヘッド）については、int[]オブジェクトそれぞれ24バイトのサイズです。しかし、それらの24バイトオブジェクトの29000 * 51を持っています - これは35MBだけです...次に29000 int[][]オブジェクトがあります。これはさらに6MBです...（それから、トップレベルの配列自体があります約120K）

基本的に、Javaには多次元配列がないことを覚えておく必要があります。つまり、配列の配列を持ち、各配列は個別のオーバーヘッドを持つオブジェクトです。

private int[] init = new int[29000 * 51 * 2]; 

の代わりに、適切なオフセットを使用することをおすすめします。 （dpの場合はの値ではなくの値ではなく、さらに悪い値であるため、29000 * 51アレイのそれぞれは、24ではなく32バイト以上となります。）だけでも、ディメンションだろうヘルプ治療した順序逆転

：これらの変数のそれぞれについて、今

private long[][][] dp = new long[2][51][29000]; 
private int[][][] init = new int[2][51][29000]; 

を、1つのトップレベルのアレイ・オブ・アレー・オブ・アレーがあります、 2アレイアレイ、およびlongまたはintの102アレイ。これは、ロットに相当します。

他の計算も間違っていますが、この2つの配列の配列の配列は最悪です。

Answer 2

Javaの多次元配列は実際の多次元配列ではないという問題があります。それらがあれば、Javaは[x、y]表記をサポートします。しかし、それはしません。 Javaの多次元配列は配列の配列として実装されるためです。だから、new boolean[1024][1024]は実際に1024個の配列オブジェクトであり、それぞれに1024個のブール値が入っています。 （それぞれ1KB）

私はどのディメンションがメジャーなのか、マイナーなのか覚えていませんが、プログラムがメモリ不足であると判断して、最初のディメンションはおそらく大きなものです。したがって、new long[29000][51][2]は29000 * 51 = 1479000の配列オブジェクトであり、それぞれ2つのlong値を含みます。したがって、非常に多くのオブジェクトで、オブジェクトごとのオーバーヘッドを考慮すると、それを忘れてしまいます！

Answer 3

上記のとおり、long[29000][51][2]は24メガバイトを超えます。あなたはこのように、配列の最後に最大寸法を移動することによって、メモリの量を減らしてみてくださいすることができます

private long[][][] dp = new long[51][2][29000]; 

これは、プログラミングコンテストにによって鳴きためにあなたのプログラムのために十分かもしれません。

Answer 4

マイナーな提案：すべての宣言を「最終的」にしてみます。大きな配列は、領域が見つかるだけでなく、連続したスペースが必要であるため、メモリ割り当てに問題を引き起こします。 Javaはスペースを作るために物事を動かすことができますが、時間がかかりすぎると理論上利用可能な場合でもメモリ不足の例外がスローされます。あなたは、あなたのすべての記憶を前面につかんで、プログラムが終了するまでそれを保つことによって、この問題を回避しているようです。 "final"を使用すると、JVMはあなたがこれについて深刻であることを知り、恐らくそれがあなたを助けるような方法でスペースを割り当てさせるようにします。

これはJVMには役立ちません。私は、ここ数年、Javaがひどく巧妙になってきていることを発見しました。最終的なものとそうでないものについて教えていただく必要はありません。しかし、人々はdoを聞く必要があります。 "final"を使用すると、あなたと他の誰かが、コード内の別の場所でpositions = new int[500010];のようなステートメントを使用して、誤ってスペースを再割り当てすることからコードを変更し、JVM /ガベージコレクタを圧倒します。