in-place बनाम O(1) स्पेस: Python उदाहरणों से फर्क समझें

यह लेख in-place, strict in-place और O(1) स्पेस के फर्क को Python सूची के उदाहरणों से समझाता है: बफ़र-आधारित बनाम स्वैप-आधारित तरीकों, रिकर्शन बनाम इटरेशन.

जब हम स्पेस कॉम्प्लेक्सिटी और “in-place” व्यवहार की बात करते हैं, तो डायनेमिक एरेज़, स्टैक फ़्रेम और मध्यवर्ती स्ट्रक्चर जैसे ही तस्वीर में आते हैं, सीमाएँ धुंधली पड़ जाती हैं। दिखने में साधारण-सा स्निपेट भी चौंकाने वाली बारीकी वाली बहस छेड़ सकता है। मान लें, एक फ़ंक्शन है जो एक सूची को दूसरी में उड़ेल देता है और फिर सबकुछ वापस लौटा देता है। क्या यह in-place है? क्या यह O(1) स्पेस है? या फिर अस्थायी सूची पूरी तरह वर्गीकरण बदल देती है?

समस्या की रूपरेखा

यहाँ एक छोटा-सा फ़ंक्शन है जो तत्वों को दूसरी सूची में पॉप करके मूल सूची को उलट देता है और फिर पॉप करके वापस मूल क्रम में ला देता है। अंततः सूची वहीं लौट आती है जहाँ से शुरू हुई थी, लेकिन बीच में एक अतिरिक्त सूची आवंटित होती है।

def flip_twice(seq):
    buf = []
    while seq:
        buf.append(seq.pop())
    while buf:
        seq.append(buf.pop())

पहली नज़र में लग सकता है कि कुल तत्वों की संख्या स्थिर रहती है और किसी भी क्षण len(seq) + len(buf) मूल आकार के बराबर है, तो अतिरिक्त मेमोरी किसी तरह “स्थिर” है। लेकिन वर्गीकरण इस बात पर निर्भर करता है कि मेमोरी वास्तविक रूप से कैसे उपयोग होती है, केवल इस पर नहीं कि कुल मिलाकर संरक्षित है।

परिभाषाओं का वास्तविक अर्थ

इस पर तीन नजरियों से देखा जा सकता है। कोई एल्गोरिथ्म in-place कहलाता है जब वह केवल निश्चित मात्रा की अतिरिक्त मेमोरी (auxiliary space) का उपयोग करता है और इनपुट को उसी स्थान पर रूपांतरित करता है। एक सख़्त अवधारणा—strict in-place—किसी भी अप्रत्यक्ष अतिरिक्त मेमोरी को बाहर रखती है, जैसे रिकर्शन से स्टैक का बढ़ना या जेनरेटर चेन। अंततः, O(1) स्पेस का मतलब है कि आवश्यक सहायक मेमोरी इनपुट के आकार के साथ नहीं बढ़ती, भले ही गणना के दौरान वह मेमोरी इधर-उधर “स्थानांतरित” होती रहे। ये शब्द अच्छी तरह परिभाषित हैं, हालांकि व्यवहार में लोग इस बात पर असहमत हो सकते हैं कि किस प्रकार की स्पेस—auxiliary एरे बनाम कॉल स्टैक—को गिना जाना चाहिए। यही असहमति बताती है कि परिभाषाओं को स्पष्ट करना क्यों जरूरी है।

यह उदाहरण in-place और O(1) क्यों नहीं है

ऊपर वाला फ़ंक्शन एक नई सूची आवंटित करता है और उसे मूल सूची जितने ही तत्वों से भरता है। भले ही बफ़र बढ़ते समय स्रोत सूची छोटी होती जाती है, आप वही स्टोरेज पुनः प्रयोग नहीं कर रहे; आप अस्थायी सूची में तत्व रखने के लिए अतिरिक्त स्पेस आवंटित कर रहे हैं। इनपुट जितना बड़ा होगा, अस्थायी स्ट्रक्चर उतना ही बड़ा होगा। यानी सहायक स्पेस इनपुट आकार के साथ स्केल करती है। परिभाषाओं के अनुसार, यह न तो in-place है, न strict in-place, और न ही O(1) स्पेस।

यह भी ध्यान देने योग्य है कि चलने के दौरान मूल सूची खाली होकर फिर से बनती है, यानी डेटा इनपुट कंटेनर को असल में छोड़ देता है और बाद में वापस लिखा जाता है। यह फिर रेखांकित करता है कि काम in-place नहीं हो रहा। चर्चा अक्सर डायनेमिक एरे, मेमोरी की निरंतरता, या append के व्यवहार जैसी इम्प्लीमेंटेशन-डिटेल्स में उलझ जाती है; यहाँ ये बातें वर्गीकरण नहीं बदलतीं। कुछ डेवलपर इस पर भी बहस करते हैं कि append() को O(1) माना जाए या नहीं, जिससे समय-विश्लेषण जटिल हो जाता है—लेकिन स्पेस वाला तर्क अपने आप में पर्याप्त है।

वास्तव में in-place विकल्प

दूसरी सूची बनाए बिना भी आप वही मध्य-अवस्था—आधे रास्ते पर उलटी सूची—प्राप्त कर सकते हैं। नीचे दिया गया संस्करण सममित तत्वों को in-place स्वैप करता है, और फिर यही दोबारा करता है, जिससे सूची अंत में वैसी ही रह जाती है जैसी शुरू में थी।

def spin_twice(items):
    for k in range(len(items) // 2):
        items[k], items[-k - 1] = items[-k - 1], items[k]
    for k in range(len(items) // 2):
        items[k], items[-k - 1] = items[-k - 1], items[k]

यह तरीका पूरी तरह मूल स्टोरेज के भीतर काम करता है। यह in-place है क्योंकि सभी बदलाव वहीं होते हैं जहाँ डेटा रहता है। यह strict in-place है क्योंकि इसमें न रिकर्शन है न किसी और तरह का अप्रत्यक्ष स्टैक-वृद्धि। और यह O(1) सहायक स्पेस लेता है, क्योंकि अतिरिक्त मेमोरी की जरूरत इनपुट के आकार पर निर्भर नहीं करती; इटरेशन की अपनी सीमाएँ तय हैं। यदि आप पहली पास के मध्य में अस्थायी स्थिति प्रिंट करके उसे पहले वाले बफ़र-आधारित फ़ंक्शन की पहली चरण की मध्य-अवस्था से मिलाएँ, तो वही उल्टा क्रम दिखाई देगा।

एक non-strict in-place रूपांतर

यही स्वैप-तर्क यदि आप रिकर्सिव रूप में लिखते हैं, तो in-place गुण बना रहता है, पर कॉल-गहराई बढ़ने के कारण strictness खो जाती है। प्रयुक्त सटीक परिभाषा पर निर्भर करते हुए, स्टैक स्पेस को O(1) में गिना भी जा सकता है या नहीं भी; किसी भी हाल में रिकर्शन की गहराई इनपुट आकार के साथ बढ़ती है।

def spin_twice_rec(items, idx = 0):
    items[idx], items[-idx - 1] = items[-idx - 1], items[idx]
    if idx < len(items) // 2:
        spin_twice_rec(items, idx + 1)
    items[idx], items[-idx - 1] = items[-idx - 1], items[idx]

यह अब भी in-place है क्योंकि यह बिना कोई सहायक कंटेनर बनाए सीधे सूची को बदलता है। लेकिन यह strict in-place नहीं रहता, क्योंकि इनपुट बढ़ने पर रिकर्शन अप्रत्यक्ष स्टैक-वृद्धि लाता है। इसे स्पेस में O(1) कहना या न कहना इस बात पर टिका है कि क्या आप स्टैक फ़्रेमों को गणना में शामिल करते हैं; एक वाजिब मत यह है कि यह O(1) नहीं है।

यह अंतर क्यों मायने रखता है

स्पेस कॉम्प्लेक्सिटी पर चर्चा अक्सर इम्प्लीमेंटेशन डिटेल्स या “सिर्फ एक अतिरिक्त सूची” जैसी अनौपचारिक भाषा में उलझ जाती है। स्पष्ट और साझा परिभाषाएँ आपको अनुमान लगाए बिना कोड का आकलन करने देती हैं। चाहे आपको किसी डिज़ाइन निर्णय का औचित्य देना हो, एल्गोरिथ्मिक गारंटी की समीक्षा करनी हो, या मेमोरी उपयोग का ऑडिट—अस्थायी बफ़र आवंटित करना और in-place स्वैप करना, इन दोनों में ठोस फर्क पड़ता है। इसके अलावा, लोग कभी-कभी उन पैटर्न के लिए भी O(1) स्पेस का दावा कर देते हैं जो वाकई अतिरिक्त मेमोरी आवंटित करते हैं—शायद इसलिए कि वे तत्वों के “संरक्षण” पर ध्यान देते हैं, न कि इस तंत्र पर कि निष्पादन के दौरान वे तत्व कहाँ रहते हैं। जब आप बातचीत को auxiliary स्पेस, अप्रत्यक्ष स्टैक और in-place रूपांतरण पर टिकाते हैं, तो वर्गीकरण सीधा हो जाता है।

निष्कर्ष

स्पेस का वर्गीकरण करते समय साफ़-साफ़ बताइए कि आप क्या गिन रहे हैं। यदि आपकी परिभाषा में सहायक डेटा-स्ट्रक्चर और अप्रत्यक्ष स्टैक फ़्रेम शामिल हैं, तो बफ़र-आधारित तरीका न तो in-place है, न O(1); जबकि इटरेटिव स्वैप वाला संस्करण strict in-place और O(1) है। अगर आप स्टैक स्पेस को बाहर रखते हैं, तो रिकर्सिव स्वैप को in-place कहा जा सकता है, पर वह strict नहीं होगा। यदि मध्य-अवस्थाओं को लेकर संदेह हो, तो दोनों रूपों को इस तरह साधनबद्ध करें कि आधे रास्ते पर प्रिंट करें और दिखने वाली सूची के क्रम की तुलना करें। सबसे अहम, शुरुआत में ही परिभाषाओं पर सहमति बना लें ताकि बातचीत उलझे नहीं।