为什么我的MergeSort在Python中这么慢？

Question

我在理解这种行为时遇到了一些麻烦.我正在使用timeit-module测量执行时间,并获得10000个周期的以下结果:

• 合并:1.22722930395
• 泡泡: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

编辑:

我已经将列表操作更改为使用指针,我的测试现在可以使用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).

我看不到BubbleSort,但我敢打赌它可以就地运行,难怪它更快.

您需要将其重写为就地工作.而不是复制原始列表的一部分,传递开始和结束索引.

Answer 2

对于初学者:我无法在100个周期和大小为10000的列表中重现您的计时结果.timeit本答案中讨论的所有实现的详尽基准(包括bubblesort 和您的原始片段)在此处作为要点发布.我发现单次运行的平均持续时间的结果如下:

• Python的本机(Tim)排序:0.0144600081444
• Bubblesort:26.9620819092
• (您的)原始Mergesort:0.224888720512

现在,为了使您的功能更快,您可以做一些事情.

• 编辑:嗯,显然,我错了(感谢cwillu).长度计算在python中占用O(1).但删除无处不在的计算仍然有点改善(原始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
  

  这又是快:无LEN归并:0.195795390606,无LEN归并+ fastmerge:0.126505711079

• 第三 - 如果您使用的语言执行尾调用优化,这只会是有用的,没有它,这是一个坏主意 - 您对merge的调用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循环来延迟调用堆栈管理(蹦床,例如此处解释,最初由Guy Steele引起的技巧).蹦床和CPS一起工作很好.

  你编写了一个thunking函数,它"记录"并延迟应用程序:它接受一个函数及其参数,并返回一个返回的函数(原始函数应用于这些参数).

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

  然后你编写一个管理thunks调用的trampoline:它应用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))
  

可悲的是,这并不是那么快(递归mergesort:0.126505711079,这个蹦床版本:0.170638551712).好吧,我想递归合并排序算法的堆栈爆炸实际上是适度的:只要你走出数组切片递归模式中最左边的路径,算法就会开始返回(&删除帧).因此,对于10K大小的列表,您获得的函数堆栈最多为log_2(10 000)= 14 ...非常适中.

你可以在这个SO答案的基础上做更多涉及基于堆栈的TCO消除:

    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
• Bubblesort:26.9620819092
• 原始Mergesort:0.224888720512
• no-len Mergesort:0.195795390606
• no-len Mergesort + fastmerge:0.126505711079
• trampolined CPS Mergesort + fastmerge:0.170638551712
• 基于堆栈的mergesort + fastmerge:0.144994809628