1. समस्या
StableBoundedPriorityQueue लागू करें। प्रत्येक प्रविष्टि (entry) में priority, sequence, और value होता है; पहले priority और फिर sequence की तुलना करें। क्षमता C के साथ, push अधिकतम C प्रविष्टियों को रखता है। एक नई प्रविष्टि वर्तमान सबसे खराब प्रविष्टि को केवल तभी बदलती है जब वह बेहतर हो; अन्यथा इसे अस्वीकार कर दिया जाता है। pop सबसे अच्छी प्रविष्टि लौटाता है।
2. बाधाएं और स्पष्टीकरण
Cएक धनात्मक पूर्णांक (positive integer) है;C=0के साथ, सरणी सीमा (array boundary) को छुए बिना प्रत्येक प्रविष्टि को अस्वीकार कर दिया जाता है।- कम संख्या का अर्थ उच्च प्राथमिकता है; समान प्राथमिकताओं को सम्मिलन क्रम (insertion order) में ही बाहर निकलना चाहिए।
- भरे होने पर सबसे खराब आइटम को अस्वीकार करने के लिए उस आइटम को खोजना आवश्यक होता है। एकल मिन-हीप (min-heap) इसे सीधे
O(log C)में प्रदर्शित नहीं कर सकता है, इसलिए दूसरे इंडेक्स, मैक्स-हीप (max-heap) का उपयोग करें, या एक लीनियर स्कैन स्वीकार करें। - सिंगल-थ्रेडेड कार्यान्वयन से शुरुआत करें। समवर्ती उत्पादकों (producers) और उपभोक्ताओं (consumers) को एक बाहरी लॉक या एक समर्पित समवर्ती कतार की आवश्यकता होती है।
3. मुख्य दृष्टिकोण
अगले आइटम के लिए मिन-हीप का उपयोग करें, जो (priority, sequence) द्वारा क्रमित हो। सबसे खराब आइटम के लिए मैक्स-हीप का उपयोग करें, जिसे इस प्रकार क्रमित किया गया हो कि बड़ी प्राथमिकता और बाद का अनुक्रम (sequence) बदतर माना जाए। दोनों हीप समान प्रविष्टि रिकॉर्ड की ओर इंगित करते हैं। निष्कासन एक प्रविष्टि को alive=false के रूप में चिह्नित करता है; प्रत्येक हीप मृत नोड्स को तब छोड़ (discard) देता है जब वे उसके रूट (root) तक पहुँचते हैं। यह लेज़ी डिलीशन (lazy deletion) मनमाने स्थान से हीप हटाने से बचाता है।
छोटी क्षमताओं के लिए, सबसे खराब आइटम के लिए एक लीनियर स्कैन सरल है: pop, O(log C) ही रहता है, जबकि भरी हुई कतार में push की लागत O(C) होती है। दो-हीप अनुकूलन प्रस्तुत करने से पहले इस ट्रेड-ऑफ़ का उल्लेख करें।
4. संदर्भ कार्यान्वयन
record Entry(priority, sequence, value, alive=true)
push(priority, value):
if capacity == 0: return false
candidate = Entry(priority, nextSequence(), value)
if size < capacity:
add candidate to minHeap and maxHeap
size += 1
return true
discard dead nodes from maxHeap
worst = maxHeap.peek()
if (priority, candidate.sequence) >= (worst.priority, worst.sequence):
return false
worst.alive = false
pop maxHeap
add candidate to both heaps
return true
pop():
discard dead nodes from minHeap
if minHeap is empty: return EMPTY
entry = pop minHeap
entry.alive = false
size -= 1
return entry.valueमैक्स-हीप कुंजी (key) का अर्थ है "बड़ा बदतर है": एक बड़ी प्राथमिकता बदतर होती है, और समान प्राथमिकता के लिए एक बड़ा अनुक्रम बाद का होता है और इसलिए बदतर होता है। यदि किसी भाषा में मैक्स-हीप नहीं है, तो कुंजी को नकारें (negate करें) या एक तुलनित्र (comparator) प्रदान करें। nextSequence मोनोटोनिक (monotonic) होना चाहिए; एक विस्तृत पूर्णांक (wide integer) का उपयोग करें या इसे केवल तभी रीसेट करें जब कतार खाली हो।
5. जटिलता और ट्रेड-ऑफ़
एक स्वीकृत सम्मिलन प्रत्येक हीप में एक नोड जोड़ता है, इसलिए इसकी लागत O(log C) होती है; pop की लागत O(log C) होती है। प्रतिस्थापन भी O(log C) है। लेज़ी डिलीशन मृत नोड्स को अस्थायी रूप से छोड़ सकता है, लेकिन प्रत्येक मृत नोड को एक बार पॉप किया जाता है, जिससे निरंतर-कारक वृद्धि (constant-factor increase) के साथ परिशोधित (amortized) O(log C) संचालन और O(C) स्थान मिलता है। एक लीनियर-स्कैन संस्करण कम स्थान और छोटे कोड का उपयोग करता है लेकिन भरी हुई कतार में सम्मिलन के लिए इसकी लागत O(C) होती है।
6. सत्यापन और अवलोकनीयता
C=0,C=1, एक खाली कतार, बार-बार अस्वीकृति, और बार-बार प्रतिस्थापन को कवर करें।- कई समान-प्राथमिकता वाली प्रविष्टियां डालें और अनुक्रम द्वारा FIFO क्रम सत्यापित करें।
- भरी हुई कतार के विरुद्ध एक बदतर, समान और बेहतर उम्मीदवार का परीक्षण करें; अस्वीकार, अस्वीकार और प्रतिस्थापित की अपेक्षा करें।
- यादृच्छिक ऑपरेशन ट्रेस की तुलना एक संदर्भ मॉडल से करें जो सभी लाइव प्रविष्टियों को
(priority, sequence)द्वारा सॉर्ट करता है औरCतक ट्रंकेट करता है। - कतार की लंबाई, अस्वीकृति गणना, और लेज़ी-नोड क्लीनअप गणना रिकॉर्ड करें। बढ़ती अस्वीकृति दर अपस्ट्रीम थ्रॉटलिंग या लोड शेडिंग को ट्रिगर कर सकती है।
7. सामान्य गलतियाँ
- केवल प्राथमिकता के आधार पर सॉर्ट करना, जिससे टाई होने पर FIFO स्थिरता समाप्त हो जाती है।
- दिशा की पुष्टि किए बिना यह मान लेना कि बड़ी संख्यात्मक प्राथमिकता अधिक महत्वपूर्ण है।
- एडमिशन से पहले हीप रूट को पॉप करना, जो कतार भरी होने पर सबसे अच्छे कार्य को हटा देता है।
- मृत नोड्स को हटाने में विफल होना, जिससे
peekपहले से प्रतिस्थापित या रद्द की गई प्रविष्टि लौटाता है। - अनुक्रम संख्याओं के लिए वॉल-क्लॉक टाइमस्टैम्प का उपयोग करना; क्लॉक रोलबैक या समान-टिक प्रविष्टियां FIFO को तोड़ सकती हैं।
8. अनुवर्ती प्रश्न
आप प्रति-किरायेदार (per-tenant) कोटा कैसे लागू करेंगे?
प्रत्येक किरायेदार के लिए एक गिनती और सीमा रखें। सम्मिलन से पहले वैश्विक क्षमता और किरायेदार कोटा दोनों की जांच करें, और दो अस्वीकृति कारणों को अलग-अलग गिनें ताकि सक्रिय किरायेदारों की पहचान हो सके।
आप किसी प्रविष्टि को कैसे रद्द या पुन: प्राथमिकता देंगे?
प्रत्येक प्रविष्टि को एक ID दें और लेज़ी डिलीशन का उपयोग करें। रद्दीकरण इसे मृत के रूप में चिह्नित करता है; पुन: प्राथमिकता देना एक नई प्रविष्टि बनाता है और पुरानी को अमान्य करता है। मनमाने हीप स्थानों से हटाने के बजाय पीक (peeking) या पॉप (popping) करते समय मृत नोड्स को साफ़ करें।
आपको लाइब्रेरी समवर्ती प्रायोरिटी कतार का उपयोग कब करना चाहिए?
जब कई थ्रेड्स या प्रक्रियाएं उत्पादन और उपभोग करती हैं, ब्लॉकिंग प्रतीक्षा की आवश्यकता होती है, या मेमोरी सीमाएं सख्त होती हैं, तो एक परीक्षण किए गए समवर्ती कार्यान्वयन का उपयोग करें। एक कस्टम दो-हीप डिज़ाइन केवल एक स्पष्ट सिंगल-थ्रेडेड सीमा और एक परीक्षण योग्य जीवनचक्र के साथ ही उपयुक्त है।