पायथन क्विकॉर्ट - सूची समझ बनाम रिकर्सन (विभाजन दिनचर्या)

Question

मैंने तीन खूबसूरत क्विक्सॉर्ट्स को देखा और क्विकॉर्ट के साथ घूम रहा था। पायथन में मेरा कार्यान्वयन सी के समान था (पिवोट का चयन करें, इसके चारों ओर विभाजन और छोटे और बड़े विभाजनों पर पुनरावर्ती)। जो मैंने सोचा था पायथनिक नहीं था।

तो यह पाइथन में सूची समझ का उपयोग करके कार्यान्वयन है।

def qsort(list): 
    if list == []: 
     return [] 
    pivot = list[0] 
    l = qsort([x for x in list[1:] if x < pivot]) 
    u = qsort([x for x in list[1:] if x >= pivot]) 
    return l + [pivot] + u 

रिकर्सन मेथो qsortR को कॉल करने दें। अब मैंने देखा है कि qsortR बड़ी (आर) सूचियों के लिए qsort से बहुत धीमी गति से चलता है। असल में "अधिकतम रिकर्सन गहराई सीएमपी में पार हो गई" भर्ती विधि के लिए 1000 elems के लिए भी। जो मैं sys.setrecursionlimit में रीसेट करता हूं।

कुछ संख्या:

list-compr 1000 elems 0.491770029068 
recursion 1000 elems 2.24620914459 
list-compr 2000 elems 0.992327928543 
recursion 2000 elems 7.72630095482 

सभी कोड here है।

• क्यों इतना तेजी से सूची समझ है:

  मैं सवालों की एक जोड़ी है?

• पायथन में रिकर्सन पर सीमा पर कुछ ज्ञान। मैंने इसे पहले 100000 तक सेट किया था कि मुझे किस मामले में सावधान रहना चाहिए?
  • (वास्तव में क्या द्वारा 'पूंछ प्रत्यावर्तन के अनुकूलन' का मतलब है, यह कैसे किया जाता है?)
• सॉर्ट करने के लिए 1000000 तत्वों अपने लैपटॉप की स्मृति hogged (प्रत्यावर्तन विधि के साथ) की कोशिश कर रहा। अगर मैं इतने सारे तत्वों को सॉर्ट करना चाहता हूं तो मुझे क्या करना चाहिए? किस प्रकार के अनुकूलन संभव हैं?

Answer 1

1. क्यों इतना तेजी से सूची समझ है?

   क्योंकि सूची समझ का अर्थ सी लूप है जो पाइथन के for ब्लॉक का उपयोग करने के धीमे सामान्य तरीके से बहुत तेज़ है।

2. पायथन में रिकर्सन पर सीमा पर कुछ ज्ञान। मैंने इसे पहले 100000 तक सेट किया था कि मुझे किस मामले में सावधान रहना चाहिए?

   यदि आप स्मृति से बाहर हो जाते हैं।

3. 1000000 तत्वों को सॉर्ट करने की कोशिश कर रहा है मेरे लैपटॉप (रिकर्सन विधि के साथ)। अगर मैं इतने सारे तत्वों को सॉर्ट करना चाहता हूं तो मुझे क्या करना चाहिए? किस प्रकार के अनुकूलन संभव हैं?

   पायथन का रिकर्सन इस तरह के ओवरहेड देता है क्योंकि प्रत्येक फ़ंक्शन कॉल प्रत्येक कॉल पर बहुत सारी स्टैक मेमोरी स्पेस आवंटित करता है।

   सामान्य रूप से, पुनरावृत्ति उत्तर है (सांख्यिकीय रूप से 99% उपयोग मामलों में बेहतर प्रदर्शन प्रदान करेगा)।

   मेमोरी संरचनाओं के बारे में बात करते हुए, यदि आपके पास सरल डेटा संरचनाएं हैं, जैसे कि चार्स, इंटीग्रर्स, फ्लोट्स: array.array में अंतर्निहित उपयोग करें जो list से अधिक मेमोरी कुशल है।

Answer 2

क्या आपने partition के गैर-पुनरावर्ती कार्यान्वयन को लिखने का प्रयास किया है? मुझे संदेह है कि प्रदर्शन अंतर पूरी तरह से partition कार्यान्वयन है। आप अपने कार्यान्वयन में प्रत्येक तत्व के लिए रिकर्सिंग कर रहे हैं।

अद्यतन

यहां एक त्वरित कार्यान्वयन है। यह अभी भी तेज तेज़ या कुशल नहीं है, लेकिन यह आपके मूल रिकर्सिव से भी बेहतर है।

>>> def partition(data): 
... pivot = data[0] 
... less, equal, greater = [], [], [] 
... for elm in data: 
... if elm < pivot: 
... less.append(elm) 
... elif elm > pivot: 
... greater.append(elm) 
... else: 
... equal.append(elm) 
... return less, equal, greater 
... 
>>> def qsort2(data): 
... if data: 
... less, equal, greater = partition(data) 
... return qsort2(less) + equal + qsort2(greater) 
... return data 
... 

मुझे यह भी लगता है कि "पारंपरिक" संस्करण में बड़ी संख्या में अस्थायी सूचियां उत्पन्न हुई हैं।

Answer 3

स्मृति की वास्तव में बड़ी होने पर सूची की समझ को इन-प्लेस एल्गोरिदम में तुलना करने का प्रयास करें। 100K पूर्णांक संख्याओं को सॉर्ट करते समय नीचे दिया गया कोड निकट निष्पादन समय प्राप्त करता है, लेकिन संभवतः आप 1 एम पूर्णांक को सॉर्ट करते समय सूची समझ समाधान में फंस जाएंगे। मैंने 4 जीबी मशीन का उपयोग करके परीक्षण किए हैं। पूर्ण कोड: http://snipt.org/Aaaje2

class QSort: 
def __init__(self, lst): 
    self.lst = lst 

def sorted(self): 
    self.qsort_swap(0, len(self.lst)) 
    return self.lst 

def qsort_swap(self, begin, end): 
    if (end - begin) > 1: 
     pivot = self.lst[begin] 
     l = begin + 1 
     r = end 
     while l < r: 
      if self.lst[l] <= pivot: 
       l += 1 
      else: 
       r -= 1 
       self.lst[l], self.lst[r] = self.lst[r], self.lst[l] 

     l -= 1 
     self.lst[begin], self.lst[l] = self.lst[l], self.lst[begin]  
     # print begin, end, self.lst 
     self.qsort_swap(begin, l) 
     self.qsort_swap(r, end)