14

Java で高密度の可変長 bitarray を格納する非常にコンパクトな方法を探しています。現在、私は を使用していますが、サイズnBitSetのビット ベクトルに対して平均1.5*n ビットのストレージ スペースを使用しているようです。通常、これは問題にはなりませんが、この場合、格納されるビット配列はアプリケーションのメモリ フットプリントのかなりの部分を占めます。したがって、それらを少し小さくすることは本当に役立ちます。

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 の独自の代替実装を作成できます。しかし、必要がなければ、標準クラス ライブラリに既にある機能を複製するのは本当に嫌です。

4

2 に答える 2

20

BitSetコンストラクタを使用して作成BitSet(int nbits)すると、容量を指定できます。容量を間違えてオーバーすると2倍になります。

このBitSetクラスtrimToSizeにはプライベートなメソッドがあり、writeObject および clone() によって呼び出されます。オブジェクトを複製またはシリアライズすると、オブジェクトは正しい長さにトリミングされます (クラスが ensureCapacity メソッドを介してオーバーエクスパンドしたと仮定します)。

于 2010-01-19T04:24:49.130 に答える
5

圧縮された BitSet の代替手段が役立つ場合があります。例を参照してください。

https://github.com/lemire/javaewah

http://roaringbitmap.org/

于 2012-11-02T17:38:48.583 に答える