在Python中合并两个排序的列表

Question

我有两个对象列表。每个列表已经按日期时间类型的对象的属性排序。我想将两个列表合并为一个排序的列表。最好的方法是仅执行排序，还是在Python中有更聪明的方法来执行此操作？

Answer 1

人们似乎对此过于复杂了。只需组合两个列表，然后对它们进行排序：

>>> l1 = [1, 3, 4, 7]

>>> l2 = [0, 2, 5, 6, 8, 9]

>>> l1.extend(l2)

>>> sorted(l1)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

..或更短（且无需修改l1）：

>>> sorted(l1 + l2)

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

..简单！另外，它仅使用两个内置函数，因此，假设列表的大小合理，则比在循环中实现排序/合并要快。更重要的是，以上代码少得多，而且可读性强。

如果您的列表很大（我想可能超过几十万），则使用替代/自定义排序方法可能会更快，但是可能首先要进行其他优化（例如，不存储数百万个datetime对象）

使用timeit.Timer().repeat()（将功能重复1000000次），我将其相对于ghoseb的解决方案进行了基准测试，并且sorted(l1+l2)速度更快：

merge_sorted_lists 拿..

[9.7439379692077637, 9.8844599723815918, 9.552299976348877]

sorted(l1+l2) 拿..

[2.860386848449707, 2.7589840888977051, 2.7682540416717529]

Answer 2

有没有更聪明的方式在Python中做到这一点

这没有被提及，所以我继续-python 2.6+的heapq模块中有一个合并stdlib函数。如果您只是想把事情做好，那么这可能是一个更好的主意。当然，如果您想实现自己的实现，则合并归类排序是可行的方法。

>>> list1 = [1, 5, 8, 10, 50]

>>> list2 = [3, 4, 29, 41, 45, 49]

>>> from heapq import merge

>>> list(merge(list1, list2))

[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]

这是文档。