运行 TImes 的两种 MergeSort 实现

Question

我是初学者，为了好玩而学习算法，我正在尝试在 Python 中实现归并排序。

下面是我的实现。当我向它提供 100000 列表时，它非常慢。

def mergesortedlist(L, R):
    LR = [0]*(len(L)+len(R))  ##merged output (LR combined)
    i= 0     ##counter for left side
    j= 0      ##counter for ride side
    k = 0
    while i <= len(L) and j <= len(R):

        if i == len(L): 
            LR[k:]= R[j:]
            return LR

        elif j == len(R): 
            LR[k:] = L[i:]
            return LR
        elif L[i] < R[j]: 
            LR[k]= L[i]
            i+=1
            k+=1
        else: ##left side is bigger than right side
            LR[k]=R[j]
            j+=1
            k+=1   

def mergesort(N):  

    if len(N) <= 1: 
        return N
    else:
        sub1 = N[0:round(len(N)/2)]  
        sub2 = N[round(len(N)/2):]
        return mergesortedlist(mergesort(sub1), mergesort(sub2))

这是我从该网站 (http://interactivepython.org/courselib/static/pythonds/SortSearch/TheMergeSort.html) 在线某处找到的实现

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

速度非常快。

据我所知，我的实现也是 O(Nlog(N))，那么为什么我的要慢得多？

感谢您的帮助。

干杯！

Answer 1

我没有看到巨大的性能差异：1,000,000 个随机浮点数分别为 7.3 秒和 5.4 秒。但是你是对的，第二个更快。

以下是如何对他们进行概要分析以了解占用时间的方法。

python -m cProfile -s time mergesort.py

你的输出：

999999    8.517    0.000   11.088    0.000 mergesort.py:2(mergesortedlist)
1999999/1    2.735    0.000   14.151   14.151 mergesort.py:25(mergesort)
84184856/84184834    2.725    0.000    2.725    0.000 {len}
1999998    0.174    0.000    0.174    0.000 {round}

第二个：

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
1999999/1    7.377    0.000    8.721    8.721 mergesort2.py:1(mergeSort)
40499148/40499126    1.344    0.000    1.344    0.000 {len}

您会发现您的调用 len() 和 round() 花费了更多时间。

第二个也对通过引用传递的数组进行操作，而你的 returns 对数组进行操作。复制也可能需要一些时间。由于您是初学者，因此有必要复习一下 difference

Answer 2

我的 2 美分。在我的测试中，round() 或 len() 函数都不会显着影响运行时间。我认为问题如下：在每个 mergesortedlist() 调用中，您都会创建一个新列表。我用 IPython 的 %%timeit

测试了这段代码

L = N[0:round(len(N)/2)]  
R = N[round(len(N)/2):]
LR = [0]*(len(L)+len(R))

2,000,000 个元素 -> 10 个循环，最好的 3 个：每个循环 34.4 毫秒
1,000,000 个元素 -> 100 个循环，最好的 3 个：每个循环 17.2 毫秒
500,000 个元素 -> 100 个循环，最好的 3 个：每个循环 8.3 毫秒
250,000 个元素 -> 100 个循环，最好的 3 个：每个循环 3.49 毫秒
125,000 个元素 -> 1000 个循环，最好的 3 个：每个循环 1.25 毫秒
62,500 个元素 -> 1000 个循环，最好的 3 个：每个循环 526 微秒
所以...

请记住，合并排序的最坏情况是 O(N*logN)。（这个事实拒绝了我们将第一个排序函数应用于随机数而第二个排序函数应用于排序数字的情况。）

运行 TImes 的两种 MergeSort 实现

Two Implementations of MergeSort with Vastly Different Running TImes

python

sorting

performance

mergesort