Python合并列表

Question

mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ]
import time
def timeit(f):
    def wrapper(*args, **kw):
        t = time.time()
        res = f(*args, **kw)
        print "%s took %s" % (f.func_name, time.time() - t)
        return res

    return wrapper

# merge two given lists
def merge(l, r):
    if len(l) == 0:
        return r

    if len(r) == 0:
        return l

    if l[0] <= r[0]:
        return [l[0]] + merge(l[1:], r)
    else:
        return [r[0]] + merge(l, r[1:])

def merge2(x,y):
    if len(x) == 0:
        return y
    if len(y) == 0:
        return x

    #pop the lower one between the two biggest items
    last = y.pop() if x[-1] < y[-1] else x.pop()

    merged = merge2(x,y)
    merged.append(last)

    return merged

def merge3(xs, ys):
    ms = []
    i = 0
    j = 0

    while i < len(xs) and j < len(ys):
        if xs[i] <= ys[j]:
            ms.append(xs[i])
            i = i + 1
        else:
            ms.append(ys[j])
            j = j + 1 
    while i < len(xs) and j == len(ys):
        ms.append(xs[i])
        i = i + 1

    while i == len(xs) and j < len(ys):
        ms.append(xs[i])
        j = j + 1

    return ms

# divide and conquer
def lmerge(lists, m):
    if len(lists) <= 1:
        return lists

    mid = len(lists) / 2

    llists = lmerge(lists[:mid], m)
    rlists = lmerge(lists[mid:], m)

    # the bottom merge will have a list of list
    if isinstance(llists[0], list):
        llists = llists[0]
    if isinstance(rlists[0], list):
        rlists = rlists[0]

    return m(llists, rlists)

@timeit
def a():
    print lmerge(mylists, merge)

@timeit
def b():
    print lmerge(mylists, merge2)

@timeit
def c():
    print lmerge(mylists, merge3)

@timeit
def d():
    print sorted(reduce(lambda x,y: x + y, mylists))


a()
b()
c()
d()

---

^{pr2}$

有点搞不清为什么merge3的提升和索引错误？在

merge，merge2，merge3应该有相同的输出（至少在我的脑海中是这样的），所以我不明白为什么它会引发索引错误，因为它适用于merge和merge2

编辑：如果有更好的合并算法，我可以有一个更好的合并算法吗？在

Answer 1

我想在merge3()结尾处有个错误。 如果i == len(xs)，那么由于xs[i]超出范围，ms.append(xs[i])将始终失败。在

while i == len(xs) and j < len(ys):
    #ms.append(xs[i]) # Possibly wrong.
    ms.append(ys[j]) # I think that is what you want instead.
    ....

你不会再出现索引超出范围的错误，你的算法现在应该可以正常工作了。在

Answer 2

你有几个问题。调试是一件艰难的事情，尤其是当它是您自己的代码时。我给你的第一个建议是开始在代码中放入print语句，看看问题出在哪里，出了什么问题。如果你希望“mylist”之类的东西看起来总是一样的，那就去看看它是否会改变。在

话虽如此，事情是这样的：

我的第一个建议是检查一下在每次合并中“mylist”会发生什么。现在你认为问题出在合并3。但在你到达那一步之前，确实有一些奇怪的事情发生了。在

在merge2中使用对merge2的递归调用。这太棒了，因为递归太棒了。但是当你到达这两个列表的末尾时会发生什么呢？当列表被传递到函数中时，它们发生了什么？如果merge2到达x或y的末尾，它将返回x或y。但是x或y是什么呢？它们是传入python的原始列表，随着时间的推移，被修改了。在merge2中，实际上是在更改传入的列表。但是，你可能会说，当我复制这些列表时，也会发生同样的事情！好的，让我们用标准的temp_lists=list（mylist）复制一个列表，并检查您传入的所有内容的ID。注释出a（）、c（）和d（）并将b（）改为如下所示并检查：

@timeit
def b():
    temp_lists = []
    temp_lists = list(mylists)  #making our copy here
    print "in b"
    print "id of temp_lists is: ", id(temp_lists)
    print "id of mylists is: ", id(mylists)
    print "id of temp_lists[0] is: ", id(temp_lists[0])
    print "id of mylists[0] is: ", id(mylists[0])
    print lmerge(temp_lists, merge2)
    print "after b"
    print "id of temp_lists[0] is: ", id(temp_lists[0])
    print "id of mylists[0] is: ", id(mylists[0])

输出应如下所示：

^{pr2}$

注意temp_list和mylist的id不同，但是temp_list[0]和mylist[0]的id是相同的。这意味着当你从每个列表中弹出一些东西来合并它们时，你正在修改原始列表。有几种方法可以解决这个问题。退房复制.deepcopy（）或者，根据此问题的上下文，编写自己的方法递归地复制列表。在

您还有其他问题（例如，如果您在我的列表中传入一个空列表，会发生什么情况？）但是，现在，您的问题在于如何处理传入merge2的列表。在

Answer 3

除非我错过了什么，否则很容易做到：

mylists = [ [1,3,5,7], [2,4,7,8], [11,15], [20] ]
newlist = []
for elem in mylists:
    newlist.extend(elem)
newlist = sorted(newlist)