Javaで0と1だけの配列を効率的に保存する

Question

1と0の配列をJavaで最も効率的に格納する方法は何ですか？

Answer 1

答えは、配列のサイズを事前に知っているかどうか、データがどれほど疎かランダムであるかによって異なります。

最も効率的なストレージを探している場合は、生の0と1を保存する代わりにデータを圧縮する必要があります。一般に良い圧縮アルゴリズムの1つはHuffman Codingですが、特にデータがランダムな場合は必ずしも「最良」であるとは限りません。 implementation hereが見つかります。

元の質問に戻り、生の値を保持したいと仮定します。最も効率的なストレージは、アレイのサイズを事前に知っているかどうかによって異なります。固定サイズの場合は、byteプリミティブの数を作成できます。これらのそれぞれは、正確に1バイトと、それが格納されているオブジェクトのオーバーヘッドを取ります。必要に応じて、short,int、またはlongを使用して2,4,8バイトをグループ化すると、変数の数を減らすことができます。これらの変数を他の変数を持つクラスのメンバとして含める場合、オブジェクト自体がオーバーヘッドのために8バイトをとり、サイズは常に8バイトの倍数になるため、使用する型に違いがあります。それで不足している変数は、複数の8バイトに埋め込まれます。

任意のサイズの配列（独自の12バイトのオーバーヘッド、オブジェクトの場合は8、配列の長さの場合は4）が必要な場合は、答えはbyte[]の配列であり続けます。あなたの1と0です。しかし、JVMは8バイトのチャンクでメモリを割り当てますので、1〜4バイトはintのメモリフットプリントになりますので、byte[]の配列はshort[]、またはint[]のメモリフットプリントと最終的に一致し、実際に配列を割り当てる必要はありません（すべてのビットを効率的に使用することができる限り、long[]は、12バイトのオブジェクトオーバーヘッドと16バイトの割り当てのため、他の整数型の配列よりも8バイト余分になります四捨五入一日の終わりに。

が、しかし、読みやすさ/使いやすさは、おそらくメモリ使用量を切り札。BitSet店は、ボンネットの下にlong[]などの値と友好アクセス方法を持っているし、最小限に抑えるために、おそらくここに最良の選択であります（厳密ではありませんが、実用的な目的には十分です）メモリフットプリント。

boolean[]は、CPUを処理するのが最も速いでしょうが、プリミティブな整数型として8倍のメモリを消費します。

Answer 2

あなたはBitSetに行っていただきたいと思います。私はビットを格納する効率的な方法だと思う。 https://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html

いますが、

Answer 3

として偽の0と1を真として扱う必要があり、私はあなたが最も「0の後、」1 'のを持っている場合、ほとんどの最もスペース効率的な方法は、バイナリ行列を格納すると思う、sparse matrixを使用しています。 疎な行列では、交差リスト構造を使用して '1'値のみを表す必要があります。

GitHubにいくつかの実装があります。