Медленная реализация слияния, что не так?

Question

Я получаю неожиданные (?) Результаты от этой реализации слияния.Это очень медленно по сравнению с моей трехсторонней быстрой сортировкой (также написанной на python).

Моя быстрая сортировка завершается с 10000 элементами примерно через 0,005 с, тогда как для сортировки слиянием требуется 1,6 с!Включая исходный код для обеих реализаций.

Слияние:

#Merges two sorted lists into one sorted list. recursively
def merge(left, right):
    if len(left) == 0 and len(right) == 0:
        return []
    elif len(left) == 0:
        return right
    elif len(right) == 0:
        return left
    else:
        if left[0] <= right[0]:
            return left[:1] + merge(left[1:],right)
        else:
            return right[:1] + merge(left,right[1:])

#Splits a list in half and returns the halves
def halve(list):
    return list[:len(list)//2],list[len(list)//2:]

#Mergesort
def mergesort(list):
    if len(list) <= 1:
        return list
    left,right = halve(list)
    left,right = mergesort(left),mergesort(right)
    return merge(left,right)

Быстрая сортировка:

#Three-way QuickSort in Python
def quicksort(a):
    if len(a) == 0:
        return []
    p = a[(len(a)-1)//2]
    less = quicksort([x for x in a if x < p])
    greater = quicksort([x for x in a if x > p])
    equal = [x for x in a if x == p]
    return less + equal + greater

Может кто-нибудь придумать объяснение или, возможно, даже исправить?1011 *

Answer 1

Обычно предположения о производительности неверны, но я пойду с этим один раз, так как у меня есть некоторый опыт с этим. Профиль, если вы действительно хотите знать :

Вы добавляете списки, т.е. left[:1] + merge(left[1:],right), это одна из более медленных операций в Python. Он создает новый список из обоих списков, поэтому ваша сортировка слиянием создает как N ** 2 промежуточные списки. Quicksort с другой стороны использует вместо этого очень быстрые LC и создает меньше списков (я думаю, как 2N или около того).

Попробуйте использовать extend вместо +, возможно, это поможет.

Answer 2

Рекурсивная сортировка слиянием - не самый лучший способ сделать что-то. Вы должны получить лучшую производительность с прямым итеративным подходом. Я не очень хорошо знаком с Python, поэтому я дам вам псевдокод, похожий на C.

ileft = 0 // index into left array
iright = 0 // index into right array
iresult = 0 // index into result array
while (ileft < left.length && iright < right.length)
{
    if (left[ileft] <= right[iright])
        result[iresult++] = left[ileft++]
    else
        result[iresult++] = right[iright++]
}

// now clean up the remaining list
while (ileft < left.length)
    result[iresult++] = left[ileft++]

while (iright < right.length)
    result[iresult++] = right[iright++]

Answer 3

Объяснение:

Как правило, быстрая сортировка на практике значительно быстрее, чем другие алгоритмы n (nlogn), поскольку ее внутренний цикл может быть эффективно реализован на большинстве архитектур и в большинстве реальных данных.можно сделать выбор дизайна, который минимизирует вероятность необходимости квадратичного времени.

Answer 4

Просто из любопытства я написал быструю реализацию с использованием генераторов (может быть чище).Как это сравнить с теми, что в оригинальном методе?

def merge(listA,listB):
    iterA, iterB = iter(listA), iter(listB)
    valA, valB = iterA.next(), iterB.next()
    while True:
        if valA <= valB:
            yield valA
            try:
                valA = iterA.next()
            except StopIteration:
                yield valB
                try:
                    while True:
                        yield iterB.next()
                except StopIteration:
                    return
        else:
            yield valB
            try:
                valB = iterB.next()
            except StopIteration:
                yield valA
                try:
                    while True:
                        yield iterA.next()
                except StopIteration:
                    return