0

我正在练习合并排序，我很好奇我的第二个版本是否比第一个更好——这似乎是在内存需求方面，因为我从列表中弹出而不是仅仅移动索引

版本 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？到目前为止，我将如何描述这两个版本的内存要求？

4

2 回答 2

1

为什么不使用集合中的双端队列？它会降低 popleft() 操作的成本吗？

于 2013-03-22T23:12:34.403 回答
0

对于 list L，L[:n]操作是Python 中的O(n)时间、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))

wheremerge()合并两个排序的迭代器。您可以使用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

您可以在 Python Tutor 一步一步地遵循代码。

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

for item in iterable:
    yield item

请参阅解释的 Pythonyield关键字。

于 2013-03-23T10:42:08.367 回答