提高归并排序

我在练归并排序，并很好奇，如果我的第二个版本比第一次更好 - 它似乎是在内存需求方面，因为我从列表弹出刚刚动指数提高归并排序

代替版本1：

def mergesort(L): 
    if len(L)<=1: return L 
    pivot=len(L)/2 
    left=mergesort(L[:pivot]) 
    right=mergesort(L[pivot:]) 
    i=j=0 
    sortedArr=[] 
    while i<len(left) and j<len(right): 
     if left[i]<right[j]: 
      sortedArr.append(left[i]) 
      i+=1 
     else: 
      sortedArr.append(right[j]) 
      j+=1 
    return sortedArr + left[i:] + right[j:]

2版

def mergesort(L): 
    if len(L)<=1: return L 
    pivot=len(L)/2 
    left=mergesort(L[:pivot]) 
    right=mergesort(L[pivot:]) 
    sortedArr=[] 
    while left!=[] and right!=[]: 
     if left[0]<right[0]: 
      sortedArr.append(left.pop(0)) 
     else: 
      sortedArr.append(right.pop(0)) 
    return sortedArr + left + right

没有进入并行化，有没有办法在第2版，以进一步提高，假设它是优于第1版？我到目前为止如何描述这两个版本的内存需求？

来源

2013-03-22 MyNameIsKhan

从列表的前膨化将是效率极其低下。 – 2013-03-22 20:25:47

在内存方面，你可能有更好的版本2，但计算，每'pop'需要Python的元素列表中的内存1向左移动，这将是非常低效的。我想你可以扭转列表，并弹出结束，以解决这个问题... – mgilson 2013-03-22 20:26:41

@mgilson是否扭转了名单昂贵？ – MyNameIsKhan 2013-03-22 20:31:01

为什么不利用馆藏一个deque？它会降低popleft（）操作的成本？

来源

2013-03-22 23:12:34 Dvx

有关列表L，L[:n]操作O(n)时间，在Python O(n)空间（它创建与n元素的新列表）。

鉴于a，b，c名单，a + b + c是O(n)时间和空间，其中n是len(a) + len(b) + len(c)（它还创建了带有n元素的新列表）。

因此，每次致电mergesort()需要T(n) = 2T(n/2) + O(n)时间和空间，即T(n) = O(n*log(n))。

你的第二个版本有时间差的复杂性，由于left.pop(0)是O(len(left))操作。第二个版本的内存要求与第一个版本的内存要求渐近相同。

这里的O(n*log(n))时间，O(n)结构相同（使用Python 3.3+语法）的空间解决方案：

def mergesort(L): 
    return list(merge_sort_gen(L, 0, len(L))) 

def merge_sort_gen(L, start, n): # O(n*log(n)) time, O(n) space 
    if n == 1: # a list of one element is always sorted 
     yield L[start] 
    elif n > 1: # sort halves and merge them 
     half = n // 2 
     yield from merge(merge_sort_gen(L, start, half), 
         merge_sort_gen(L, start + half, n - half))

凡merge()合并两个排序的迭代器。你可以使用heapq.merge()或：

from functools import partial 

def merge(sorted_a, sorted_b, done=object()): # O(n) time, O(1) space 
    next_a, next_b = partial(next, sorted_a, done), partial(next, sorted_b, done) 

    a, b = next_a(), next_b() 
    while a is not done and b is not done: 
     if b < a: 
      yield b 
      b = next_b() 
     else: 
      yield a 
      a = next_a() 

    item, rest = (a, sorted_a) if b is done else (b, sorted_b) 
    yield item #XXX at least one of sorted_a or sorted_b must be non-empty 
    yield from rest

你可以follow the code step by step at Python Tutor。

yield from iterable产生相同的项目，如（但内部细节是不同的）：

for item in iterable: 
    yield item

The Python yield keyword explained见。

来源

2013-03-23 10:42:08 jfs

提高归并排序

回答

相关问题