सवाल
0 से लेकर U-1 तक की कुंजियों (keys) वाले एक निश्चित इंटीजर यूनिवर्स को देखते हुए, insertion, deletion, membership, minimum, maximum, predecessor, और successor का समर्थन करने वाला एक van Emde Boas Tree लागू करें। high और low अपघटन (decomposition), summary संरचना, खाली क्लस्टर हैंडलिंग, और यह समझाएं कि ऑपरेशन्स O(log U) के बजाय O(log log U) समय क्यों लेते हैं।
इंटरव्यूअर क्या जांच रहा है
- क्या आप यह समझते हैं कि vEB Tree एक निश्चित इंटीजर यूनिवर्स और बिट ऑपरेशन्स मानकर चलता है, इसलिए यह सीधे तौर पर मनमाने ऑब्जेक्ट्स के लिए कंपेरिसन ट्री की जगह नहीं लेता है।
- क्या आप क्लस्टर इंडेक्स और ऑफ़सेट की सही गणना कर सकते हैं और summary को गैर-खाली क्लस्टरों से अवगत रख सकते हैं।
- क्या आप खाली ट्री, सिंगलटन, बाउंड्री कीज़, minimum के डिलीशन, और किसी क्लस्टर के खाली होने के बाद क्लीनअप को सही ढंग से संभालते हैं।
- क्या आप सैद्धांतिक जटिलता और O(U) स्पेस लागत बता सकते हैं, और फिर यह नाम दे सकते हैं कि कब y-fast trie, सॉर्टेड ऐरे, या सामान्य बैलेंस्ड ट्री अधिक बेहतर होता है।
मॉडल उत्तर
मान लें कि U बिट चौड़ाई w के साथ दो की घात (power of two) है। प्रत्येक vEB नोड u आकार के एक सब-यूनिवर्स का मालिक होता है और एक की (key) को एक high क्लस्टर इंडेक्स और एक low ऑफ़सेट में विभाजित करता है। सामान्य रिकर्सिव परिभाषा में, दोनों आधे लगभग आधे बिट्स का उपयोग करते हैं, इसलिए एक नोड में लगभग sqrt(u) क्लस्टर होते हैं। प्रत्येक क्लस्टर sqrt(u) आकार का एक अन्य vEB होता है, और sqrt(u) आकार का एक summary यह रिकॉर्ड करता है कि कौन से क्लस्टर गैर-खाली हैं।
नोड min और max को भी स्टोर करता है ताकि सामान्य ऑपरेशन्स पत्तियों (leaves) तक रिकर्स न करें। पहले तत्व को इन्सर्ट करने पर दोनों मान सेट हो जाते हैं; बाद का इन्सर्शन छोटी की (key) को min में स्वैप करता है और पुराने min को उसके क्लस्टर में इन्सर्ट करता है। डिलीशन को min या max को हटाने, summary के माध्यम से अगले गैर-खाली क्लस्टर को खोजने, और क्लस्टर खाली होने पर उसे summary से हटाने को संभालना चाहिए।
पुनरावृत्ति (recurrence) T(u)=T(sqrt(u))+O(1) है। बार-बार स्क्वायर रूट लेने से प्रत्येक स्तर पर घातांक आधा हो जाता है, इसलिए गहराई O(log log U) होती है। एक सामान्य लेआउट के साथ, रिकर्सिव नोड्स में क्लस्टर पॉइंटर्स और सारांश O(U) स्पेस का उपयोग करते हैं। स्पार्स लेआउट्स स्थिरांक (constants) को कम करते हैं लेकिन अपने आप में यूनिवर्स पर निर्भरता को नहीं हटाते हैं।
कार्यान्वयन की रूपरेखा
छद्म-कोड अपघटन और पुनर्संयोजन के लिए high, low, और index का उपयोग करता है, जिसमें मेमोरी पूल और तर्क सत्यापन (argument validation) को छोड़ दिया गया है।
high(x, bits) = x >> ceil(bits / 2)
low(x, bits) = x & ((1 << floor(bits / 2)) - 1)
index(h, l, bits) = (h << floor(bits / 2)) | l
insert(v, x):
if v.min is empty:
v.min = x; v.max = x; return
if x < v.min:
swap(x, v.min)
if v.bits > 1:
h = high(x, v.bits); l = low(x, v.bits)
if v.cluster[h].min is empty:
insert(v.summary, h)
insert(v.cluster[h], l)
if x > v.max:
v.max = x
successor(v, x):
if v.min is empty or x >= v.max: return empty
if v.bits == 1:
return v.max if v.max > x else empty
if x < v.min: return v.min
h = high(x, v.bits); l = low(x, v.bits)
c = v.cluster[h]
if c is not empty and l < c.max:
return index(h, successor(c, l), v.bits)
next_h = successor(v.summary, h)
if next_h is empty: return empty
return index(next_h, v.cluster[next_h].min, v.bits)एक वास्तविक डिलीशन कार्यान्वयन को सममित (symmetric) खाली-क्लस्टर नियमों को बनाए रखना चाहिए। लीफ नोड्स रिकर्सिव रूप से ऑब्जेक्ट्स आवंटित करने के बजाय एक छोटे बिटमैप या दो मानों का उपयोग कर सकते हैं। पहले बिट चौड़ाई तय करें, फिर रैंडम ऑपरेशन सीक्वेंस की तुलना एक ऑर्डर्ड सेट से करें ताकि predecessor और successor के परिणाम मेल खाएं।
सामान्य गलतियाँ
- U को तत्व गणना n मान लेना और दावा करना कि प्रत्येक ऑपरेशन O(log log n) है। पैरामीटर यूनिवर्स का आकार U है।
- जब U दो की घात नहीं होता है, तो राउंडिंग को नज़रअंदाज़ करना, जिससे high, low, और index अब व्युत्क्रम (inverse) ऑपरेशन्स नहीं रह जाते हैं।
- membership और minimum को लागू करना लेकिन डिलीशन के बाद summary से खाली क्लस्टरों को कभी न हटाना।
- O(U) स्पेस, कैश लोकैलिटी, और वास्तविक की (key) वितरण की उपेक्षा करते हुए यह मान लेना कि vEB हमेशा रेड-ब्लैक ट्री से तेज़ होता है।
- summary को उसके यूनिवर्स की सीमा और खाली प्रतिनिधित्व को बताए बिना वही रिकर्सिव संरचना देना।
जटिलता का संतुलन (Trade-offs)
मशीन-वर्ड इंटीजर्स, एक ज्ञात यूनिवर्स, और predecessor तथा successor पर केंद्रित वर्कलोड्स के लिए, O(log log U) सिद्धांत रूप में आकर्षक है। यदि U वर्ड रेंज के करीब है लेकिन सेट स्पार्स है, तो एक सामान्य लेआउट मेमोरी बर्बाद करता है। x-fast या y-fast tries हैशिंग, रैंडमनेस, या कार्यान्वयन जटिलता की कीमत पर स्पेस को n पर अधिक निर्भर बनाते हैं।
एक सामान्य बैलेंस्ड ट्री O(log n) ऑपरेशन्स, O(n) स्पेस, और सरल इटरेटर सिमेंटिक्स प्रदान करता है। एक सॉर्टेड ऐरे स्थिर सेटों और बैच क्वेरीज़ के लिए उपयुक्त है। एक इंटरव्यू में, केवल सबसे तेज़ एसिम्प्टोटिक बाउंड की रिपोर्ट करने के बजाय की डोमेन, अपडेट अनुपात, मेमोरी बजट, और रखरखाव के आधार पर चयन करें।
सीमा अपघटन (boundary decomposition) का परीक्षण करने के लिए U को 2, 4, और 16 के बराबर, साथ ही गैर-दो-की-घात वाले यूनिवर्स के साथ शुरू करें। रैंडम इन्सर्शन, डिलीशन, और क्वेरी सीक्वेंस उत्पन्न करें और भाषा के ऑर्डर्ड सेट के साथ minimum, maximum, membership, predecessor, और successor की तुलना करें। इसके अलावा डुप्लिकेट इन्सर्शन, गायब की (missing key) को हटाना, अंतिम की को हटाना, और minimum या maximum को बार-बार हटाने को भी कवर करें।
संदर्भ
- MIT OpenCourseWare van Emde Boas Trees व्याख्यान: रिकर्सिव क्लस्टर्स, सारांश, और ऑपरेशन व्युत्पत्ति।
- Carnegie Mellon Graduate Algorithms व्याख्यान 7: O(log log U) पुनरावृत्ति विश्लेषण और कार्यान्वयन विवरण।
- Springer का predecessor-search सर्वेक्षण: मूल van Emde Boas कार्य और predecessor-समस्या संदर्भ।
अनुवर्ती प्रश्न
summary संरचना क्यों आवश्यक है?
जब वर्तमान क्लस्टर में कोई बड़ा तत्व नहीं होता है, तो ट्री को अगले गैर-खाली क्लस्टर को जल्दी से खोजना होगा। सारांश क्लस्टरों को लीनियर रूप से स्कैन करने के बजाय "कौन से क्लस्टर गैर-खाली हैं" को एक अन्य predecessor या successor समस्या में बदल देता है।
min और max क्लस्टरों के बाहर क्यों रह सकते हैं?
min और max को अलग रखने से खाली-ट्री और सिंगलटन ऑपरेशन्स स्थिर समय (constant time) में होते हैं और रिकर्सन कम हो जाता है। इन्सर्शन एक छोटे मान को min में स्वैप करता है; डिलीशन summary के माध्यम से एक प्रतिस्थापन एक्सट्रीम ढूंढता है और इनवेरिएंट्स को पुनर्स्थापित करता है।
क्या होगा यदि U दो की घात नहीं है?
दो की घात वाले यूनिवर्स में राउंड अप करें जो प्रत्येक वैध की को कवर करता है और मूल सीमा के बाहर की कुंजियों को अस्वीकार कर देता है। वैकल्पिक रूप से, राउंडेड क्लस्टर बाउंड्रीज़ लागू करें, लेकिन यह साबित करें कि high, low, और index व्युत्क्रम बने रहते हैं और जटिलता अभी भी लागू रहती है।
आप O(U) स्पेस को कैसे कम कर सकते हैं?
स्पार्स क्लस्टर्स, x-fast tries, या y-fast tries का उपयोग करें। केवल बिग-O नोटेशन की तुलना करने के बजाय हैश टकराव, रैंडमनेस, इटरेटर सिमेंटिक्स, और स्थिर कारकों (constant factors) की व्याख्या करें।
आपको vEB से कब बचना चाहिए?
जब की (key) डोमेन बहुत बड़ा और स्पार्स हो, यूनिवर्स को तय नहीं किया जा सकता हो, एक सामान्य तुलनित्र (comparator) की आवश्यकता हो, या परिपक्व इटरेटर व्यवहार सैद्धांतिक बाउंड की तुलना में अधिक मायने रखता हो, तो बैलेंस्ड ट्री या B-tree का उपयोग करें।