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

बाइनरी सर्च क्या है?

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

द्विभाजित मॉड्यूल: क्रमबद्ध सूची संचालन को सरल बनाना

हालांकि बाइनरी खोज प्रभावी है, हर बार कार्यान्वयन लिखना कठिन हो सकता है। लेकिन क्या होगा यदि आप कोड की केवल एक पंक्ति के साथ समान ऑपरेशन कर सकें? यहीं पर पायथन का बाइसेक्ट मॉड्यूल आता है। पायथन की मानक लाइब्रेरी का हिस्सा, बाइसेक्ट आपको प्रत्येक प्रविष्टि के बाद इसे क्रमबद्ध करने की आवश्यकता के बिना एक क्रमबद्ध सूची बनाए रखने में मदद करता है। यह एक सरल द्विभाजन एल्गोरिथ्म का उपयोग करके ऐसा करता है।

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

समद्विभाजित मॉड्यूल का उपयोग करना: एक व्यावहारिक उदाहरण

आइए मॉड्यूल आयात करके शुरू करें:

import bisect

उदाहरण 1: क्रमबद्ध सूची में एक संख्या सम्मिलित करना

मान लीजिए हमारे पास संख्याओं की एक क्रमबद्ध सूची है:

data = [1, 3, 5, 6, 8]

सूची को क्रमबद्ध रखते हुए एक नया नंबर डालने के लिए, बस इसका उपयोग करें:

bisect.insort(data, 7)

इस कोड को चलाने के बाद, डेटा इस तरह दिखेगा:

[1, 3, 5, 6, 7, 8]

उदाहरण 2: सम्मिलन बिंदु ढूँढना

क्या होगा यदि आप केवल यह जानना चाहते हैं कि कोई संख्या वास्तव में डाले बिना कहाँ डाली जाएगी? आप bisect_left या bisect_right फ़ंक्शन का उपयोग कर सकते हैं:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

यह हमें बताता है कि सूची को क्रमबद्ध रखने के लिए संख्या 4 को सूचकांक 2 में डाला जाना चाहिए।

उदाहरण 3: गतिशील सूची में क्रमबद्ध क्रम बनाए रखना

मान लें कि आप एक गतिशील रूप से बढ़ती सूची का प्रबंधन कर रहे हैं और यह सुनिश्चित करते हुए कि यह क्रमबद्ध रहे, तत्वों को सम्मिलित करने की आवश्यकता है:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

यह प्रत्येक चरण में तत्वों को सम्मिलित करते समय सूची को आउटपुट करेगा:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

उदाहरण 4: कस्टम ऑब्जेक्ट के साथ समद्विभाजक का उपयोग करना

मान लीजिए कि आपके पास कस्टम ऑब्जेक्ट्स की एक सूची है, जैसे टुपल्स, और आप उन्हें एक विशिष्ट मानदंड के आधार पर सम्मिलित करना चाहते हैं:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

या आप प्रत्येक टुपल के दूसरे तत्व के आधार पर सम्मिलित करना चाह सकते हैं:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

क्रिया में द्विभाजित: शब्दों की खोज

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

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

या किसी विशिष्ट उपसर्ग वाले शब्दों के समूह में पहला शब्द ढूंढने के लिए:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

हालांकि, ध्यान रखें कि bisect_left वह इंडेक्स लौटाता है जहां लक्ष्य डाला जाना चाहिए, न कि यह कि लक्ष्य सूची में मौजूद है या नहीं।

समद्विभाजित और अंतःविषय के भिन्न रूप

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

हुड के नीचे द्विभाजित

बाइसेक्ट मॉड्यूल की शक्ति बाइनरी सर्च एल्गोरिदम के कुशल कार्यान्वयन में निहित है। उदाहरण के लिए, जब आप bisect.bisect_left को कॉल करते हैं, तो फ़ंक्शन अनिवार्य रूप से नए तत्व के लिए सही प्रविष्टि बिंदु निर्धारित करने के लिए सूची पर एक बाइनरी खोज करता है।

यहां बताया गया है कि यह हुड के नीचे कैसे काम करता है:

1. प्रारंभिकरण: फ़ंक्शन दो पॉइंटर्स, लो और हाय से शुरू होता है, जो सूची के भीतर खोज सीमा की निचली और ऊपरी सीमा का प्रतिनिधित्व करता है। प्रारंभ में, lo को सूची के प्रारंभ (सूचकांक 0) पर सेट किया गया है, और hi को सूची के अंत पर सेट किया गया है (सूचकांक सूची की लंबाई के बराबर है)। लेकिन आप सूची की एक विशिष्ट श्रेणी में खोजने के लिए कस्टम लो और हाय मान भी निर्दिष्ट कर सकते हैं।

2. द्विभाजन: एक लूप के भीतर, फ़ंक्शन लो और हाय के बीच मध्यबिंदु (मध्य) की गणना करता है। इसके बाद यह आपके द्वारा सम्मिलित किए जाने वाले लक्ष्य मान के साथ मध्य मूल्य की तुलना करता है।

3. तुलना:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. समाप्ति: यह प्रक्रिया जारी रहती है, हर बार खोज सीमा आधी हो जाती है, जब तक कि लो हाय के बराबर न हो जाए। इस बिंदु पर, लो (या हाय) सही सूचकांक का प्रतिनिधित्व करता है जहां सूची के क्रमबद्ध क्रम को बनाए रखने के लिए लक्ष्य डाला जाना चाहिए।

2. सम्मिलन: इन्सॉर्ट फ़ंक्शन के लिए, एक बार bisect_left का उपयोग करके सही सूचकांक पाया जाता है, तो लक्ष्य को उस स्थिति में सूची में डाला जाता है।

यह दृष्टिकोण सुनिश्चित करता है कि प्रविष्टि प्रक्रिया कुशल है, सूची स्थानांतरण ऑपरेशन के कारण खोज के लिए ओ (लॉग एन) और प्रविष्टि के लिए ओ (एन) की समय जटिलता के साथ। यह प्रत्येक प्रविष्टि के बाद सूची को क्रमबद्ध करने की तुलना में काफी अधिक कुशल है, विशेष रूप से बड़े डेटासेट के लिए।

bisect_left कोड उदाहरण:

    if lo 



insort_left कोड उदाहरण:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  निष्कर्ष


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