Mergesort in Python

Question

Meine Mergesort-Implementierung dauert derzeit sehr lange. Bei einer Liste mit 1 Million Elementen dauert es über 130 Sekunden, bis die Liste sortiert ist.

• Könnte jemand freundlicherweise einen Blick auf meinen Code werfen und vorschlagen, was ich tun könnte, um ihn zu verbessern?

• Gibt es etwas Besonderes in meinem Code, das sehr lange dauert?

Code

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

Hier ist mein Code zum Generieren der Millionen Elemente:

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

Answer 1

Das pop(0)dauert lineare Zeit. Mach das anders, in O (1) Zeit. Die Standardmethode verwendet Indexvariablen. In den Antworten dieser Frage finden Sie weitere pythonische Möglichkeiten. Oder Sie können von rechts nach links zusammenführen pop()und dann reverse()das Ergebnis verwenden.

Ein Weg, um Letzteres zu tun:

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

Andere Änderungen, die ich vorgenommen habe und die Sie auch in den anderen Teilen Ihres Codes anwenden können:

• Die Unterstriche aus den Variablen entfernt, ich denke, es liest sich besser. Ich habe sie in Großbuchstaben gehalten, denn Ldas sagt PEP 8 . Und dann habe ich Nfür Konsistenz gehalten. Normalerweise würde ich verwenden resultoder vielleicht merged. Ich weiß nicht, warum du gewählt hast N. Wenn Sie ein aussagekräftiges Wort haben, das mit "n" beginnt, dann schlage ich vor, dieses zu verwenden.
• Abstand zwischen den Funktionsparametern.
• Richtiges Dokumentzeichenfolgenformat anstelle eines Kommentars.
• Ersetzt len(L_1) > 0durch die normale L1Nicht-Leereprüfung.
• Ersetzt N += [x]durch das normale N.append(x).

Nur eine andere Möglichkeit, diese eine "lange" Zeile Ldurch eine klarere, aber langsamere zu ersetzen :

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

Zum Spaß zwei Listenverständnis-Hacks:

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]

Und ich möchte nicht ohne einen viel schnelleren Weg gehen:

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

Das ist O (n) wegen Timsort. Und schnelles O (n) wegen C-Code. Wenn Sie der Meinung sind, dass die Verwendung des Mächtigen sortedin einem Mergesort den Zweck des Schreibens des Mergesorts in erster Linie zunichte macht: Auch das kann sinnvoll sein, wenn Sie nicht nur Mergesort durchführen. Mindestens einmal habe ich einen Mergesort mit eingebetteter Zählung von etwas geschrieben, und ich habe ihn tatsächlich sortednur für die Zusammenführung verwendet. Weil das meine Lösung schneller / kürzer / einfacher machte.

Noch effizienter (sowohl räumlich als auch zeitlich):

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

(Falls L2kann als länger sein L1, könnte es von Vorteil sein , einfügen L1in L2statt.)