Scalanie w Pythonie

Question

Moja implementacja Mausort zajmuje obecnie bardzo dużo czasu, w przypadku listy zawierającej 1 milion elementów, posortowanie listy zajmuje ponad 130 sekund.

• Czy ktoś mógłby uprzejmie rzucić okiem na mój kod i zasugerować, co mogę zrobić, aby go ulepszyć?

• Czy jest coś szczególnego w moim kodzie, co zajmuje dużo czasu?

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

Oto mój kod do generowania milionów elementów:

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

Answer 1

Trwa pop(0)to liniowo. Zrób to inaczej, w czasie O (1). Standardowy sposób wykorzystuje zmienne indeksowe. Zobacz odpowiedzi na to pytanie , aby poznać bardziej Pythonowe sposoby. Lub możesz scalić od prawej do lewej, używając pop(), a na końcu reverse()wyniku.

Jeden ze sposobów na zrobienie tego drugiego:

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

Inne zmiany, które zrobiłem i które możesz zastosować również w innych częściach kodu:

• Usunięto podkreślenia ze zmiennych, myślę, że lepiej czyta. Zostawiłem je wielkimi literami, ponieważ Ltak mówi PEP 8 . A potem zachowałem Nspójność. Zwykle bym używał, resulta może merged. Nie wiem, dlaczego wybrałeś N. Jeśli masz jakieś znaczące słowo zaczynające się na „n”, proponuję go użyć.
• Przestrzeń między parametrami funkcji.
• Właściwy format ciągów dokumentów zamiast komentarza.
• Zastąpiony len(L_1) > 0normalnym L1sprawdzeniem braku pustki.
• Zastąpiony N += [x]normalnym N.append(x).

Po prostu inny sposób, zastępując tę ​​jedną „długą” linię w celu ustalenia Lwyraźniejszym, ale wolniejszym sposobem:

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

Dla zabawy dwa sposoby na zrozumienie listy:

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]

I nie chcę wyjeżdżać bez dużo szybszej drogi:

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

To jest O (n) z powodu Timsorta. I szybkie O (n) dzięki kodowi C. Jeśli myślisz, że użycie potęgi sortedwewnątrz scalania jest sprzeczne z celem pisania funkcji scalania: nawet to może mieć znaczenie, jeśli nie robisz po prostu scalania. Przynajmniej raz napisałem scalenie z wbudowanym liczeniem czegoś i rzeczywiście użyłem sortedtylko do scalenia. Ponieważ dzięki temu moje rozwiązanie jest szybsze / krótsze / prostsze.

Jeszcze wydajniejsze (zarówno przestrzenne, jak i czasowe):

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

(W przypadku L2może być dłuższy niż L1może to być korzystne, aby wstawić L1do L2zamiast).