Java の非常にコンパクトな Bitarray

Question

Java で高密度の可変長 bitarray を格納する非常にコンパクトな方法を探しています。今、私が使っているのは、 BitSet, 、しかし平均的には使用しているようです 1.5*n ビット サイズのビット ベクトルの記憶領域 n. 。通常、これは問題ではありませんが、この場合、格納されている bitarray はアプリケーションのメモリ フットプリントのかなりの部分を占めます。したがって、それらをもう少し小さくすることが非常に役立ちます。

BitSet に必要なスペースは、データ構造をサポートするために使用される Long 配列が、より多くのビットを保持するために拡張されるたびに 2 倍になる傾向があるためと思われます。

// BitSet's resizing code
private void ensureCapacity(int wordsRequired) {
  if (words.length < wordsRequired) {
    // Allocate larger of doubled size or required size
    int request = Math.max(2 * words.length, wordsRequired);
    words = Arrays.copyOf(words, request);
    sizeIsSticky = false;
  }
}

バックエンドのデータ構造をより控えめにスケーリングする独自の BitSet の代替実装を作成することもできます。ただし、標準クラス ライブラリに既に存在する機能を複製する必要がない場合は、複製したくありません。

Answer 1

あなたはコンストラクタBitSetを使用してBitSet(int nbits)を作成する場合は、

あなたは、容量を指定することができます。あなたは、容量間違っを推測し、越える場合は、サイズを2倍になります。

BitSetクラスはプライベートで、およびwriteObjectおよびクローン（）によって呼び出されtrimToSizeメソッドを持っています。あなたがオブジェクトを複製、またはそれをシリアル化した場合、それは（ensureCapacityメソッドを通してそれを拡大上のクラスを想定）正しい長さにトリミングされます。

Answer 2

あなたは圧縮されたBitSetの選択肢の恩恵を受ける可能性があります。例えば参照してください。

https://github.com/lemire/javaewahする

http://roaringbitmap.org/する