जावा में बहुत कॉम्पैक्ट बिटर्रे

Question

मैं जावा में घने परिवर्तनीय लंबाई बिटरैरे को संग्रहित करने का एक बहुत ही कॉम्पैक्ट तरीका ढूंढ रहा हूं। अभी, मैं BitSet का उपयोग कर रहा हूं, लेकिन ऐसा लगता है कि आकार एन के थोड़ा वेक्टर के लिए भंडारण स्थान के औसत 1.5 * एन बिट्स पर उपयोग किया जाता है। आम तौर पर, यह कोई समस्या नहीं है, लेकिन इस मामले में बिटरएयर संग्रहीत किए जा रहे हैं, एप्लिकेशन की स्मृति पदचिह्न एक बहुत महत्वपूर्ण हिस्सा हैं। तो, यह वास्तव में उन्हें थोड़ा छोटा होने में मदद करेगा।

अंतरिक्ष BitSet के लिए आवश्यक तथ्य यह है कि डेटा संरचना वापस करने के लिए इस्तेमाल किया देशांतर की सरणी हर बार विस्तार किया जाता है दोगुना करने के लिए अधिक बिट्स पकड़ आदत की वजह से हो रहा है:

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

मैं लिख सकता है बिटसेट के अपने स्वयं के वैकल्पिक कार्यान्वयन जो बैकएंड डेटा संरचना को अधिक रूढ़िवादी रूप से स्केल करते हैं। लेकिन, मैं वास्तव में मानक वर्ग पुस्तकालयों में पहले से ही कार्यक्षमता को डुप्लिकेट करने से नफरत करता हूं यदि मुझे ऐसा नहीं करना है।

Answer 1

यदि आप निर्माता BitSet(int nbits) का उपयोग कर बनाते हैं तो आप क्षमता निर्दिष्ट कर सकते हैं। यदि आपको लगता है कि क्षमता गलत है, और आगे बढ़ें, तो यह आकार को दोगुना कर देगा।

BitSet कक्षा में trimToSize विधि है जो निजी है, और इसे लिखने के लिए ऑब्जेक्ट और क्लोन() कहा जाता है। यदि आप अपनी ऑब्जेक्ट क्लोन करते हैं, या इसे क्रमबद्ध करते हैं, तो यह इसे सही लंबाई तक ट्रिम कर देगा (कक्षा को सुनिश्चित करने के लिए क्लास को सुनिश्चित करने के लिए इसे सक्षम करें)।

Answer 2

आपको संपीड़ित बिटसेट विकल्पों से लाभ हो सकता है। है उदाहरण के लिए देखें:

https://github.com/lemire/javaewah

http://roaringbitmap.org/