Java'da Çok Kompakt Bitarray

Question

Java'da yoğun değişken uzunluklu bitarray depolamanın çok kompakt bir yolunu arıyorum. Şu anda, BitSet kullanıyorum, ancak n boyutunda bir bit vektörü için ortalama 1.5 * n bitleri depolama alanı kullanıyor görünmektedir. Tipik olarak, bu bir problem değildir, ancak bu durumda depolanan bitardamarlar, uygulamanın bellek ayak izinin oldukça önemli bir parçasıdır. Yani, onları biraz daha küçük olmaya yardımcı olur.

BitSet gerektirdiği boşluk, veri yapısı geri almak için kullanılan uzun ürünler dizisi daha fazla bit tutmak için genişletilmişse her çift için eğilimi göstermesine bağlı gibi görünmektedir

:

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

I yazabiliriz Arka uç veri yapısını daha muhafazakar bir şekilde ölçekleyen kendi alternatif uygulamam. Ancak, gerekmiyorsa standart sınıf kitaplıklarında bulunan işlevleri çoğaltmaktan gerçekten nefret ediyorum.

Answer 1

oluşturucu BitSet(int nbits) yapıcısını kullanarak oluşturursanız, kapasiteyi belirtebilirsiniz. Kapasiteyi yanlış tahmin ederseniz ve giderseniz, boyutu iki katına çıkar.

BitSet sınıfında, özel olan ve writeObject ve clone() tarafından çağrılan bir trimToSize yöntemine sahiptir. Nesnenizi klonlarsanız veya serileştirirseniz, doğru uzunluğa (sınıfın overclock'u, warrantyCapacity yöntemiyle genişletildiğini varsayarak) keser.

Answer 2

Sıkıştırılmış BitSet alternatiflerinden yararlanabilirsiniz. Örneğin bakınız:

https://github.com/lemire/javaewah

http://roaringbitmap.org/