अजगर में विलय

Question

वर्तमान में मेरे विलय के कार्यान्वयन में बहुत लंबा समय लगता है, 1 मिलियन तत्वों वाली सूची के लिए सूची को सॉर्ट करने में 130 सेकंड से अधिक समय लगता है।

• क्या कोई मेरे कोड को देख सकता है और सुझाव दे सकता है कि मैं इसे सुधारने के लिए क्या कर सकता हूं?

• क्या मेरे कोड में कुछ विशेष है जो काफी लंबा समय ले रहा है?

कोड

def splitlist(L): #splits the list to a list of individual listed elements (e.g. [1,2] to [[1],[2]])
    envelop = lambda x: [x]
    return(list(map(envelop,L)))


def merge(L_1,L_2): #merges two (already sorted) lists to one sorted list
    N = []
    while len(L_1) > 0 and len(L_2) > 0:
        if L_1[0] > L_2[0]:
            N += [L_2.pop(0)]
        else:
            N += [L_1.pop(0)]
    if len(L_1) == 0:
        N += L_2
    else:
        N += L_1
        
    return(N)


#performs one round of pairwise merges (e.g. [[2],[1],[4],[3]] to [[1,2],[3,4]]), or [[5,10],[1,8],[2,3]] to [[1,2,3,5,8,10]])   
def mergelist(L): 
    N = []
    if len(L) % 2 == 0:
        for i in range(0,len(L)//2):
            N += [merge(L[2*i],L[2*i + 1])]
    else:
        for i in range(0,len(L)//2 - 1):
            N += [merge(L[2*i],L[2*i + 1])]
        N += [merge(merge(L[-3],L[-2]),L[-1])]
    
    return(N)

def mergesort(L): #recursively performs mergelist until there is only 1 sorted list remaining
    L = splitlist(L)
    while len(L) > 1:
        L = mergelist(L)
    return(L[0])

यहाँ लाख तत्वों को उत्पन्न करने के लिए मेरा कोड है:

rlist = random.sample(range(0,2000000),1000000)

Answer 1

pop(0)रैखिक समय लगता है। इसे अलग-अलग, ओ (1) समय में करें। मानक तरीका सूचकांक चर का उपयोग करता है। कुछ और पायथोनिक तरीकों के लिए इस सवाल का जवाब देखें । या आप परिणाम pop()के अंत में दाएं से बाएं, विलय का उपयोग कर सकते हैं reverse()।

बाद करने का एक तरीका:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    while L1 and L2:
        L = L1 if L1[-1] > L2[-1] else L2
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

अन्य परिवर्तन जो मैंने किए और जिन्हें आप अपने कोड के अन्य भागों में भी लागू कर सकते हैं:

• चर से अंडरस्कोर हटा दिया, मुझे लगता है कि यह बेहतर पढ़ता है। मैंने उन्हें ऊपरी मामला रखा क्योंकि इसके लिए L, यही पीईपी 8 कहता है । और फिर मैंने Nस्थिरता के लिए रखा । आमतौर पर मैं इस्तेमाल करता हूँ resultया शायद merged। पता नहीं आपने क्यों चुना N। यदि आपके पास एक सार्थक शब्द है जो "एन" से शुरू होता है, तो मैं इसका उपयोग करने का सुझाव देता हूं।
• फ़ंक्शन मापदंडों के बीच का स्थान।
• टिप्पणी के बजाय उचित डॉकस्ट्रिंग प्रारूप।
• len(L_1) > 0सामान्य L1गैर-शून्यता जाँच के साथ प्रतिस्थापित ।
• N += [x]सामान्य के साथ प्रतिस्थापित N.append(x)।

बस एक और तरीका है, कि एक "लंबी" लाइन की जगह Lएक स्पष्ट लेकिन धीमी गति से निर्धारित करें:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    N = []
    def last(L):
        return L[-1]
    while L1 and L2:
        L = max(L2, L1, key=last)
        N.append(L.pop())
    N.reverse()
    N[:0] = L1 or L2
    return N

कुछ मज़ेदार के लिए, दो सूची समझ वाले हैक:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    def end(L):
        return L[-1:]
    return [max(L2, L1, key=end).pop() for _ in L1 + L2][::-1]

def merge(L, R):
    """Merges two (already sorted) lists to one sorted list."""
    return [(R, L)[L[-1:] > R[-1:]].pop() for _ in L + R][::-1]

और मैं बहुत तेज़ तरीके से नहीं जाना चाहता:

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    return sorted(L1 + L2)

Timsort के कारण वह O (n) है। और C कोड के कारण तेजी से O (n)। यदि आप सोचते हैं कि sortedकिसी मर्ज के अंदर पराक्रमी का उपयोग करना मर्ज़ॉर्ट को पहली जगह में लिखने के उद्देश्य को परास्त करता है: यहां तक ​​कि अगर आप सिर्फ मर्जसॉर्ट नहीं कर रहे हैं, तो यह सार्थक हो सकता है। कम से कम एक बार मैंने किसी चीज़ की एम्बेडेड गणना के साथ एक मर्ज को लिखा, और मैंने वास्तव में sortedसिर्फ विलय के लिए उपयोग किया । क्योंकि इसने मेरे समाधान को और तेज़ / छोटा / सरल बना दिया।

और भी अधिक कुशल (दोनों स्थान और समय):

def merge(L1, L2):
    """Merges two (already sorted) lists to one sorted list."""
    L1 += L2
    L1.sort()
    return L1

(यदि इससे L2अधिक समय L1हो सकता है , तो इसके बजाय सम्मिलित L1करना लाभप्रद हो सकता है L2।)