Java에서 매우 컴팩트 한 Bitarray

Question

Java에서 밀도가 높은 가변 길이의 bitarray를 저장하는 매우 컴팩트 한 방법을 찾고 있습니다. 지금은 BitSet을 사용하고 있지만, 평균 크기가 * 1.5 비트인데, n 비트 벡터의 저장 공간은입니다. 일반적으로 이것은 문제가되지 않지만,이 경우 저장된 비트 배열은 응용 프로그램의 메모리 사용량 중 중요한 부분입니다. 그래서, 그것들을 조금 더 작게 만드는 것이 도움이 될 것입니다.

비트 세트에 필요한 공간 인해 데이터 구조를 백업하는 데 사용 long 치의 배열이 더 많은 비트 개최가 확장 될 때마다 두 배로하는 경향이 있다는 사실을 것 같다

:

// 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(int nbits) 생성자를 사용하여 BitSet을 만드는 경우 용량을 지정할 수 있습니다. 용량을 잘못 추측하고 넘어 가면 크기가 두 배가됩니다.

BitSet 클래스에는 private이며, writeObject 및 clone()에 의해 호출되는 trimToSize 메서드가 있습니다. 객체를 복제하거나 직렬화하면 올바른 길이로 자릅니다 (ensureCapacity 메소드를 통해 클래스를 확장 한 경우).

Answer 2

압축 된 BitSet 대안의 이점이 있습니다. 예를 들어, 참조 :

https://github.com/lemire/javaewah

http://roaringbitmap.org/