Mergesort en python

Question

La mise en œuvre de mon tri de fusion prend actuellement beaucoup de temps, pour une liste avec 1 million d'éléments, il faut plus de 130 secondes pour que la liste soit triée.

• Quelqu'un pourrait-il gentiment jeter un œil à mon code et suggérer ce que je pourrais faire pour l'améliorer?

• Y a-t-il quelque chose de particulier dans mon code qui prend beaucoup de temps?

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

Voici mon code pour générer le million d'éléments:

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

Answer 1

Le pop(0)prend un temps linéaire. Faites cela différemment, en temps O (1). La méthode standard utilise des variables d'index. Voir les réponses à cette question pour d'autres manières pythoniques. Ou vous pouvez fusionner de droite à gauche, en utilisant pop(), puis à la fin reverse()le résultat.

Une façon de faire ce dernier:

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

Autres modifications que j'ai apportées et que vous pouvez également appliquer dans les autres parties de votre code:

• Suppression des traits de soulignement des variables, je pense que cela se lit mieux. Je les ai gardés en majuscules parce que pour L, c'est ce que dit PEP 8 . Et puis j'ai gardé la Ncohérence. Habituellement, j'utiliserais resultou peut-être merged. Je ne sais pas pourquoi tu as choisi N. Si vous avez un mot significatif qui commence par "n", je vous suggère de l'utiliser.
• Espace entre les paramètres de la fonction.
• Format de docstring approprié au lieu de commentaire.
• Remplacé len(L_1) > 0par le L1contrôle normal de non-vide.
• Remplacé N += [x]par la normale N.append(x).

Juste une autre façon, en remplaçant cette "longue" ligne pour déterminer Lpar une manière plus claire mais plus lente:

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

Pour vous amuser, deux hacks de compréhension de liste:

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]

Et je ne veux pas partir sans un moyen beaucoup plus rapide:

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

C'est O (n) à cause de Timsort. Et rapide O (n) à cause du code C. Si vous pensez que l'utilisation du puissant à l' sortedintérieur d'un tri de fusion va à l'encontre de l'objectif d'écrire le tri de fusion en premier lieu: même cela peut être significatif, si vous ne faites pas que du tri de fusion. Au moins une fois, j'ai écrit un tri de fusion avec comptage intégré de quelque chose, et je l'ai en effet utilisé sortedjuste pour la fusion. Parce que cela a rendu ma solution plus rapide / plus courte / plus simple.

Encore plus efficace (à la fois dans l'espace et dans le temps):

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

(Si L2peut être plus long que L1, il peut être avantageux de l'insérer L1à la L2place.)