मैं "संपीड़ित सरणी"/"संपीड़ित वेक्टर" वर्ग (नीचे विवरण) बनाना चाहता हूं, जो यादृच्छिक डेटा को अधिक या कम स्थिर समय के साथ एक्सेस करने की अनुमति देता है।यादृच्छिक डेटा एक्सेस के साथ संपीड़ित वेक्टर/सरणी वर्ग
"अधिक या कम स्थिर समय" का अर्थ है कि यद्यपि तत्व पहुंच का समय स्थिर नहीं है, लेकिन जब मैं सरणी के कुछ बिंदु के करीब आता हूं तो इसे बढ़ाना नहीं चाहिए। अर्थात। कंटेनर को एक और तत्व प्राप्त करने के लिए महत्वपूर्ण गणना नहीं करना चाहिए (जैसे कि "अंतिम तत्व प्राप्त करने के लिए एक बार फिर से सब कुछ दबाएं" और "पहले प्राप्त करने के लिए लगभग कुछ भी नहीं करें")। संकुचित डेटा के हिस्सों में विभाजित सरणी द्वारा संभवतः हासिल किया जा सकता है। अर्थात। एक तत्व तक पहुंचने से "औसत समय" + - कुछ विचलन लेना चाहिए। मैं कह सकता हूं कि मैं सबसे अच्छा केस एक्सेस टाइम और सबसे खराब केस एक्सेस समय औसत पहुंच समय के अपेक्षाकृत निकटतम होना चाहता हूं।
मेरे विकल्प क्या हैं (उपयुक्त एल्गोरिदम/पहले से उपलब्ध कंटेनर - यदि कोई हैं तो)?
कंटेनर विवरण:
- कंटेनर (जैसे std :: वेक्टर के रूप में)
- एक बार कंटेनर आरंभ नहीं हो जाता समान तत्वों की एक रेखीय सरणी के रूप में कार्य करता है, डेटा स्थिर है और कभी नहीं बदलता। कंटेनर को केवल पढ़ने के लिए पहुंच प्रदान करने की आवश्यकता है।
- कंटेनर को सरणी/std :: vector - i.e. ऑपरेटर के माध्यम से उपयोग किए जाने वाले मानों का व्यवहार करना चाहिए [], वहाँ .size(), आदि
- यह अच्छा होगा अगर मैं इसे टेम्पलेट क्लास के रूप में बना सकता हूं।
- डेटा तक पहुंच निरंतर समय-समय पर होनी चाहिए। मुझे हर तत्व के लिए एक ही एक्सेस समय की आवश्यकता नहीं है, लेकिन मुझे अंतिम तत्व प्राप्त करने के लिए सब कुछ डिकंप्रेस नहीं करना चाहिए।
उपयोग उदाहरण:
डेटा पर बाइनरी खोज।
डेटा विवरण:
1. डेटा स्ट्रक्चर ज्यादातर फ्लोट्स और कुछ चींटियों से युक्त होता है। चींटियों की तुलना में अधिक तैरते हैं। कोई संबंध नही।
2. यह संभावना नहीं है कि सरणी में कई समान तत्व हैं, इसलिए डेटा को अनुक्रमणित करना संभव नहीं होगा।
3. एक तत्व का आकार 100 बाइट से कम है।
4. प्रति कंटेनर का कुल डेटा आकार कुछ किलोबाइट्स और कुछ मेगाबाइट्स के बीच है।
5. डेटा स्पैस नहीं है - यह तत्वों का निरंतर ब्लॉक है, उनमें से सभी को असाइन किया गया है, कोई "खाली स्लॉट" नहीं हैं।
संपीड़न का लक्ष्य ब्लॉक को रैम की मात्रा को कम करना है, जबकि असम्पीडित प्रतिनिधित्व की तुलना में सरणी के रूप में असम्पीडित प्रतिनिधित्व की तुलना में, कुछ हद तक उचित पढ़ने के प्रदर्शन को ध्यान में रखते हुए, और तत्वों को सरणी के रूप में यादृच्छिक रूप से एक्सेस करने की अनुमति देता है। अर्थात। डेटा आंतरिक रूप से संकुचित रूप में संग्रहीत किया जाना चाहिए, और मुझे इसे एक्सेस करने में सक्षम होना चाहिए (केवल पढ़ने के लिए) जैसे कि यह एक std :: वेक्टर या समान कंटेनर है।
विचार/राय?
"अधिक या कम" निरंतर समय क्या है? या तो यह स्थिर है, या तो यह नहीं है। अन्यथा दिलचस्प सवाल। क्या आप वाकई कई मौजूदा कंटेनर कक्षाओं के साथ जो कुछ भी चाहते हैं वह नहीं कर सकते हैं? – ereOn
"संपीड़ित" भाग इसमें प्रवेश करता है? आपने उस हिस्से को कभी समझाया नहीं है। क्या आप सिर्फ gzipped blobs, या ऐसा कुछ करने के लिए पॉइंटर्स के वेक्टर का उपयोग कर सकते हैं? या क्या आपका मतलब संकुचित है क्योंकि आपके पास एक स्पैससेट डेटासेट है, इसलिए एक बेवकूफ वेक्टर में बहुत सारे खाली स्लॉट होंगे? – jalf
इसके अलावा आप कहते हैं कि तत्व केवल फ्लोट्स और इनट्स हैं, और यह कि एक तत्व 100 बाइट से अधिक नहीं है। जब तक आप कुछ 800 बिट्स आर्किटेक्चर पर काम नहीं करते हैं, तो आप आखिरी आवश्यकता को छोड़ सकते हैं। – ereOn