Какие методы я могу использовать, чтобы моя реализация mergesort работала быстрее? - PullRequest
Новая
       13

Какие методы я могу использовать, чтобы моя реализация mergesort работала быстрее?

0 голосов
/ 30 апреля 2020

Я пытаюсь выяснить, как ускорить мою реализацию сортировки слиянием. В настоящее время я реализовал это рекурсивно, используя deques в Python, как вы можете видеть ниже.

Лог c состоит в том, чтобы разбить пополам, пока у нас не появится список размера 1, преобразовать его в deque и затем используйте двойную природу deques для popleft, а не pop (0) в списке. У нас есть запросы вплоть до тех пор, пока конечная очередь не станет той же длины, что и первоначальный список; эта дека затем превращается обратно в список. 

from collections import deque

def mergesort(iterable, final_length=False):
    '''
    Return a new list containing all items from the iterable in ascending order.

    This uses a custom implementation of mergesort that utilises a deque.
    final_length should not be input and is there to ensure the final deque 
    produced gets converted to a list.
    '''

    if not final_length:
        final_length = len(iterable)

    if len(iterable) <= 1:
        return iterable

    l1 = iterable[:len(iterable)//2]
    l2 = iterable[len(iterable)//2:]

    ml1 = mergesort(l1, final_length)
    ml2 = mergesort(l2, final_length)

    ml = merge(ml1, ml2)

    return ml if len(ml) < final_length else list(ml)

def merge(l1, l2):
    '''
    Return a sorted, merged deque of two input values or deques.
    '''
    l3 = deque()

    if len(l1) == 1:
        l1 = deque(l1)
    if len(l2) == 1:
        l2 = deque(l2)

    while l1 and l2:
        if l1[0] < l2[0]:
            l3.append(l1.popleft())
        else:
            l3.append(l2.popleft())

    while l1 and not l2:
        l3.append(l1.popleft())

    while l2 and not l1:
        l3.append(l2.popleft())

    return l3

Но, к сожалению, он работает намного медленнее, чем встроенный алгоритм timsort. 

num_items,time(s),algorithm
1000,0.00017970000000033792,builtin
1000,0.006608100000001116,mergesort
499000,0.33416399999987334,builtin
499000,4.807901299999912,mergesort

Я ценю, что timsort невероятно эффективен и использует код более низкого уровня и, как правило, будет быстрее, но есть ли что-то конкретное c Я здесь упускаю, что заставляет мой код работать так медленно?

Я не особо ищу полное рабочее решение, а скорее общее обсуждение и советы.

...