为什么我的 Python 合并排序这么慢？

Question

我在理解这种行为时遇到了一些困难。 我正在使用 timeit-module 测量执行时间，并获得 10000 周期的以下结果：

• Merge : 1.22722930395
• Bubble: 0.810706578175
• Select: 0.469924766812

This is my合并排序代码：

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

编辑：

我已将列表操作更改为使用指针，并且我的测试现在使用包含 0-1000 之间的 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

现在看起来效果很好:)

Answer 1

list.pop(0) 弹出第一个元素，并且必须移动所有剩余的元素，这是一个额外的 O(n) 操作，不能发生。

此外，对 list 对象进行切片会创建一个副本：

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

这意味着您还使用 O(n * log(n)) 内存而不是 O(n)。

我看不到冒泡排序，但我敢打赌它就地工作，难怪它更快。

您需要重写它才能就地工作。不要复制原始列表的一部分，而是传递开始和结束索引。

Answer 2

对于初学者：我无法在 100 个周期和大小为 10000 的列表上重现您的计时结果。本答案中讨论的所有实现的 timeit 的详尽基准（包括气泡排序 >并且您的原始片段）作为要点发布在此处。我发现单次运行的平均持续时间如下：

• Python 的本机 (Tim)sort : 0.0144600081444
• Bubblesort : 26.9620819092
• (Your) Original Mergesort : 0.224888720512

现在，为了使您的函数更快，您可以做一些事情。

• 编辑：嗯，显然，我错了（感谢cwillu）。 Python 中的长度计算需要 O(1)。但是在各处删除无用的计算仍然会改善一些情况（原始合并排序：0.224888720512，无长度合并排序：0.195795390606）：

  def nolenmerge(array1,array2):
      合并数组=[]
      而数组1或数组2：
          如果不是数组1：
              merged_array.append(array2.pop(0))
          elif（不是 array2）或 array1[0] <数组2[0]：
              merged_array.append(array1.pop(0))
          别的：
              merged_array.append(array2.pop(0))
      返回合并数组
  
  def nolenmergeSort(数组):
      n = 长度（数组）
      如果 n <= 1：
          返回数组
      左 = 数组[:n/2]
      右 = 数组[n/2:]
      返回 nolenmerge(nolenmergeSort(左),nolenmergeSort(右))
  

• 第二，如这个答案，流行(0) 是线性的。将合并重写为最后的 pop()：

  def fastmerge(array1,array2):
      合并数组=[]
      而数组1或数组2：
          如果不是数组1：
              merged_array.append(array2.pop())
          elif (不是 array2) 或 array1[-1] >数组2[-1]：
              merged_array.append(array1.pop())
          别的：
              merged_array.append(array2.pop())
      merged_array.reverse()
      返回合并数组
  

  这又更快了：no-len Mergesort: 0.195795390606, no-len Mergesort+fastmerge: 0.126505711079

• 第三 - 如果您使用的是尾部调用优化的语言，那么这只会很有用，没有它，它就是一个坏主意 - 您对 merge 的调用 merge 不是 尾递归；当调用 (merge) 中还有剩余工作时，它会递归调用 (mergeSort left) 和 (mergeSort right)。

  但是您可以使用 CPS 进行尾递归合并（这将如果您不执行 tco，即使是适度的列表也会耗尽堆栈大小）：

  def cps_merge_sort(数组):
      返回 cpsmergeSort(数组,lambda x:x)
  
  def cpsmergeSort（数组，延续）：
      n = 长度（数组）
      如果 n <= 1：
          返回延续（数组）
      左 = 数组[:n/2]
      右 = 数组[n/2:]
      返回 cpsmergeSort (左, lambda leftR:
                           cpsmergeSort(右, lambda rightR:
                                        延续（快速合并（左R，右R））））
  

  完成此操作后，您可以手动执行 TCO，以将通过递归完成的调用堆栈管理推迟到普通函数的 while 循环（蹦床，解释例如此处，最初由 Guy Steele 发明的技巧）。 蹦床和 CPS 协同工作。

  您编写一个 thunking 函数，它“记录”并延迟应用程序：它接受一个函数及其参数，并返回一个返回的函数（应用于这些参数的原始函数）。

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

  然后，您编写一个蹦床来管理对 thunk 的调用：它应用 thunk 直到 thunk 返回结果（而不是另一个 thunk）

  def 蹦床（弹跳器）：
      当可调用时（保镖）：
          保镖=保镖()
      返回保镖
  

  然后剩下的就是“冻结”（thunk）来自原始 CPS 函数的所有递归调用，让蹦床以正确的顺序解开它们。现在，您的函数在每次调用时都会返回一个 thunk，而无需递归（并丢弃其自己的帧）：

  def tco_cpsmergeSort（数组，延续）：
      n = 长度（数组）
      如果 n <= 1：
          返回延续（数组）
      左 = 数组[:n/2]
      右 = 数组[n/2:]
      返回 thunk (tco_cpsmergeSort, left, lambda leftR:
                    thunk (tco_cpsmergeSort, 右, lambda rightR:
                           （继续（快速合并（左R，右R）））））
  
  mycpomergesort = lambda l：蹦床（tco_cpsmergeSort（l，lambda x：x））
  

遗憾的是，这并没有那么快（递归合并排序：0.126505711079，这个蹦床版本：0.170638551712）。好吧，我猜递归合并排序算法的堆栈爆炸实际上是适度的：一旦你走出数组切片递归模式中最左边的路径，算法就开始返回 (&删除框架）。因此，对于 10K 大小的列表，您最多会得到一个函数堆栈 log_2(10 000) = 14 ...相当适中。

您可以以此 所以答案给出：

    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

但是这只是快一点（蹦床合并排序： 0.170638551712，这个基于堆栈的版本：0.144994809628）。显然，堆栈构建 python 在我们原始合并排序的递归调用中所做的工作非常便宜。

最终结果如何？在我的机器上（Ubuntu natty 的 Python 2.7.1+），平均运行时间（100 次运行中 - 除了 Bubblesort -，大小为 10000 的列表，包含大小为 0-10000000 的随机整数）是：

• Python 的本机（Tim） ）排序：0.0144600081444
• 冒泡排序： 26.9620819092
• 原始合并排序：0.224888720512
• 无长度合并排序：0.195795390606
• 无长度合并排序 + 快速合并：0.126505711079
• 蹦床 CPS 合并排序 + 快速合并：0.170638551712
• 基于堆栈合并排序+快速合并：0.144994809628

Answer 3

您的合并排序有一个很大的常数因子，您必须在大列表上运行它才能看到渐近复杂度的好处。

Answer 4

嗯.. 1,000 条记录？你仍然处于多项式系数的主导地位..如果我有
选择排序：15 * n ^ 2（读取）+ 5 * n^2（交换）
插入排序：5 * n ^2（读取）+ 15 * n^2（交换）
合并排序： 200 * n * log(n) （读取） 1000 * n * log(n) （合并）

你将在很长一段时间内处于一场势均力敌的竞争中..顺便说一下，排序速度快了 2 倍没什么。尝试慢 100 倍。这就是感受到真正差异的地方。尝试“在我的一生中都完成不了”的算法（已知的正则表达式需要这么长时间才能匹配简单的字符串）。

因此，请尝试 1M 或 1G 记录，如果您仍然认为合并排序效果不佳，请告诉我们。

话虽这么说……

有很多因素导致这种合并排序的成本高昂。首先，没有人在小型数据结构上运行快速排序或合并排序。在 if (len <= 1) 处，人们通常会这样写：
if (len <= 16) : (使用内联插入排序)
else: 合并排序
在每个传播级别。

由于插入排序在 n 较小时具有较小的系数成本。请注意，您 50% 的工作是在最后一英里完成的。

接下来，您不必要地运行 array1.pop(0) 而不是维护索引计数器。如果你幸运的话，python 可以有效地管理数组开始偏移量，但在其他条件相同的情况下，你正在改变输入参数

此外，你知道合并期间目标数组的大小，为什么要复制并加倍 merged_array重复.. 在函数开始时预先分配目标数组的大小.. 这将为每个合并级别至少节省十几个“克隆”。

一般来说，合并排序使用 RAM 大小的 2 倍。由于所有临时合并缓冲区，您的算法可能使用 20 倍（希望 python 可以在递归之前释放结构）。它破坏了优雅，但通常最好的合并排序算法会立即分配等于源数组大小的合并缓冲区，并且您执行复杂的地址算术（或数组索引+跨度长度）以保持合并数据-来回结构。它不会像这样的简单递归问题那么优雅，但它有点接近。

在 C 排序中，缓存一致性是最大的敌人。您需要热数据结构，以便最大化缓存。通过分配瞬态临时缓冲区（即使内存管理器返回指向热内存的指针），您将面临进行缓慢 DRAM 调用的风险（为要覆盖的数据预填充缓存行）。这是插入排序、选择排序和快速排序相对于合并排序的优势之一（当按上述方式实现时）

说到这里，像快速排序这样的代码既是自然优雅的代码，也是自然高效的代码，而且不不要浪费任何内存（在维基百科上谷歌它 - 他们有一个 javascript 实现，可以作为您的代码的基础）。从快速排序中榨取最后一盎司的性能是很困难的（特别是在脚本语言中，这就是为什么他们通常只使用 C-api 来完成这部分），并且最坏的情况是 O(n^2) 。您可以通过组合冒泡排序/快速排序来尝试并聪明地减轻最坏的情况。

快乐编码。