Python 3.7

heapq - ढेर कतार एल्गोरिथ्म




python

heapq - ढेर कतार एल्गोरिथ्म

स्रोत कोड: Lib/heapq.py

यह मॉड्यूल हीप कतार एल्गोरिदम का कार्यान्वयन प्रदान करता है, जिसे प्राथमिकता कतार एल्गोरिदम के रूप में भी जाना जाता है।

ढेर बाइनरी ट्री हैं, जिनके लिए प्रत्येक माता-पिता के नोड का मूल्य उसके किसी भी बच्चे से कम या बराबर है। यह कार्यान्वयन सरणियों का उपयोग करता है जिसके लिए heap[k] <= heap[2*k+1] और heap[k] <= heap[2*k+2] सभी k के लिए , शून्य से तत्वों की गिनती। तुलना के लिए, गैर-मौजूदा तत्वों को अनंत माना जाता है। एक ढेर की दिलचस्प संपत्ति यह है कि इसका सबसे छोटा तत्व हमेशा जड़ होता है, heap[0]

नीचे दी गई एपीआई पाठ्यपुस्तक के ढेर एल्गोरिदम से दो पहलुओं में भिन्न है: (ए) हम शून्य-आधारित अनुक्रमण का उपयोग करते हैं। यह नोड के लिए इंडेक्स और उसके बच्चों के लिए इंडेक्स के बीच संबंध को थोड़ा कम स्पष्ट करता है, लेकिन अधिक उपयुक्त है क्योंकि पायथन शून्य-आधारित इंडेक्सिंग का उपयोग करता है। (b) हमारी पॉप विधि सबसे छोटी वस्तु लौटाती है, सबसे बड़ी नहीं (जिसे पाठ्यपुस्तकों में "न्यूनतम हीप" कहा जाता है, "इन-प्लेस छँटाई के लिए उपयुक्तता के कारण ग्रंथों में" अधिकतम हीप "अधिक सामान्य है)।

ये दोनों बिना किसी आश्चर्य के एक नियमित पायथन सूची के रूप में ढेर को देखना संभव बनाते हैं: heap[0] सबसे छोटी वस्तु है, और heap.sort() ढेर को heap.sort() बनाए रखता है!

एक हीप बनाने के लिए, [] लिए इनिशियलाइज़ की गई सूची का उपयोग करें, या आप फंक्शन heapify() माध्यम से एक पॉपुलेटेड लिस्ट को हीप में बदल सकते हैं।

निम्नलिखित कार्य प्रदान किए जाते हैं:

heapq.heappush(heap, item)

ढेर पर मूल्य आइटम धक्का, ढेर अपरिवर्तनीय बनाए रखने।

heapq.heappop(heap)

पॉप और ढेर से सबसे छोटी वस्तु को वापस करें, ढेर को अपरिवर्तित बनाए रखना। यदि ढेर खाली है, तो IndexError को उठाया जाता है। इसे पॉप किए बिना सबसे छोटी वस्तु तक पहुंचने के लिए, heap[0] उपयोग करें heap[0]

heapq.heappushpop(heap, item)

आइटम को ढेर पर पुश करें, फिर पॉप करें और ढेर से सबसे छोटी वस्तु वापस करें। संयुक्त कार्रवाई अधिक प्रभावी ढंग से heappush() अलग करने के लिए एक अलग कॉल के heappop()

heapq.heapify(x)

सूची x को ढेर में, जगह में, रैखिक समय में परिवर्तित करें।

heapq.heapreplace(heap, item)

पॉप और ढेर से सबसे छोटी वस्तु लौटाएं, और नई वस्तु को भी धक्का दें। ढेर का आकार नहीं बदलता है। यदि ढेर खाली है, तो IndexError को उठाया जाता है।

यह एक स्टेप ऑपरेशन एक heappop() बाद heappop() से अधिक कुशल है और एक निश्चित आकार के ढेर का उपयोग करते समय अधिक उपयुक्त हो सकता है। पॉप / पुश संयोजन हमेशा एक तत्व को ढेर से लौटाता है और इसे आइटम से बदल देता है।

लौटाया गया मान, जोड़े गए आइटम से बड़ा हो सकता है। यदि यह वांछित नहीं है, तो इसके बजाय heappushpop() का उपयोग करने पर विचार करें। इसका धक्का / पॉप संयोजन दो मानों को छोटा करता है, जिससे ढेर पर बड़ा मूल्य निकल जाता है।

मॉड्यूल ढेर के आधार पर तीन सामान्य उद्देश्य फ़ंक्शन भी प्रदान करता है।

heapq.merge(*iterables, key=None, reverse=False)

एकल सॉर्ट किए गए आउटपुट में कई सॉर्ट किए गए इनपुट मर्ज करें (उदाहरण के लिए, कई लॉग फ़ाइलों से टाइमस्टैम्प्ड प्रविष्टियों को मर्ज करें)। सॉर्ट किए गए मानों पर iterator देता है।

sorted(itertools.chain(*iterables)) लेकिन पुनरावृति देता है, डेटा को एक बार में मेमोरी में नहीं खींचता है, और मानता है कि प्रत्येक इनपुट स्ट्रीम पहले से ही सॉर्ट की गई है (सबसे छोटी से सबसे बड़ी)।

दो वैकल्पिक तर्क हैं जिन्हें कीवर्ड तर्क के रूप में निर्दिष्ट किया जाना चाहिए।

कुंजी एक तर्क के एक प्रमुख कार्य को निर्दिष्ट करती है जिसका उपयोग प्रत्येक इनपुट तत्व से तुलना कुंजी निकालने के लिए किया जाता है। डिफ़ॉल्ट मान None (सीधे तत्वों की तुलना करें)।

रिवर्स एक बूलियन मूल्य है। यदि इसे True सेट किया जाता है, तो इनपुट तत्वों को विलय कर दिया जाता है जैसे कि प्रत्येक तुलना को उलट दिया जाता है। sorted(itertools.chain(*iterables), reverse=True) समान व्यवहार प्राप्त करने के लिए, सभी पुनरावृत्तियों को सबसे बड़े से लेकर सबसे छोटे तक क्रमबद्ध किया जाना चाहिए।

3.5 संस्करण में बदल गया : वैकल्पिक कुंजी और रिवर्स मापदंडों को जोड़ा गया।

heapq.nlargest(n, iterable, key=None)

पुनरावृत्ति द्वारा परिभाषित डेटासेट से n सबसे बड़े तत्वों के साथ एक सूची लौटाएं। कुंजी , यदि प्रदान की जाती है, तो एक तर्क के एक फ़ंक्शन को निर्दिष्ट करता है जिसका उपयोग प्रत्येक तत्व से तुलना कुंजी निकालने के लिए किया जाता है: key=str.lower : key=str.lower समतुल्य: sorted(iterable, key=key, reverse=True)[:n]

heapq.nsmallest(n, iterable, key=None)

पुनरावृत्ति द्वारा परिभाषित डेटासेट से n सबसे छोटे तत्वों के साथ एक सूची लौटाएं। कुंजी , यदि प्रदान की जाती है, तो एक तर्क के एक फ़ंक्शन को निर्दिष्ट करता है, जिसका उपयोग पुनरावृत्त में प्रत्येक तत्व से तुलना कुंजी निकालने के लिए किया जाता है: key=str.lower समतुल्य: sorted(iterable, key=key)[:n]

बाद के दो कार्य n के छोटे मूल्यों के लिए सर्वश्रेष्ठ प्रदर्शन करते हैं। बड़े मूल्यों के लिए, sorted() फ़ंक्शन का उपयोग करना अधिक कुशल है। इसके अलावा, जब n==1 , यह अंतर्निहित min() और max() फ़ंक्शन का उपयोग करने के लिए अधिक कुशल है। यदि इन कार्यों के बार-बार उपयोग की आवश्यकता होती है, तो पुनरावृत्ति को एक वास्तविक ढेर में बदलने पर विचार करें।

मूल उदाहरण

एक ढेर पर सभी मूल्यों को धकेल कर और फिर एक समय में सबसे छोटे मानों को बंद करके एक ढेर को लागू किया जा सकता है:

>>> def heapsort(iterable):
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

यह sorted(iterable) समान है, लेकिन sorted() विपरीत, यह कार्यान्वयन स्थिर नहीं है।

ढेर तत्व ट्यूपल्स हो सकते हैं। यह तुलनात्मक मान निर्दिष्ट करने के लिए उपयोगी है (जैसे कार्य प्राथमिकताएं) मुख्य रिकॉर्ड के साथ ट्रैक किया जा रहा है:

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

प्राथमिकता कतार कार्यान्वयन नोट्स

एक प्राथमिकता कतार ढेर के लिए आम उपयोग है, और यह कई कार्यान्वयन चुनौतियां प्रस्तुत करती है:

  • क्रमबद्धता स्थिरता: आप मूल रूप से जोड़े गए क्रम में वापस आने के लिए समान प्राथमिकता वाले दो कार्य कैसे प्राप्त करते हैं?
  • यदि प्राथमिकताएं समान हैं और कार्यों में डिफ़ॉल्ट तुलना क्रम नहीं है, तो टपल तुलना (प्राथमिकता, कार्य) जोड़े के लिए टूट जाती है।
  • यदि किसी कार्य की प्राथमिकता बदल जाती है, तो आप इसे कैसे एक नए स्थान पर ले जाते हैं?
  • या यदि किसी लंबित कार्य को हटाने की आवश्यकता है, तो आप इसे कैसे ढूंढते हैं और इसे कतार से हटाते हैं?

पहली दो चुनौतियों का समाधान प्रविष्टियों को 3-तत्व सूची के रूप में प्राथमिकता, प्रविष्टि संख्या और कार्य सहित संग्रहीत करना है। एंट्री काउंट एक टाई-ब्रेकर के रूप में कार्य करता है ताकि एक ही प्राथमिकता वाले दो कार्यों को उस क्रम में वापस किया जाए जो उन्हें जोड़ा गया था। और चूंकि कोई भी दो एंट्री काउंट समान नहीं हैं, टपल की तुलना कभी भी दो कार्यों की सीधे तुलना करने का प्रयास नहीं करेगी।

गैर-तुलनीय कार्यों की समस्या का एक और समाधान एक आवरण वर्ग बनाना है जो कार्य आइटम की उपेक्षा करता है और केवल प्राथमिकता क्षेत्र की तुलना करता है:

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

शेष चुनौतियाँ एक लंबित कार्य को खोजने और उसकी प्राथमिकता में बदलाव करने या इसे पूरी तरह से हटाने के इर्द-गिर्द घूमती हैं। एक कार्य ढूँढना एक शब्दकोश के साथ कतार में एक प्रविष्टि की ओर इशारा करते हुए किया जा सकता है।

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

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
counter = itertools.count()     # unique sequence count

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = next(counter)
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop_task():
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

सिद्धांत

हीप एरे हैं, जिनके a[k] <= a[2*k+1] और a[k] <= a[2*k+2] सभी k के लिए , गिनती के तत्व 0. से, तुलना के लिए, गैर -उपस्थित तत्व अनंत माने जाते हैं। एक ढेर की दिलचस्प संपत्ति यह है कि a[0] हमेशा इसका सबसे छोटा तत्व होता है।

ऊपर दिए गए अजीब से आक्रमण का मतलब एक टूर्नामेंट के लिए एक कुशल मेमोरी प्रतिनिधित्व है। नीचे दिए गए नंबर k हैं , न a[k] :

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

ऊपर के पेड़ में, प्रत्येक कोशिका k 2*k+1 और 2*k+2 । एक सामान्य बाइनरी टूर्नामेंट में हम खेल में देखते हैं, प्रत्येक कोशिका दो कोशिकाओं में सबसे ऊपर विजेता होती है, और हम सभी विरोधियों को जीतने के लिए पेड़ के नीचे विजेता का पता लगा सकते हैं। हालांकि, ऐसे टूर्नामेंटों के कई कंप्यूटर अनुप्रयोगों में, हमें एक विजेता के इतिहास का पता लगाने की आवश्यकता नहीं है। अधिक स्मृति कुशल होने के लिए, जब एक विजेता को पदोन्नत किया जाता है, तो हम इसे निचले स्तर पर किसी और चीज़ से बदलने की कोशिश करते हैं, और नियम यह हो जाता है कि एक सेल और दो कोशिकाओं में यह तीन अलग-अलग आइटम होते हैं, लेकिन शीर्ष सेल "जीतता है" दो से अधिक शीर्ष कोशिकाओं।

यदि यह ढेर अशुभ हर समय संरक्षित है, तो सूचकांक 0 स्पष्ट रूप से समग्र विजेता है। इसे हटाने के लिए सबसे सरल एल्गोरिदमिक तरीका है और "अगला" विजेता को कुछ स्थिति में स्थानांतरित करना है (चलो ऊपर चित्र में सेल 30 कहते हैं) को 0 स्थिति में ले जाएं, और फिर इस नए 0 को पेड़ से नीचे करें, मूल्यों का आदान-प्रदान करें, जब तक कि हमलावर नहीं होता। फिर से स्थापित किया गया है। यह स्पष्ट रूप से वृक्ष में वस्तुओं की कुल संख्या पर लघुगणकीय है। सभी आइटम्स पर पुनरावृत्ति करके, आपको O (n लॉग एन) सॉर्ट मिलता है।

इस तरह की एक अच्छी विशेषता यह है कि आप जिस तरह से चल रहे हैं, आप कुशलतापूर्वक नई वस्तुओं को सम्मिलित कर सकते हैं, बशर्ते कि सम्मिलित आइटम आपके द्वारा निकाले गए अंतिम 0 के तत्व की तुलना में "बेहतर" न हों। यह विशेष रूप से सिमुलेशन संदर्भों में उपयोगी है, जहां पेड़ सभी आने वाली घटनाओं को रखता है, और "जीत" स्थिति का अर्थ है सबसे छोटा निर्धारित समय। जब कोई घटना निष्पादन के लिए अन्य घटनाओं को निर्धारित करती है, तो उन्हें भविष्य में निर्धारित किया जाता है, ताकि वे आसानी से ढेर में जा सकें। तो, एक शेड्यूल शेड्यूलर्स को लागू करने के लिए एक अच्छी संरचना है (यह वही है जो मैंने अपने मिडी सीक्वेंसर :-) के लिए इस्तेमाल किया था।

शेड्यूलर्स को लागू करने के लिए विभिन्न संरचनाओं का बड़े पैमाने पर अध्ययन किया गया है, और इसके लिए ढेर अच्छे हैं, क्योंकि वे यथोचित रूप से तेज़ हैं, गति लगभग स्थिर है, और सबसे खराब स्थिति औसत मामले से बहुत अलग नहीं है। हालांकि, अन्य अभ्यावेदन हैं जो समग्र रूप से अधिक कुशल हैं, फिर भी सबसे खराब मामले भयानक हो सकते हैं।

बड़े डिस्क के प्रकारों में भी ढेर बहुत उपयोगी होते हैं। आप शायद सभी जानते हैं कि एक बड़ा प्रकार "रन" का उत्पादन करता है (जो पूर्व-क्रमबद्ध अनुक्रम हैं, जिसका आकार आमतौर पर सीपीयू मेमोरी की मात्रा से संबंधित होता है), इसके बाद इन रनों के लिए एक विलय पास होता है, जो विलय अक्सर बहुत चतुराई से होता है आयोजित [1] । यह बहुत महत्वपूर्ण है कि प्रारंभिक सॉर्ट संभव सबसे लंबे समय तक चलता है। टूर्नामेंट हासिल करने का एक अच्छा तरीका है। यदि, टूर्नामेंट आयोजित करने के लिए उपलब्ध सभी मेमोरी का उपयोग करते हुए, आप वर्तमान रन को फिट करने के लिए आइटमों को बदल देते हैं और नष्ट कर देते हैं, तो आप ऐसे रन बनाएंगे जो यादृच्छिक इनपुट के लिए मेमोरी के आकार का दोगुना है, और इनपुट फ़ज़ीली ऑर्डर के लिए बहुत बेहतर है।

इसके अलावा, यदि आप डिस्क पर 0 आइटम का आउटपुट करते हैं और एक इनपुट प्राप्त करते हैं जो वर्तमान टूर्नामेंट में फिट नहीं हो सकता है (क्योंकि पिछले आउटपुट मान पर "जीत"), यह ढेर में फिट नहीं हो सकता है, इसलिए आकार ढेर कम हो जाता है। मुक्त स्मृति को चतुराई से दूसरे ढेर के निर्माण के लिए तुरंत पुन: उपयोग किया जा सकता है, जो उसी दर से बढ़ता है जो पहले ढेर पिघलता है। जब पहला ढेर पूरी तरह से गायब हो जाता है, तो आप ढेर स्विच करते हैं और एक नया रन शुरू करते हैं। चतुर और काफी प्रभावी!

एक शब्द में, ढेर जानने के लिए उपयोगी स्मृति संरचनाएं हैं। मैं उन्हें कुछ अनुप्रयोगों में उपयोग करता हूं, और मुझे लगता है कि एक 'ढेर' मॉड्यूल रखना अच्छा है। :-)

फुटनोट

[1] डिस्क संतुलन एल्गोरिदम, जो वर्तमान में हैं, आजकल चालाक की तुलना में अधिक कष्टप्रद हैं, और यह डिस्क की मांग क्षमताओं का एक परिणाम है। उन उपकरणों पर, जो बड़े टेप ड्राइव की तरह नहीं खोज सकते हैं, कहानी काफी अलग थी, और यह सुनिश्चित करने के लिए बहुत चालाक होना चाहिए (प्रत्येक अग्रिम में) कि प्रत्येक टेप आंदोलन सबसे प्रभावी संभव होगा (यानी, सबसे अच्छा भाग लेंगे) प्रगति "विलय"। कुछ टेप भी पीछे की ओर पढ़ने में सक्षम थे, और इसका उपयोग रिवाइंडिंग समय से बचने के लिए भी किया जाता था। मेरा विश्वास करो, असली अच्छे टेप प्रकार देखने में काफी शानदार थे! हर समय से, छँटाई हमेशा एक महान कला रही है! :-)