इस पाठ में पाइथॉन और सीपीथॉन शब्द, जो भाषा का संदर्भ कार्यान्वयन है, का परस्पर उपयोग किया जाता है। यह लेख विशेष रूप से CPython को संबोधित करता है और Python के किसी अन्य कार्यान्वयन से संबंधित नहीं है।

पायथन एक सुंदर भाषा है जो एक प्रोग्रामर को पर्दे के पीछे वास्तविक कार्यान्वयन की जटिलता को छोड़कर अपने विचारों को सरल शब्दों में व्यक्त करने की अनुमति देती है।

जिन चीजों को यह अलग करता है उनमें से एक है छंटाई।

आप इस प्रश्न का उत्तर आसानी से पा सकते हैं कि "पायथन में सॉर्टिंग कैसे लागू की जाती है?" जो लगभग हमेशा एक अन्य प्रश्न का उत्तर देता है: "पायथन किस सॉर्टिंग एल्गोरिदम का उपयोग करता है?"।

हालाँकि, यह अक्सर कुछ दिलचस्प कार्यान्वयन विवरण पीछे छोड़ देता है।

मुझे लगता है कि एक कार्यान्वयन विवरण है जिस पर पर्याप्त चर्चा नहीं हुई है, भले ही इसे सात साल पहले पायथन 3.7 में पेश किया गया था:

sorted() और list.sort() को सामान्य मामलों के लिए 40-75% तक तेज करने के लिए अनुकूलित किया गया है। (बीपीओ-28685 में इलियट गोरोखोव्स्की द्वारा योगदान।)

लेकिन इससे पहले कि हम शुरू करें...

पायथन में सॉर्टिंग का संक्षिप्त पुनः परिचय

जब आपको पायथन में किसी सूची को क्रमबद्ध करने की आवश्यकता होती है, तो आपके पास दो विकल्प होते हैं:

• एक सूची विधि: सूची.सॉर्ट(*, कुंजी=कोई नहीं, उल्टा=गलत), जो दी गई सूची को उसके स्थान पर क्रमबद्ध करती है
• एक अंतर्निर्मित फ़ंक्शन: sorted(iterable, /, *, key=None, revers= गलत), जो अपने तर्क को संशोधित किए बिना क्रमबद्ध सूची लौटाता है

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

सॉर्टेड हमेशा एक सूची लौटाता है क्योंकि यह आंतरिक रूप से list.sort का उपयोग करता है।

यहां सीपीथॉन के क्रमबद्ध सी कार्यान्वयन का एक मोटा समकक्ष शुद्ध पायथन में लिखा गया है:

def sorted(iterable: Iterable[Any], key=None, reverse=False):
    new_list = list(iterable)
    new_list.sort(key=key, reverse=reverse)
    return new_list

हां, यह इतना आसान है।

पाइथॉन सॉर्टिंग को कैसे तेज़ बनाता है

जैसा कि सॉर्टिंग के लिए पायथन का आंतरिक दस्तावेज़ कहता है:

कभी-कभी धीमी, सामान्य PyObject_RichCompareBool के लिए तेज़ प्रकार-विशिष्ट तुलनाओं को प्रतिस्थापित करना संभव होता है

और संक्षेप में इस अनुकूलन का वर्णन इस प्रकार किया जा सकता है:

जब कोई सूची सजातीय होती है, तो पायथन प्रकार-विशिष्ट तुलना फ़ंक्शन का उपयोग करता है

सजातीय सूची क्या है?

एक सजातीय सूची एक ऐसी सूची है जिसमें केवल एक प्रकार के तत्व होते हैं।

उदाहरण के लिए:

homogeneous = [1, 2, 3, 4]

दूसरी ओर, यह एक सजातीय सूची नहीं है:

heterogeneous = [1, "2", (3, ), {'4': 4}]

दिलचस्प बात यह है कि, आधिकारिक पायथन ट्यूटोरियल कहता है:

सूचियां परिवर्तनशील हैं, और उनके तत्व आम तौर पर सजातीय हैं और सूची पर पुनरावृत्ति करके उन तक पहुंचा जा सकता है

टुपल्स के बारे में एक अतिरिक्त टिप्पणी

वही ट्यूटोरियल कहता है:

ट्यूपल्स अपरिवर्तनीय हैं, और आमतौर पर तत्वों का एक विषम अनुक्रम होता है

इसलिए यदि आप कभी सोचते हैं कि टुपल या सूची का उपयोग कब करना है तो यहां सामान्य नियम दिया गया है:

यदि तत्व एक ही प्रकार के हैं, तो सूची का उपयोग करें, अन्यथा टपल का उपयोग करें

रुको, और सरणियों के बारे में क्या?

पायथन संख्यात्मक मानों के लिए एक सजातीय सरणी कंटेनर ऑब्जेक्ट लागू करता है।

हालाँकि, पायथन 3.12 के अनुसार, ऐरे अपनी स्वयं की सॉर्ट विधि लागू नहीं करते हैं।

उन्हें सॉर्ट करने का एकमात्र तरीका सॉर्टेड का उपयोग करना है, जो आंतरिक रूप से सरणी से एक सूची बनाता है, इस प्रक्रिया में किसी भी प्रकार से संबंधित जानकारी को मिटा देता है।

प्रकार-विशिष्ट तुलना फ़ंक्शन का उपयोग करने से क्यों मदद मिलती है?

पाइथन में तुलना करना महंगा है, क्योंकि पायथन कोई भी वास्तविक तुलना करने से पहले विभिन्न जांच करता है।

जब आप पायथन में दो मानों की तुलना करते हैं तो हुड के नीचे क्या होता है, इसकी एक सरल व्याख्या यहां दी गई है:

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

इसके शीर्ष पर, प्रत्येक प्रकार के अपने तुलनात्मक कार्य अतिरिक्त जांच लागू करते हैं।

उदाहरण के लिए, स्ट्रिंग्स की तुलना करते समय, पायथन जांच करेगा कि क्या स्ट्रिंग वर्ण मेमोरी के एक से अधिक बाइट लेते हैं, और फ्लोट तुलना फ्लोट की एक जोड़ी और एक फ्लोट और एक इंट की अलग-अलग तुलना करेगी।

अधिक विस्तृत विवरण और आरेख यहां पाया जा सकता है: CPython में डेटा-अवेयर सॉर्ट ऑप्टिमाइज़ेशन जोड़ना

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

सूची तत्व के प्रकारों की पहले से जाँच करना

यह जानने का कोई जादुई तरीका नहीं है कि किसी सूची के सभी तत्व एक ही प्रकार के हैं या नहीं, सूची को दोहराने और प्रत्येक तत्व की जांच करने के अलावा।

पायथन लगभग बिल्कुल यही करता है - list.sort में पारित कुंजी फ़ंक्शन द्वारा उत्पन्न सॉर्टिंग कुंजियों के प्रकारों की जांच करना या पैरामीटर के रूप में क्रमबद्ध करना

कुंजियों की एक सूची बनाना

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

अत्यधिक सरलीकृत तरीके से, कुंजी निर्माण को निम्नलिखित पायथन कोड के रूप में व्यक्त किया जा सकता है।

यदि कुंजी कोई नहीं है: कुंजियाँ = सूची_आइटम अन्य: कुंजी = [सूची_आइटम में सूची_आइटम के लिए कुंजी(सूची_आइटम)]

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

ध्यान दें, CPython में आंतरिक रूप से उपयोग की जाने वाली कुंजियाँ CPython ऑब्जेक्ट संदर्भों की C सरणी हैं, न कि Python सूची

एक बार कुंजियाँ बन जाने के बाद, पायथन उनके प्रकारों की जाँच करता है।

कुंजी के प्रकार की जाँच करना

कुंजियों के प्रकारों की जांच करते समय, पायथन का सॉर्टिंग एल्गोरिदम यह निर्धारित करने का प्रयास करता है कि क्या कुंजी सरणी में सभी तत्व या तो str, int, फ्लोट या टुपल हैं, या बस एक ही प्रकार के हैं, आधार प्रकारों के लिए कुछ बाधाओं के साथ।

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

अंतर बाधाएँ

int को

नहीं एक बिग्नम होना चाहिए

व्यावहारिक रूप से इसका मतलब यह है कि इस अनुकूलन के काम करने के लिए, पूर्णांक

2^30 - 1 से कम होना चाहिए (यह प्लेटफ़ॉर्म के आधार पर भिन्न हो सकता है)

एक साइड नोट के रूप में, यहां एक बेहतरीन लेख है जो बताता है कि पायथन बड़े पूर्णांकों को कैसे संभालता है: # पायथन सुपर लंबे पूर्णांकों को कैसे लागू करता है?

str बाधाएं

स्ट्रिंग के सभी वर्णों को 1 बाइट से कम मेमोरी लेनी चाहिए, जिसका अर्थ है कि उन्हें 0-255 की सीमा में पूर्णांक मानों द्वारा दर्शाया जाना चाहिए

व्यवहार में, इसका मतलब है कि स्ट्रिंग में केवल लैटिन वर्ण, रिक्त स्थान और ASCII तालिका में पाए जाने वाले कुछ विशेष वर्ण शामिल होने चाहिए।

फ्लोट बाधाएँ

इस अनुकूलन के काम करने के लिए फ़्लोट्स के लिए कोई बाधा नहीं है।

टपल बाधाएँ

केवल पहले तत्व का प्रकार जांचा गया है
यह तत्व स्वयं एक टुपल नहीं होना चाहिए
यदि सभी टुपल्स अपने पहले तत्व के लिए समान प्रकार साझा करते हैं, तो तुलना अनुकूलन उन पर लागू किया जाता है
अन्य सभी तत्वों की तुलना सामान्य रूप से की जाती है

मैं इस ज्ञान को कैसे लागू कर सकता हूँ?

सबसे पहले, क्या यह जानना दिलचस्प नहीं है?

दूसरी बात, पायथन डेवलपर साक्षात्कार में इस ज्ञान का उल्लेख करना एक अच्छा स्पर्श हो सकता है।

जहां तक ​​वास्तविक कोड विकास का सवाल है, इस अनुकूलन को समझने से आपको सॉर्टिंग प्रदर्शन को बेहतर बनाने में मदद मिल सकती है।

मूल्यों के प्रकार का बुद्धिमानी से चयन करके अनुकूलन करें

इस अनुकूलन को पेश करने वाले पीआर में बेंचमार्क के अनुसार, एक ऐसी सूची को सॉर्ट करना जिसमें केवल फ्लोट्स की सूची होती है न कि अंत में एक भी पूर्णांक के साथ फ्लोट्स की सूची लगभग दोगुनी तेज होती है।

इसलिए जब अनुकूलन का समय हो, तो सूची को इस तरह से रूपांतरित करें

floats_and_int = [1.0, -1.0, -0.5, 3]

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

इस तरह दिखने वाली सूची में

just_floats = [1.0, -1.0, -0.5, 3.0] # ध्यान दें कि 3.0 अब एक फ्लोट है

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

प्रदर्शन में सुधार हो सकता है।

वस्तुओं की सूची के लिए कुंजियों का उपयोग करके अनुकूलन करें

हालांकि पायथन का सॉर्टिंग ऑप्टिमाइज़ेशन अंतर्निहित प्रकारों के साथ अच्छी तरह से काम करता है, यह समझना महत्वपूर्ण है कि यह कस्टम कक्षाओं के साथ कैसे इंटरैक्ट करता है।

कस्टम कक्षाओं की वस्तुओं को सॉर्ट करते समय, पायथन आपके द्वारा परिभाषित तुलना विधियों पर निर्भर करता है, जैसे __lt__ (इससे कम) या __gt__ (इससे अधिक)।

हालाँकि, प्रकार-विशिष्ट अनुकूलन कस्टम कक्षाओं पर लागू नहीं होता है।

पायथन हमेशा इन वस्तुओं के लिए सामान्य तुलना पद्धति का उपयोग करेगा।

यहां एक उदाहरण है:

क्लास मायक्लास: def __init__(स्वयं, मान): स्व.मूल्य = मूल्य def __lt__(स्वयं, अन्य): स्व.मूल्य लौटाएँ if key is None: keys = list_items else: keys = [key(list_item) for list_item in list_item] इस मामले में, पायथन तुलना के लिए __lt__ विधि का उपयोग करेगा, लेकिन यह प्रकार-विशिष्ट अनुकूलन से लाभान्वित नहीं होगा। सॉर्टिंग अभी भी सही ढंग से काम करेगी, लेकिन यह अंतर्निहित प्रकारों को सॉर्ट करने जितनी तेज़ नहीं हो सकती है।

यदि कस्टम ऑब्जेक्ट को सॉर्ट करते समय प्रदर्शन महत्वपूर्ण है, तो एक मुख्य फ़ंक्शन का उपयोग करने पर विचार करें जो एक अंतर्निहित प्रकार लौटाता है:

sorted_list = sorted(my_list, key=lambda x: x.value)

if key is None:
    keys = list_items
else:
    keys = [key(list_item) for list_item in list_item]

अंतभाषण

समय से पहले अनुकूलन, विशेष रूप से पायथन में, बुरा है।

आपको अपने संपूर्ण एप्लिकेशन को CPython में विशिष्ट अनुकूलन के आसपास डिज़ाइन नहीं करना चाहिए, लेकिन इन अनुकूलन के बारे में जागरूक होना अच्छा है: अपने टूल को अच्छी तरह से जानना अधिक कुशल डेवलपर बनने का एक तरीका है।

इस तरह के अनुकूलन के प्रति सचेत रहने से आप स्थिति की मांग होने पर उनका लाभ उठा सकते हैं, खासकर जब प्रदर्शन महत्वपूर्ण हो जाता है:

एक ऐसे परिदृश्य पर विचार करें जहां आपकी छँटाई टाइमस्टैम्प पर आधारित हो: डेटाटाइम ऑब्जेक्ट के बजाय पूर्णांकों की एक सजातीय सूची (यूनिक्स टाइमस्टैम्प) का उपयोग करने से इस अनुकूलन का प्रभावी ढंग से लाभ उठाया जा सकता है।

हालांकि, यह याद रखना महत्वपूर्ण है कि कोड पठनीयता और रखरखाव को ऐसे अनुकूलन पर प्राथमिकता दी जानी चाहिए।

हालाँकि इन निम्न-स्तरीय विवरणों के बारे में जानना महत्वपूर्ण है, लेकिन पायथन के उच्च-स्तरीय अमूर्तताओं की सराहना करना भी उतना ही महत्वपूर्ण है जो इसे इतनी उत्पादक भाषा बनाते हैं।

पायथन एक अद्भुत भाषा है, और इसकी गहराई का पता लगाने से आपको इसे बेहतर ढंग से समझने और एक बेहतर पायथन प्रोग्रामर बनने में मदद मिल सकती है।