बिटमैप्स (जिसे बिट एरे, बिट वैक्टर आदि भी कहा जाता है) डेटा संरचना है जो आपके दिमाग में तुरंत पॉप हो जाती है जब आवश्यकता होती है एक विशाल डोमेन के लिए बूलियन जानकारी को एक कॉम्पैक्ट में मैप करने की। प्रतिनिधित्व। यह एक बहुत ही लोकप्रिय डेटा संरचना है जब भी मेमोरी स्पेस प्रीमियम पर होता है:OS कर्नेल (मेमोरी पेज, इनोड्स आदि), डिजिटल इमेजिंग आदि।
Redis, एक इन-मेमोरी डेटा स्ट्रक्चर सर्वर होने के नाते, बिट मैनिपुलेशन संचालन के लिए समर्थन प्रदान करता है। हालाँकि, Redis में बिटमैप्स के लिए कोई विशेष डेटा संरचना नहीं है। इसके बजाय, मूल रेडिस संरचना पर बिट स्तर के संचालन का समर्थन किया जाता है:स्ट्रिंग्स। अब, रेडिस स्ट्रिंग्स की अधिकतम लंबाई 512 एमबी है। इस प्रकार, Redis एक बिटमैप के रूप में जो सबसे बड़ा डोमेन मैप कर सकता है वह 2 (512 एमबी =2 बाइट्स =2 बिट) है।
Redis में बिट संबंधित ऑपरेशन दो प्रकार के होते हैं:लगातार समय (O(1)) उदा। किसी विशेष बिट को प्राप्त करने/सेट करने के लिए संचालन और संचालन जो ओ (एन) हैं जो मूल रूप से बिट्स के समूह पर काम करते हैं। इन मामलों में एन बिट्स की लंबाई है जिस पर ऑपरेशन को काम करने की आवश्यकता होगी। आइए कुछ उदाहरण देखें।
कमांड
# SETBIT key offset value: Store bit value 'value' at offset 'offset' for 'key'. O(1) # Returns the original bit value stored at that offset. 127.0.0.1:6379> setbit k 10 1 (integer) 0 # GETBIT key offset: Fetch value of 'offset' in 'key'. O(1) 127.0.0.1:6379> getbit k 10 (integer) 1 127.0.0.1:6379> getbit k 11 (integer) 0 127.0.0.1:6379> getbit k 0 (integer) 0 127.0.0.1:6379> setbit k 9 1 (integer) 0 127.0.0.1:6379> setbit k 8 1 (integer) 0 # And since it is still a generic String, here's a get. 127.0.0.1:6379> get k "\x00\xe0" # "\x00\xe0" -> "0000 0000 111" # BITCOUNT key [start end]: Number of set bits in the range. O(N) # IMPORTANT: start & end are bytes not bits 127.0.0.1:6379> bitcount k (integer) 3 127.0.0.1:6379> set m "meow" OK # meow -> 01101101 01100101 01101111 01110111 127.0.0.1:6379> bitcount m (integer) 21 # BITPOS key bit [start] [end]: 1st position of 1 or 0 in the key in range. O(N) 127.0.0.1:6379> SET mykey "\xff\xf0\x00" OK 127.0.0.1:6379> BITPOS mykey 0 (integer) 12
इसके अलावा ऐसे ऑपरेटर भी हैं जो कुंजी पर ही काम करते हैं, BITOP ऑपरेटर का उपयोग कई कुंजियों के बीच बिट-वार तार्किक संचालन के लिए किया जाता है।
# BITOP operation destkey key [key ...]. O(N) # operation can be AND, OR, XOR and NOT 127.0.0.1:6379> set a "\xff\xff" OK 127.0.0.1:6379> bitop not nota a (integer) 2 127.0.0.1:6379> get nota "\x00\x00" 127.0.0.1:6379> set b "\x0f\x0f" OK 127.0.0.1:6379> set c "\xf0\xf0" OK 127.0.0.1:6379> BITOP OR orbc b c (integer) 2 127.0.0.1:6379> get orbc "\xff\xff" 127.0.0.1:6379> BITOP AND andbc b c (integer) 2 127.0.0.1:6379> get andbc "\x00\x00" 127.0.0.1:6379> BITOP XOR xorbc b c (integer) 2 127.0.0.1:6379> get xorbc "\xff\xff"प्राप्त करें
आंतरिक
चूंकि बिटमैप ऑपरेशंस की अपनी कोई डेटा संरचना नहीं होती है, इसलिए वर्णन करने के लिए कोई विशेष डेटा संरचना नहीं होती है। रेडिस स्ट्रिंग्स को स्वयं बाइनरी सुरक्षित स्ट्रिंग के रूप में कार्यान्वित किया जाता है। रेडिस स्ट्रिंग डेटा संरचना को आंतरिक रूप से सरल गतिशील स्ट्रिंग (एसडीएस) कहा जाता है। यह मूलतः एक देशी char [] . है कुछ अतिरिक्त बहीखाता जानकारी के साथ। कार्यान्वयन विवरण यहां पाया जा सकता है।
बिटमैप फ़ंक्शंस का कार्यान्वयन फ़ाइल में है bitops.c ।
P.S.:महत्वपूर्ण OS और ग्राफिक्स कार्यक्षमता के लिए बिट मैनिपुलेशन एल्गोरिदम के महत्व को देखते हुए, अधिकांश आर्किटेक्चर ऐसे संचालन के लिए विशेष निर्देश प्रदान करते हैं। विभिन्न दिलचस्प कंप्यूटर अंकगणितीय एल्गोरिदम पर पढ़ने के लिए एक अच्छी जगह कालातीत क्लासिक हैकर्स डिलाइट है।
अनुप्रयोग
यह लोकप्रिय GetSpool ब्लॉग एक बड़े डेटा सेट पर रीयल टाइम एनालिटिक्स के लिए बिटमैप के उपयोग का एक बेहतरीन उदाहरण है। यह बिटमैप के क्लासिक उपयोग के मामले का भी एक उदाहरण है:एक बहुत बड़े डोमेन की बूलियन जानकारी को अच्छे प्रदर्शन को बनाए रखते हुए (अपेक्षाकृत) छोटे स्थान में संग्रहीत करना।
साइज आमतौर पर वास्तव में बड़े बिटमैप्स के लिए एक चिंता का विषय है, क्योंकि इस पर सबसे उपयोगी ऑपरेशन O(N) हैं। बड़ी कुंजियों के साथ काम करने से बचने के लिए, Redis प्रलेखन विशाल कुंजियों को कई छोटी कुंजियों में विभाजित करने की अनुशंसा करता है। कुंजी के बड़े होने तक BITCOUNT प्रदर्शन स्वीकार्य रहता है। उस समय, अनुशंसा है कि या तो कुंजियों को विभाजित किया जाए या श्रेणी तर्कों का उपयोग वृद्धिशील रूप से क्वेरी करने के लिए किया जाए। धीमे BITOP संचालन से निपटने की सिफारिश इसे दासों पर चलाने की है। इसलिए, सामान्य तौर पर मध्यम आकार की चाबियों से निपटना और चाबियों को कई चाबियों में विभाजित करके भविष्य की संभावित वृद्धि की योजना बनाना समझ में आता है।
रेडिस सेट बनाम रेडिस बिटमैप
Redis सेट्स और बिटमैप ऑपरेशंस द्वारा प्रदान की जाने वाली कार्यक्षमता की प्रकृति समान है। इसलिए यह अक्सर भ्रमित होता है कि दोनों में से कौन सा दृष्टिकोण बेहतर है। खैर, यह वास्तव में उपयोग के मामले की सटीक प्रकृति पर निर्भर करता है। जाहिर है, यह चर्चा केवल उस तरह के संचालन के लिए मान्य है जो सेट और बिटमैप दोनों हासिल कर सकते हैं।
Redis सेट सामान्य रूप से कुशल और स्केल वेल में होते हैं और जब तक इसका आकार अस्थिर नहीं हो जाता, तब तक यह पसंद की डेटा संरचना होनी चाहिए। रेडिस सेट को प्रबंधित करना भी आसान है, प्रोग्राम और डिबग अधिकांश अनुप्रयोगों के लिए अच्छा काम करेगा। सेट के उपयोग में आसानी को कम करके नहीं आंका जाना चाहिए:बिटमैप्स में हेरफेर करने वाला कोड आमतौर पर पढ़ने, समझने, डीबग करने और बनाए रखने में कठिन होता है। भले ही डोमेन बहुत बड़ा हो, फिर भी सेट उपयुक्त हो सकते हैं। उदाहरण के लिए यदि कोई एप्लिकेशन किसी लोकप्रिय ई-कॉमर्स साइट पर दैनिक विज़िट को ट्रैक करने के लिए है, तो परिणाम अभी भी एक सेट में अच्छी तरह से फिट हो सकते हैं क्योंकि आमतौर पर पूरे उपयोगकर्ता आधार का केवल 5-10% साइट पर प्रतिदिन आएगा। यह स्पष्ट रूप से उस साइट के लिए बदलता है जहां पूरे उपयोगकर्ता आधार का 60% दैनिक लॉगिन करने की उम्मीद है। फिर बड़ी संख्या में कुंजियों पर तार्किक बिट वार संचालन के आकार और प्रदर्शन को देखते हुए बिटमैप अधिक प्रासंगिक हो जाते हैं। रेडिस सेट्स को आईडी को बिट ऑफ़सेट में मैप न करने का विशिष्ट लाभ भी है। इसी तरह, यदि आपके मान 2 से बड़े डोमेन से हैं तो बिटमैप के लिए डोमेन को विभाजित करने के लिए तंत्र का पता लगाने की तुलना में रेडिस सेट का उपयोग करना आसान होना चाहिए।
MOOC के लिए विश्लेषण
यहां एक मनगढ़ंत (लेकिन काफी वास्तविक!) उदाहरण है, जहां कोई रेडिस बिटमैप संचालन लागू कर सकता है। मान लीजिए, आप एक बहुत लोकप्रिय ऑनलाइन एमओओसी चला रहे हैं जिसमें सैकड़ों हजारों छात्रों ने नामांकन किया है। पाठ्यक्रम की सुविधा प्रदान करने वाली अकादमिक टीम एक डैशबोर्ड चाहती है, वे छात्रों की प्रगति की वास्तविक समय की स्थिति के साथ-साथ नामांकित छात्रों की सामान्य पृष्ठभूमि देख सकते हैं। आप इसे रेडिस बिटमैप ऑपरेशंस के माध्यम से कार्यान्वित करने का निर्णय लेते हैं। यहाँ इसके लिए एक कदम दर कदम दृष्टिकोण दिया गया है।
- छात्र आईडी और बिटमैप ऑफ़सेट के बीच मैप करने के लिए एक योजना बनाएं। यह बिटमैप में आईडी के ऑफसेट होने जितना आसान हो सकता है।
- पाठ्यक्रम शुरू होने के बाद विभिन्न जनसांख्यिकीय संबंधित बिटमैप बनाएं और पॉप्युलेट करें। उदाहरण के लिए एक ही विश्वविद्यालय, शिक्षा स्तर, लिंग आदि से अन्य एमओओसी में नामांकित छात्र।
- अब जैसे-जैसे पाठ्यक्रम आगे बढ़ता है, आप पाठ्यक्रम की प्रगति को रिकॉर्ड करने के लिए नए बिटमैप बना सकते हैं। उदाहरण के लिए वे छात्र जिन्होंने सप्ताह 1 के सभी व्याख्यानों को देखना पूरा कर लिया है, वे छात्र जिन्होंने सप्ताह 1 आदि के सभी असाइनमेंट पूरे कर लिए हैं।
- अब, इन चाबियों के आधार पर रीयल टाइम एनालिटिक्स बनाना एक बहुत ही सरल अभ्यास होगा और इसे ड्रैग एंड ड्रॉप UI पर किया जा सकता है। उदाहरण के लिए
- एक प्रोफेसर जो यह देखना चाहता है कि कितने छात्रों ने सप्ताह 1 (A) के लिए व्याख्यान देखा, लेकिन सप्ताह 1 (B) के लिए असाइनमेंट पूरा नहीं किया:ऑपरेटर:BITOP। ऑपरेशन:ए और (बी नहीं)।
- सप्ताह 1 (A), सप्ताह 2 (B), सप्ताह 3 (C) और सप्ताह 4 (D) के लिए सभी असाइनमेंट पूरा करने वाले छात्र:ऑपरेटर:BITOP। ऑपरेशन ए और बी और सी और डी। कहो, ये वे लोग हैं जिन्होंने कोर्स पास किया है।
- सभी पुरुष छात्र (एम) जिन्होंने कोर्स पास किया है (जैसा कि ऊपर गणना की गई है, मान लीजिए, पी):ऑपरेटर:बीआईटीओपी। ऑपरेशन:एम एंड पी.
- पाठ्यक्रम उत्तीर्ण करने वाले छात्रों की संख्या:BITCOUNT P.
इसी तरह, बिटमैप्स के रूप में किसी भी संख्या में दिलचस्प समूह स्थापित किए जा सकते हैं और इस तरह के क्रमपरिवर्तन उन पर चलते हैं।
फुटनोट
हमारी रेडिस डेटा संरचना श्रृंखला में अन्य पोस्ट:
- सेट
- हैश
- सॉर्ट किए गए सेट
