Python'da birleştirme

Question

Birleştirme sıralaması uygulamam şu anda çok uzun sürüyor, 1 milyon öğeli bir liste için listenin sıralanması 130 saniyeden fazla sürüyor.

• Birisi koduma nazikçe bakıp onu geliştirmek için ne yapabileceğimi önerebilir mi?

• Kodumda önemli ölçüde uzun süren belirli bir şey var mı?

Kod

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])

Milyon elementi oluşturmak için benim kodum:

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

Answer 1

pop(0)Lineer zaman alır. Bunu O (1) zamanında farklı şekilde yapın. Standart yol, dizin değişkenlerini kullanır. Daha fazla pitonik yol için bu sorunun yanıtlarına bakın. Ya da kullanarak sağdan sola birleştirebilir pop()ve sonunda reverse()sonucu elde edebilirsiniz.

İkincisini yapmanın bir yolu:

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

Yaptığım ve kodunuzun diğer bölümlerine de uygulayabileceğiniz diğer değişiklikler:

• Altçizgileri değişkenlerden kaldırdık, daha iyi okuduğunu düşünüyorum. Onlara çünkü için büyük harf tuttu Len neyi olduğunu, PEP 8 söylüyor . Ve sonra Ntutarlılık için tuttum . Genellikle kullanırdım resultya da belki merged. Neden seçtiğini bilmiyorum N. "N" ile başlayan anlamlı bir kelimeniz varsa, onu kullanmanızı öneririm.
• İşlev parametreleri arasındaki boşluk.
• Yorum yerine uygun belge dizesi biçimi.
• Değiştirilen len(L_1) > 0Normal ile L1olmayan boşluk çek.
• N += [x]Normal ile değiştirildi N.append(x).

Başka bir yol, Ldaha net ama daha yavaş bir yolla belirlemek için bu "uzun" çizgiyi değiştirmek :

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

Biraz eğlence için, iki liste anlama hilesi:

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]

Ve çok daha hızlı bir yol olmadan ayrılmak istemiyorum:

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

Bu, Timsort yüzünden O (n). Ve C kodu nedeniyle hızlı O (n). Bir birleştirme sıralaması sortediçinde güçlü olanı kullanmanın ilk etapta birleştirme sıralaması yazma amacını bozduğunu düşünüyorsanız : Bu bile, eğer sadece birleştirme sıralaması yapmıyorsanız, anlamlı olabilir. En azından bir kez, bir şeyin gömülü sayımıyla bir birleştirme sıralaması yazdım ve aslında sortedsadece birleştirme için kullandım . Çünkü bu, çözümümü daha hızlı / daha kısa / daha basit hale getirdi.

Daha da verimli (hem uzay hem de zaman):

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

(Eğer L2daha uzun olabilir L1, eklemek avantajlı olabilir L1içine L2yerine).