Mergesort in pitone

Question

La mia implementazione di Mergesort richiede attualmente molto tempo, per un elenco con 1 milione di elementi ci vogliono più di 130 secondi per ottenere l'elenco ordinato.

• Qualcuno potrebbe gentilmente dare un'occhiata al mio codice e suggerire cosa posso fare per migliorarlo?

• C'è qualcosa di particolare nel mio codice che sta impiegando molto tempo?

Codice

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

Ecco il mio codice per generare il milione di elementi:

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

Answer 1

Il pop(0)tempo è lineare. Fallo in modo diverso, in O (1) tempo. Il modo standard utilizza le variabili indice. Vedi le risposte a questa domanda per alcuni modi più pitonici. Oppure potresti unire da destra a sinistra, usando pop(), e poi alla fine reverse()il risultato.

Un modo per fare quest'ultimo:

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

Altre modifiche che ho fatto e che puoi applicare anche nelle altre parti del tuo codice:

• Rimossi i trattini bassi dalle variabili, penso che si legga meglio. Li ho tenuti in lettere maiuscole perché Lquesto è ciò che dice PEP 8 . E poi ho mantenuto Nper coerenza. Di solito lo userei resulto forse merged. Non so perché hai scelto N. Se hai una parola significativa che inizia con "n", ti suggerisco di usarla.
• Spazio tra i parametri della funzione.
• Formato corretto della docstring invece del commento.
• Sostituito len(L_1) > 0con il normale controllo di L1non vuoto.
• Sostituito N += [x]con il normale N.append(x).

Solo un altro modo, sostituendo quella linea "lunga" per determinare Lcon un modo più chiaro ma più lento:

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

Per un po 'di divertimento, due hack per la comprensione dell'elenco:

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]

E non voglio andarmene senza un modo molto più veloce:

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

Questo è O (n) a causa di Timsort. E veloce O (n) a causa del codice C. Se pensi che usare il potente sortedall'interno di un Mergesort sconfigga lo scopo di scrivere il Mergesort in primo luogo: anche questo può essere significativo, se non stai solo facendo Mergesort. Almeno una volta ho scritto un mergesort con il conteggio incorporato di qualcosa, e in effetti l'ho usato sortedsolo per la fusione. Perché questo ha reso la mia soluzione più veloce / più breve / più semplice.

Ancora più efficiente (sia spazio che tempo):

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

(Se L2può essere più lungo di L1, potrebbe essere vantaggioso inserirli L1al suo L2posto.)