सॉर्ट्स: कुंजी बनाम सीएमपी

जब पायथन 2 में छँटाई होती है, तो इस छँटाई को "कॉन्फ़िगर" करने के कम से कम दो तरीके होते हैं: ये key और cmp पैरामीटर हैं। पहला केवल पायथन 2.4 में जोड़ा गया था, और दूसरा पायथन 3.0 में हटा दिया गया था। इन तथ्यों से लगता है कि key वास्तव में बेहतर है। कौन इससे सहमत नहीं है या निश्चित नहीं है - मैं बिल्ली के लिए पूछता हूं।

सबसे पहले, प्रलेखन में थोड़ा भ्रमण ताकि सब कुछ बहुत गड़बड़ न दिखे।

पायथन आमतौर पर छँटाई के लिए या तो बिल्ट-इन `सॉर्टेड` या` लिस्ट.शॉर्ट` का उपयोग करता है। वास्तव में कॉल करें

 sorted(iterable, **kwargs) 

कोड के बराबर

 lst = list(iterable); lst.sort(**kwargs); lst 

इसलिए हम `सूची.शॉर्ट` पर अधिक ध्यान केंद्रित करेंगे।

`list.sort` तीन वैकल्पिक पैरामीटर लेता है:` key` एक फ़ंक्शन (वास्तव में कोई भी कॉल करने योग्य ऑब्जेक्ट) है जो एक सूची आइटम लेता है और उस ऑब्जेक्ट को वापस करता है जिसका उपयोग मूल सूची आइटम के बजाय सॉर्टिंग के दौरान तुलना करते समय किया जाएगा; `cmp` एक फ़ंक्शन है जो किसी सूची के दो तत्वों को लेता है और पारित किए गए मापदंडों के बीच संबंध के आधार पर -1, 0, या 1 देता है; `उलट` - अगर` सच`, तो सूची को उल्टे क्रम में क्रमबद्ध किया जाएगा।

तो, क्या उपयोग करें यदि, उदाहरण के लिए, आपको `आईडी` फ़ील्ड द्वारा ऑब्जेक्ट की सूची को सॉर्ट करने की आवश्यकता है? आइए `cmp` और` key` दृष्टिकोण देखें:

 lst.sort(cmp=lambda x, y: cmp(x['id'], y['id'])) #     

 lst.sort(key=lambda x: x['id']) # , ,  

यह गति की कीमत पर निराधार नहीं होगा, परीक्षण के एक जोड़े:

 >>> lst = [{'id': x, 'name': 'test'} for x in xrange(1000)] >>> random.shuffle(lst) >>> def with_cmp(lst): ... lst.sort(cmp=lambda x, y: cmp(x['id'], y['id'])) ... >>> def with_key(lst): ... lst.sort(key=lambda x: x['id']) ... >>> timeit.timeit('with_cmp(lst[:])', setup='from __main__ import with_cmp, lst', number=1000) 2.7731389999389648 >>> timeit.timeit('with_key(lst[:])', setup='from __main__ import with_key, lst', number=1000) 0.55310797691345215 

इतना बड़ा अंतर क्यों है? तथ्य यह है कि यदि `की` पैरामीटर मौजूद है, तो इसका मूल्य सूची के सभी तत्वों पर केवल एक बार छंटाई ( सॉर्ट ) के लिए लागू होता है, जबकि` सीएमपी` मूल्य का उपयोग प्रत्येक तुलना के लिए किया जाता है! पायथन में प्रयुक्त टीम सॉर्ट ( एल्गोरिथम पार्सिंग ) को देखते हुए नॉगल (एन) की औसत रेटिंग है, हम मान सकते हैं कि हमारे उदाहरण में, `सीएमपी` से लंबोदर को कई बार अधिक बार कहा जाता था।

वास्तव में, आप इसे और भी तेज कर सकते हैं - धीमी गति से पायथन फ़ंक्शन का उपयोग नहीं कर रहा है, लेकिन एक मूल सी में लिखा गया है। ऑपरेटर पुस्तकालय यहां बहुत मदद करता है। यहां देखें कि ऑपरेटर के साथ परिणाम क्या दिखेंगे । itemgetter (अभी भी docs.python.org/library/operator.html#operator.attrgetter , methodcalled और बहुत अधिक स्वादिष्ट हैं):

 >>> from operator import itemgetter >>> def with_op(lst): ... lst.sort(key=itemgetter('id')) ... >>> timeit.timeit('with_op(lst[:])', setup='from __main__ import with_op, lst, itemgetter', number=1000) 0.4054520057716877 

पहले विकल्प की तुलना में कुल, 20 7x गति की वृद्धि - खराब नहीं, सही?

स्पष्टता के बारे में, गति के साथ समझा। मुझे नहीं लगता कि `की` \ _ cmp` का उपयोग करना स्वाद का विषय होना चाहिए, क्योंकि बाद में बहने वाली अमूर्तता का एक बड़ा उदाहरण है । सब कुछ तब तक ठीक है जब तक कि अंतर्निहित `cmp` का उपयोग` cmp` पैरामीटर के मान फ़ंक्शन में किया जाता है, जो छँटाई तंत्र के विवरण को छुपाता है, लेकिन जब आपसे निम्न कोड के आउटपुट की भविष्यवाणी करने के लिए कहा जाएगा तो आप क्या करेंगे:

 >>> def numeric_compare(x, y): return x - y >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare) 

आपको निश्चित रूप से याद है कि `cmp` को -1, 0, या 1 वापस करना चाहिए, लेकिन वास्तव में क्या? यदि `x`` y` से बड़ा है, तो क्या यह 1 या -1 होना चाहिए? यदि आप 2 लौटाते हैं, तो क्या कोई त्रुटि होगी या 2 की व्याख्या 1 के रूप में की जाएगी? बेशक, आप सवालों के जवाब आधे मिनट में पा सकते हैं, लेकिन क्यों देखें? मेरा मानना ​​है कि बेहतर अमूर्तता का उपयोग करना बेहतर है, अर्थात, 'की' पैरामीटर।

सवालों की चेतावनी देते हुए, मैं मानता हूं कि शायद ऐसे कार्यों के दुर्लभ उदाहरण हैं जहां `की` पर्याप्त नहीं है। लेकिन ये बिल्कुल अपवाद हैं, और उनके लिए भी व्यंजनों हैं (उदाहरण के लिए, यह एक है सॉर्ट मिनी-हाउ टू: cmp_to_key )।

आपका ध्यान देने के लिए धन्यवाद।

---

पुनश्च चुनौती। निम्न कोड क्यों अजीब व्यवहार करता है:

 >>> ls = [(1,2,3), (2,1,3), (2,3,1)] >>> ls.sort(key=reversed) >>> ls [(1, 2, 3), (2, 3, 1), (2, 1, 3)] >>> ls.sort(key=reversed) >>> ls [(2, 1, 3), (1, 2, 3), (2, 3, 1)] 

उत्तर है:
`उलटा` प्रकार की वस्तु लौटाता है` <प्रकार 'उलट'> `, जिसके लिए समृद्ध-संगति विधियाँ अपरिभाषित हैं। इसलिए, `list.sort` तुलना के लिए` id` ऑब्जेक्ट्स का उपयोग करता है, जो लगातार बदल रहे हैं। `उलट` के बजाय` ऑपरेटर.मिटेमेटर (स्लाइस (कोई नहीं, कोई नहीं, -1)) `का प्रयोग करें।