Mergesort en Python

Question

Mi implementación de mergesort actualmente toma mucho tiempo, para una lista con 1 millón de elementos, toma más de 130 segundos ordenar la lista.

• ¿Podría alguien echar un vistazo a mi código y sugerirme qué puedo hacer para mejorarlo?

• ¿Hay algo en particular en mi código que esté tardando mucho?

Código

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

Aquí está mi código para generar el millón de elementos:

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

Answer 1

El pop(0)toma tiempo lineal. Hazlo de manera diferente, en el tiempo O (1). La forma estándar utiliza variables de índice. Vea las respuestas de esta pregunta para conocer más formas pitónicas. O puede fusionar de derecha a izquierda, usando pop(), y luego al final reverse()el resultado.

Una forma de hacer esto último:

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

Otros cambios que hice y que también puede aplicar en las otras partes de su código:

• Se eliminaron los guiones bajos de las variables, creo que se lee mejor. Los mantuve en mayúsculas porque Leso es lo que dice PEP 8 . Y luego lo mantuve Npor coherencia. Normalmente usaría resulto tal vez merged. No sé por qué lo elegiste N. Si tiene una palabra significativa que comienza con "n", le sugiero que la use.
• Espacio entre los parámetros de la función.
• Formato de cadena de documentación adecuado en lugar de comentario.
• Reemplazado len(L_1) > 0con el L1control de no vacío normal .
• Reemplazado N += [x]con lo normal N.append(x).

Solo de otra forma, reemplazando esa línea "larga" para determinar Lcon una forma más clara pero más lenta:

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

Para divertirse, dos listas de trucos de comprensió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]

Y no quiero irme sin una forma mucho más rápida:

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

Eso es O (n) debido a Timsort. Y rápido O (n) debido al código C. Si cree que usar el poderoso sorteddentro de un mergesort anula el propósito de escribir el mergesort en primer lugar: incluso eso puede ser significativo, si no solo está haciendo mergesort. Al menos una vez escribí un mergesort con recuento incrustado de algo, y de hecho lo usé sortedsolo para la combinación. Porque eso hizo que mi solución fuera más rápida / más corta / más simple.

Aún más eficiente (tanto en espacio como en tiempo):

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

(Si L2puede ser más largo que L1, sería conveniente insertarlo L1en su L2lugar).