Сортировка слияний в Python

Question

Моя реализация сортировки слиянием в настоящее время занимает очень много времени: для списка с 1 миллионом элементов для сортировки списка требуется более 130 секунд.

• Может ли кто-нибудь взглянуть на мой код и предложить, что я могу сделать, чтобы его улучшить?

• Есть ли в моем коде что-то особенное, что занимает много времени?

Код

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

Вот мой код для создания миллиона элементов:

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

Answer 1

Это pop(0)занимает линейное время. Сделайте это по-другому, за O (1) раз. Стандартный способ использует индексные переменные. См. Ответы на этот вопрос, чтобы узнать о некоторых других питонических способах. Или вы можете объединить справа налево, используя pop(), а затем, в конце концов, reverse()результат.

Один из способов сделать последнее:

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

Другие изменения, которые я сделал, и которые вы также можете применить в других частях вашего кода:

• Удалил подчеркивание из переменных, думаю, лучше читается. Я оставил их в верхнем регистре, потому Lчто это то, что говорит PEP 8 . А потом оставил Nдля единообразия. Обычно я использую resultили, может быть merged. Не знаю, почему ты выбрал N. Если у вас есть многозначительное слово, которое начинается с «н», я предлагаю использовать его.
• Пробел между параметрами функции.
• Правильный формат строки документации вместо комментария.
• Заменил len(L_1) > 0на нормальную L1проверку непустоты.
• Заменил N += [x]на нормальный N.append(x).

Еще один способ, заменив эту одну "длинную" строку для определения Lболее четким, но более медленным способом:

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

Для некоторого удовольствия, два совета по пониманию списка:

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]

И я не хочу уезжать без более быстрого пути:

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

Это O (n) из-за Timsort. И быстро O (n) из-за кода C. Если вы думаете, что использование могущества sortedвнутри сортировки слиянием в первую очередь побеждает цель написания сортировки слиянием: даже это может иметь смысл, если вы не просто выполняете сортировку слиянием. По крайней мере однажды я написал сортировку слиянием со встроенным подсчетом чего-либо, и действительно использовал sortedтолько для слияния. Потому что это сделало мое решение быстрее / короче / проще.

Еще эффективнее (как по пространству, так и по времени):

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

(Если L2может быть больше , чем L1, может быть предпочтительным , чтобы вставить L1в L2вместо этого.)