提高MergeSort的效率

Question

我正在研究一个hackerrank问题：https://www.hackerrank.com/challenges/big-sorting

并用Python语言编写了MergeSort的实现。该算法运行良好，但在一些较大的输入测试中会出现超时错误。由于我不是Python专家，有人能建议我如何让我的代码更有效率吗？

unsorted = map(int, unsorted) # Unsorted is provided as an input, an array of strings


def mergeSort(list):
    s = len(list)

    if s == 1:
        return list

    if s == 2:
        if list[0] < list[1]:
            return list
        return [list[1], list[0]]

    listA = mergeSort(list[:s / 2])
    listB = mergeSort(list[s / 2:])

    r = []

    while len(listA) > 0 or len(listB) > 0:
        if len(listA) == 0:
            r = r + listB
            return r

        if len(listB) == 0:
            r = r + listA
            return r

        if listA[0] < listB[0]:
            r.append(listA.pop(0))
        else:
            r.append(listB.pop(0))


list = mergeSort(unsorted)
for n in list:
    print n

Answer 1

对一个包含100000个介于1和10000之间的随机数的列表运行您的脚本，就会得到这个分析结果：

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    3.687    3.687 <string>:1(<module>)
 131071/1    1.457    0.000    3.687    3.687 \Test\untitled4.py:8(mergeSort)
  1502009    1.903    0.000    1.903    0.000 {method 'pop' of 'list' objects}
  4833703    0.217    0.000    0.217    0.000 {len}
  1502009    0.110    0.000    0.110    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

从中可以看出，大部分时间都花在了pop()和len()以及函数调用上。例如，可以通过使用较低的指针来消除pop(0)。python中关于mergesort算法的类似优化有很多问题，所以请尝试应用类似问题下的答案中描述的优化。

Answer 2

与使用合并排序来运行"in-place".

• It相比，通过切片来复制子列表(例如list[:s / 2])使用的内存要多得多，这可能是因为合并排序太慢，有一些算法在某些限制下会运行得更快，如counting sort和

Answer 3

其他人也做过类似的挑战：

Recursive algorithm works without return statement? (Runs really fast)

在此挑战中，字符串没有前导零，将被视为整数。较长的字符串大于较短的字符串。首先需要进行长度比较，并且只有当字符串比较时长度相等时才需要进行长度比较。

这可以通过执行辅助数组的一次性分配aux = none*n来进一步改进，其中n是行数(main()需要计数行并将n作为参数传递给排序函数)。如果使用自顶向下的合并排序，可以使用一对相互递归的函数来避免复制数据(在这种情况下，我假设" data“实际上等同于一个指向字符串的指针数组，并且排序永远不会移动字符串)。一个函数在原始数组中以排序的子数组结束，另一个函数在辅助数组中以排序的子数组结束。每个函数调用另一个函数两次，一次用于左半部分，一次用于右半部分，然后合并这两个部分。在排序后的数据将结束于辅助数组且大小为1的特殊情况下，将单个元素从原始数组复制到辅助数组。

自下而上的合并排序会更快一些，因为它跳过了用于生成n-1对索引的所有递归，并且首先将n个元素的数组视为每个1个元素的n个子数组，然后使用迭代来操作索引。这并不是很快，因为大部分时间都花在合并函数上，而合并函数对于自上而下和自下而上的合并排序都是相同的。与优化的自顶向下合并排序类似，可以通过基于合并过程更改合并方向来避免复制。合并遍的数量是基于n预先确定的，如果是奇数遍，则第一遍可以在适当的位置交换元素对，从而留下偶数个合并遍来执行此操作，排序后的数据将最终保存在原始数组中。

这个挑战似乎是打算用C语言实现的，因为它提供了一个C代码片段。一个python实现将会慢得多。