Rất nhỏ gọn Bitarray trong Java

Question

Tôi đang tìm một cách rất nhỏ gọn để lưu trữ một bitarray độ dài biến dày đặc trong Java. Ngay bây giờ, tôi đang sử dụng BitSet, nhưng dường như sử dụng trung bình 1.5 * n bit dung lượng lưu trữ cho một bit bit có kích thước n. Thông thường, đây không phải là một vấn đề, nhưng trong trường hợp này bitmap được lưu trữ là một phần khá quan trọng trong bộ nhớ của ứng dụng. Vì vậy, nó sẽ thực sự giúp đỡ để có được chúng được một chút nhỏ hơn.

Không gian theo yêu cầu của BitSet có vẻ là do thực tế rằng các mảng thép dài sử dụng để sao cấu trúc dữ liệu có xu hướng tăng gấp đôi mỗi lần nó được mở rộng để tổ chức nhiều bit:

// 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; 
    } 
} 

tôi có thể viết thực hiện thay thế của riêng tôi về BitSet giúp cân bằng cấu trúc dữ liệu phụ trợ một cách thận trọng hơn. Nhưng, tôi thực sự ghét chức năng trùng lặp đã có trong thư viện lớp chuẩn nếu tôi không phải làm như vậy.

Answer 1

Nếu bạn tạo BitSet bằng cách sử dụng hàm tạo BitSet(int nbits) bạn có thể chỉ định dung lượng. Nếu bạn đoán công suất sai, và đi qua, nó sẽ tăng gấp đôi kích thước.

Lớp BitSet có phương thức trimToSize riêng tư và được gọi bởi writeObject và clone(). Nếu bạn sao chép đối tượng của mình, hoặc sắp xếp nó, nó sẽ cắt nó thành độ dài chính xác (giả sử lớp mở rộng nó thông qua phương thức EnsureCapacity).

Answer 2

Bạn có thể hưởng lợi từ các lựa chọn thay thế BitSet được nén. Xem ví dụ:

https://github.com/lemire/javaewah

http://roaringbitmap.org/