एक विशाल बिटमैप

Question

साक्षात्कार प्रश्न में पहला सेट बिट के लिए सर्च कर रहे हैं:

एक पार्किंग स्लॉट जो मिलियन कारों धारण कर सकते हैं, आप एक मुक्त पार्किंग स्लॉट खोजने की जरूरत है। स्लॉट कहां हो सकता है, इस पर कोई शर्त नहीं है, यानी पार्किंग स्थल में कई प्रवेश द्वार हो सकते हैं और प्रवेश द्वार के पास एक स्लॉट ढूंढ सकते हैं, इससे कोई फर्क नहीं पड़ता। सवाल यह था कि किस प्रकार की डेटा संरचना का उपयोग किया जाना चाहिए और विभिन्न परिचालनों की जटिलता क्या होगी।

मैंने लिया गया/मुक्त स्लॉट के लिए 0/1 के साथ मिलियन बिट्स की एक छोटी सी सरणी का उपयोग करने का सुझाव दिया, इसलिए मुफ्त स्थान खोजने के लिए पहले सेट बिट को खोजने के लिए अनुवाद किया गया। इस बारे में कुछ भी न मानें कि कितनी कारें हैं, इत्यादि, यानी, बिट सरणी स्पैस या घनी हो सकती है।

एक विशाल बिटमैप में सेट बिट खोजने का सबसे तेज़ तरीका क्या है? मैंने योजना के रूप में प्रति शब्द बाइनरी खोज + कुशल ffs() का सुझाव दिया था।

स्टोर एक चर में पिछले मुक्त स्लॉट के सूचकांक और फिर अगले एक शुरुआत से बिटमैप स्कैन न करें की तलाश में है, लेकिन इस मूल्य से:

Answer 1

आप इस तरह से जा सकते हैं।

यदि आपको कुछ स्लॉट मुक्त करने की आवश्यकता है, तो उसे अंतिम अनुक्रमणिका में असाइन करें।

std::vector<bool> आपकी बिट सरणी हो सकती है, इसलिए आपको खुद को बिट्स से निपटने की आवश्यकता नहीं होगी (बूल को आंतरिक रूप से इनट में पैक किया जाता है)।

``std::vector<bool>`` Bitmap; 
``std::vector<bool>`` Bitmap2; // half-sized 
``std::vector<bool>`` Bitmap4; // 1/4 
``std::vector<bool>`` Bitmap8; // 1/8 
// etc 

ऊपरी स्तर सरणियों में free मूल्यों स्थिति है जहाँ निचले स्तर सरणी किसी भी मुफ्त स्लॉट के अनुरूप:

आप एक mip-mapped संरचना लागू कर सकते हैं। आप इस संरचना को पार करने के लिए बाइनरी खोज का उपयोग कर सकते हैं।

Answer 2

एक मिलियन 32-बिट पूर्णांक को लगभग 4 एमबी मेमोरी की आवश्यकता होती है। तो मैं कहूंगा कि आप मुफ्त स्लॉट की एक सूची रखते हैं। जब भी कोई कार प्रवेश करती है, तो आप सूची से एक वस्तु लेते हैं और उसे असाइन करते हैं। जब भी कोई कार छोड़ती है, तो आप मुक्त स्लॉट नंबर को सूची में डाल देते हैं।

आप केवल कभी सूची के अंत (तो यह एक stack या LIFO संरचना के रूप में इस्तेमाल वास्तव में है), यह आप इष्टतम हे (1) दोनों एक नि: शुल्क स्लॉट को खोजने के लिए और वापस आने के लिए प्रदर्शन देता है जोड़ तोड़ के रूप में होगी मुक्त राज्य के लिए एक स्लॉट। यदि आप स्मृति के कच्चे हिस्से के साथ निम्न स्तर पर ऐसा करते हैं, तो आपको सूची के वर्तमान छोर को इंगित करने वाले सूचक की आवश्यकता होगी। एक स्लॉट कमी ढूँढना जो पॉइंटर और उसका मूल्य देता है। एक स्लॉट लौटने से सूचक को आवंटित किया जाता है और बाद में इसे बढ़ाया जाता है।

यदि आप बाद में अतिरिक्त आवश्यकताओं को जोड़ने का निर्णय लेते हैं, तो आप अपने डेटा का कुछ जोड़-विमर्श कर सकते हैं, उदा। इसे heap में बदलें। 0/1 बिट्स के बड़े मानचित्र के साथ, ऐसे एक्सटेंशन संभव नहीं होंगे।