Почему мой MergeSort такой медленный в Python? - PullRequest
Новая
       9

Почему мой MergeSort такой медленный в Python?

3 голосов
/ 15 августа 2011

У меня проблемы с пониманием этого поведения.Я измеряю время выполнения с помощью модуля timeit и получаю следующие результаты для циклов 10000 :

  • Слияние: 1.22722930395
  • Bubble: 0,810706578175
  • Выберите: 0,469924766812

Это мой код для MergeSort: 

def mergeSort(array):
    if len(array) <= 1:
        return array
    else:
        left = array[:len(array)/2]
        right = array[len(array)/2:]
        return merge(mergeSort(left),mergeSort(right))

def merge(array1,array2):
    merged_array=[]
    while len(array1) > 0 or len(array2) > 0:

        if array2 and not array1:
            merged_array.append(array2.pop(0))

        elif (array1 and not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))

        else:
            merged_array.append(array2.pop(0))
    return merged_array

Редактировать:

Я изменил операции со списком, чтобы использовать указатели, и мои тесты теперь работают со списком из 1000 случайных чисел от 0 до 1000.(кстати: я изменил только на 10 циклов)

результат:

  • Слияние: 0.0574434420723
  • Пузырь: 1.74780097558
  • Выберите: 0.362952293025

Это мое переписанное определение слияния: 

def merge(array1, array2):
    merged_array = []
    pointer1, pointer2 = 0, 0
    while pointer1 < len(array1) and pointer2 < len(array2):
        if array1[pointer1] < array2[pointer2]:
            merged_array.append(array1[pointer1])
            pointer1 += 1
        else:
            merged_array.append(array2[pointer2])
            pointer2 += 1
    while pointer1 < len(array1):
        merged_array.append(array1[pointer1])
        pointer1 += 1

    while pointer2 < len(array2):
        merged_array.append(array2[pointer2])
        pointer2 += 1

    return merged_array

, похоже, работает довольно хорошо :)

Ответы [ 4 ]

10 голосов
/ 15 августа 2011

list.pop(0) выскакивает первый элемент и должен сдвинуть все остальные, это дополнительная операция O (n), которая не должна выполняться.

Кроме того, при разрезании объекта list создается копия: 

left = array[:len(array)/2]
right = array[len(array)/2:]

Это означает, что вы также используете O (n * log (n)) памяти вместо O (n).

Я не вижу BubbleSort, но держу пари, он работает на месте, неудивительно, что он быстрее.

Вам нужно переписать его, чтобы он работал на месте. Вместо копирования части исходного списка передайте начальный и конечный индексы.

6 голосов
/ 15 августа 2011

Для начала: Я не могу воспроизвести ваши результаты хронирования на 100 циклах и списках размером 10000. Исчерпывающий тест с timeit всех реализаций, обсуждаемых в этом ответе (включая пузырьковую сортировку и Ваш оригинальный фрагмент) выложен в виде здесь .Я нахожу следующие результаты для средней продолжительности одного сеанса:

  • Родная (Тим) сортировка Python: 0,0144600081444
  • Bubblesort: 26,9620819092
  • (Ваш) ОригиналMergesort: 0.224888720512

Теперь, чтобы ускорить работу, вы можете сделать несколько вещей.

  • Редактировать : Ну, по-видимомуЯ был неправ в этом (спасибо cwillu ). Длина вычислений занимает O (1) в Python .Но удаление бесполезных вычислений повсюду все еще немного улучшает ситуацию (Original Mergesort: 0.224888720512, без длины Mergesort: 0.195795390606): 

    def nolenmerge(array1,array2):
    merged_array=[]
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop(0))
        elif (not array2) or array1[0] < array2[0]:
            merged_array.append(array1.pop(0))
        else:
            merged_array.append(array2.pop(0))
    return merged_array

def nolenmergeSort(array):
    n  = len(array)
    if n <= 1:
        return array
    left = array[:n/2]
    right = array[n/2:]
    return nolenmerge(nolenmergeSort(left),nolenmergeSort(right))

  • Второе, как предложено в этот ответ , pop(0) является линейным.Перепишите ваше слияние на pop() в конце : 

    def fastmerge(array1,array2):
    merged_array=[]
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array

    Это снова быстрее: no-len Mergesort: 0.195795390606, no-len Mergesort + fastmerge: 0.126505711079

  • Третье - , и это было бы полезно только как есть, если бы вы использовали язык, который выполняет оптимизацию хвостовых вызовов , без него это плохая идея - ваш вызовслияние с merge не является хвост-рекурсивным ;он вызывает как (mergeSort left), так и (mergeSort right) рекурсивно, пока в вызове остается работа (merge).

    Но вы можете сделать хвостовое слияние рекурсивным с помощью CPS (это будетисчерпать размер стека даже для скромных списков, если вы не выполняете tco): 

    def cps_merge_sort(array):
    return cpsmergeSort(array,lambda x:x)

def cpsmergeSort(array,continuation):
    n  = len(array)
    if n <= 1:
        return continuation(array)
    left = array[:n/2]
    right = array[n/2:]
    return cpsmergeSort (left, lambda leftR:
                         cpsmergeSort(right, lambda rightR:
                                      continuation(fastmerge(leftR,rightR))))

    Как только это будет сделано, вы можете выполнить TCO вручную , чтобы отложить управление стеком вызововсделано рекурсией к циклу while нормальной функции ( прыжок на батуте , объяснено, например, здесь , трюк, первоначально из-за Гая Стила). Trampolining и CPS отлично работают вместе .

    Вы пишете функцию thunking, которая «записывает» и задерживает приложение: она принимает функцию и ее аргументы и возвращает функцию, которая возвращает (этот оригиналфункция применяется к этим аргументам). 

    thunk = lambda name, *args: lambda: name(*args)

    Затем вы пишете батут, который управляет вызовами thunks: он применяет thunk, пока thunk не возвращает результат (в отличие от другого thunk) 

    def trampoline(bouncer):
    while callable(bouncer):
        bouncer = bouncer()
    return bouncer

    Тогда остается только «заморозить» (отбросить) все ваши рекурсивные вызовы из исходной функции CPS, чтобы батут развернул их в правильной последовательности.Ваша функция теперь возвращает thunk, без рекурсии (и отбрасывая свой собственный кадр), при каждом вызове: 

    def tco_cpsmergeSort(array,continuation):
    n  = len(array)
    if n <= 1:
        return continuation(array)
    left = array[:n/2]
    right = array[n/2:]
    return thunk (tco_cpsmergeSort, left, lambda leftR:
                  thunk (tco_cpsmergeSort, right, lambda rightR:
                         (continuation(fastmerge(leftR,rightR)))))

mycpomergesort = lambda l: trampoline(tco_cpsmergeSort(l,lambda x:x))

К сожалению, это не так быстро (рекурсивное слияние: 0.126505711079, версия с батутом: 0.170638551712).Ладно, я думаю, разрушение стека алгоритма рекурсивной сортировки слиянием на самом деле скромно : как только вы выходите из крайнего левого пути в шаблоне рекурсии среза массива, алгоритм начинает возвращаться (и удаляет кадры).Таким образом, для списков размером 10K вы получаете стек функций не более log_2 (10 000) = 14 ... довольно скромный.

Вы можете сделать чуть более сложное устранение TCO на основе стека под видом этого SO ответа дает: 

    def leftcomb(l):
        maxn,leftcomb = len(l),[]
        n = maxn/2
        while maxn > 1:
            leftcomb.append((l[n:maxn],False))
            maxn,n = n,n/2
        return l[:maxn],leftcomb

    def tcomergesort(l):
        l,stack = leftcomb(l)
        while stack: # l sorted, stack contains tagged slices
            i,ordered = stack.pop()
            if ordered:
                l = fastmerge(l,i)
            else:
                stack.append((l,True)) # store return call
                rsub,ssub = leftcomb(i)
                stack.extend(ssub) #recurse
                l = rsub
        return l

Но это идет только чуть-чутьбыстрее (trampolined mergesort: 0.170638551712, эта версия на основе стека: 0.144994809628).По-видимому, Python для построения стека делает при рекурсивных вызовах нашего исходного вида слияния довольно недорогой.

Окончательные результаты?на моей машине (Ubuntu natty's Python 2.7.1+) среднее время выполнения (из 100 запусков-исключая Bubblesort-, список размером 10000, содержащий случайные целые числа размера 0-10000000):

  • Родной Python (Tim): 0,0144600081444
  • Bubblesort: 26,9620819092
  • Original Mergesort: 0,224888720512
  • no-len Mergesort: 0,195795390606
  • no-len Mergesort + fastmerge: 0.126505711079
  • батутный CPS Mergesort + fastmerge: 0.170638551712
  • объединение на основе стека + fastmerge: 0,144994809628
1 голос
/ 15 августа 2011

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

0 голосов
/ 15 августа 2011

Умм .. 1000 записей ??Вы все еще в пределах доминирующего полиномиального коэффициента. Если у меня есть выборка-сортировка: 15 * n ^ 2 (читает) + 5 * n ^ 2 (перестановки) вставка-сортировка: 5 * n ^ 2 (читает) + 15* n ^ 2 (swaps) сортировка слиянием: 200 * n * log (n) (чтение) 1000 * n * log (n) (слияние)

Вы будете в гонкеА пока ... Кстати, в 2 раза быстрее в сортировке НИЧЕГО.Попробуйте в 100 раз медленнее.Вот где чувствуются реальные различия.Попробуйте "не закончить в моей жизни" алгоритмы (есть известные регулярные выражения, которые требуют столько времени, чтобы соответствовать простым строкам).

Так что попробуйте записи 1M или 1G и дайте нам знать, если вы все-таки слились-сортировка идет не очень хорошо.

При этом ..

Есть много вещей, которые делают сортировку слиянием дорогой.Прежде всего, никто никогда не запускает быструю сортировку или сортировку слиянием на мелкомасштабных структурах данных. Где у вас есть if (len <= 1), люди обычно ставят: if (len <= 16): (используйте встроенную вставку-сортировку) else: сортировка слиянием На КАЖДОМ уровне распространения. </p>

Поскольку сортировка с вставкой имеет меньшую стоимость коэффициента при меньших размерах n.Обратите внимание, что 50% вашей работы выполняется на этой последней миле.

Далее вы без необходимости запускаете array1.pop (0) вместо поддержки счетчиков индекса.Если вам повезет, python эффективно управляет смещениями начала массива, но при прочих равных условиях вы изменяете входные параметры

Кроме того, вы знаете размер целевого массива во время слияния, зачем копировать- и дважды удваивать merged_array. Предварительно назначать размер целевого массива в начале функции. Это сэкономит как минимум дюжину «клонов» на уровень объединения.

В общем, сортировка слиянием использует 2-кратный размер оперативной памяти. Ваш алгоритм, вероятно, использует 20-кратный размер из-за всех временных буферов слияния (возможно, python может освободить структуры перед рекурсией).Это нарушает элегантность, но, как правило, лучшие алгоритмы сортировки слиянием делают немедленное выделение буфера слияния равным размеру исходного массива, и вы выполняете сложную адресную арифметику (или индекс-массива + span-length), чтобы просто продолжать слияние данных-структуры туда и обратно.Это не будет так просто, как простая рекурсивная проблема, подобная этой, но она несколько близка.

В C-сортировке когерентность кэша - ваш главный враг.Вам нужны горячие структуры данных, чтобы максимизировать кэш.Распределяя временные временные буферы (даже если диспетчер памяти возвращает указатели на горячую память), вы рискуете сделать медленные вызовы DRAM (предварительно заполнив строки кэша для данных, которые вы собираетесь перезаписать).Это одно из преимуществ вставки-сортировки, выбора-сортировки и быстрой сортировки по сравнению с сортировкой слиянием (при реализации, как указано выше)

Кстати, что-то вроде быстрой сортировки - это и естественно элегантный код, и естественно эффективный-код, и не тратит впустую память (Google это в Википедии - у них есть реализация javascript, из которой можно основать свой код).Трудно выжать последнюю унцию производительности из быстрой сортировки (особенно в языках сценариев, поэтому они обычно используют C-api для выполнения этой части), и у вас наихудший случай O (n ^ 2),Вы можете попытаться проявить смекалку, выполнив комбинацию «пузырьковая сортировка / быстрая сортировка», чтобы уменьшить наихудший случай.

Счастливое кодирование.

...