我合并两个排序列表的线性时间实现 - 有什么可以改进的？

Question

来自谷歌的Python课程：

E. Given two lists sorted in increasing order, create and return a merged
list of all the elements in sorted order. You may modify the passed in lists.
Ideally, the solution should work in "linear" time, making a single
pass of both lists.

这是我的解决方案：

def linear_merge(list1, list2):
  merged_list = []
  i = 0
  j = 0

  while True:
    if i == len(list1):
        return merged_list + list2[j:]
    if j == len(list2):
        return merged_list + list1[i:]

    if list1[i] <= list2[j]:
        merged_list.append(list1[i])
        i += 1
    else:
        merged_list.append(list2[j])
        j += 1

首先，这里使用无限循环可以吗？当我完成合并列表时，是不是应该用break关键字跳出循环，还是可以直接用return呢？

我看到这里有类似的问题被问过，所有的解决方案看起来都和我的很像，也就是非常像C语言的写法。难道没有更像Python的解决方案吗？还是说这是算法本身的特点？

Answer 1

为什么只合并两个列表呢？

这里我提供了一种基于生成器的方法，可以在线性时间内合并任意数量的已排序迭代器。

我不明白为什么像这样的功能没有在itertools库里...

def merge(*sortedlists):

    # Create a list of tuples containing each iterator and its first value
    iterlist = [[i,i.next()] for i in [iter(j) for j in sortedlists]]

    # Perform an initial sort of each iterator's first value
    iterlist.sort(key=lambda x: x[1])

    # Helper function to move the larger first item to its proper position
    def reorder(iterlist, i): 
        if i == len(iterlist) or iterlist[0][1] < iterlist[i][1]:
            iterlist.insert(i-1,iterlist.pop(0))
        else:
            reorder(iterlist,i+1)

    while True:
        if len(iterlist):
            # Reorder the list if the 1st element has grown larger than the 2nd
            if len(iterlist) > 1 and iterlist[0][1] > iterlist[1][1]:
                reorder(iterlist, 1)

            yield iterlist[0][1]

            # try to pull the next value from the current iterator
            try:
                iterlist[0][1] = iterlist[0][0].next()
            except StopIteration:
                del iterlist[0]
        else:
            break

下面是一个例子：

x = [1,10,20,33,99]
y = [3,11,20,99,1001]
z = [3,5,7,70,1002]

[i for i in merge(x,y,z)]

Answer 2

这里介绍一种生成器的方法。你可能注意到，很多“生成列表”的操作其实可以用生成器函数来很好地实现。生成器非常有用，因为它们不需要在使用数据之前就把整个列表都生成出来，也不需要把整个列表都放在内存里。而且，你可以用它们直接生成多种数据类型，不仅仅是列表。

这种方法适用于任何迭代器，不仅限于列表。

这个方法还有一个很实用的特点：当你传入一个无限或者接近无限的迭代器时，它也能正常工作，比如 linear_merge(xrange(10**9), xrange(10**9))。

在这两种情况下的冗余部分可能可以减少，这样如果你想支持合并多个列表会更有用，但为了让内容更清晰，我在这里没有做这个调整。

def linear_merge(list1, list2):
    """
    >>> a = [1, 3, 5, 7]
    >>> b = [2, 4, 6, 8]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> [i for i in linear_merge(b, a)]
    [1, 2, 3, 4, 5, 6, 7, 8]
    >>> a = [1, 2, 2, 3]
    >>> b = [2, 2, 4, 4]
    >>> [i for i in linear_merge(a, b)]
    [1, 2, 2, 2, 2, 3, 4, 4]
    """
    list1 = iter(list1)
    list2 = iter(list2)

    value1 = next(list1)
    value2 = next(list2)

    # We'll normally exit this loop from a next() call raising StopIteration, which is
    # how a generator function exits anyway.
    while True:
        if value1 <= value2:
            # Yield the lower value.
            yield value1
            try:
                # Grab the next value from list1.
                value1 = next(list1)
            except StopIteration:
                # list1 is empty.  Yield the last value we received from list2, then
                # yield the rest of list2.
                yield value2
                while True:
                    yield next(list2)
        else:
            yield value2
            try:
                value2 = next(list2)

            except StopIteration:
                # list2 is empty.
                yield value1
                while True:
                    yield next(list1)

Answer 3

这个问题讲得比你可能需要的更详细。 ;) 选中的答案符合你的要求。如果我自己需要做这个，我会按照dbr在他或她的回答中描述的方法来做（把列表加在一起，然后对新列表进行排序），因为这样非常简单。

编辑：

我在下面添加了一个实现的例子。其实我在这里看到过另一个答案，但似乎被删除了。我只是希望它不是因为有错误而被删除的，我没有发现这个错误。 ;)

def mergeSortedLists(a, b):
    l = []
    while a and b:
        if a[0] < b[0]:
            l.append(a.pop(0))
        else:
            l.append(b.pop(0))
    return l + a + b