在Python中组合两个排序列表
在Python中组合两个排序列表
提问于 2009-01-21 07:33:48
我有两个对象列表。每个列表已经按datetime类型的对象的属性进行了排序。我想将这两个列表合并为一个排序列表。排序是最好的方式，还是在Python中有更聪明的方式？
回答 17
Stack Overflow用户
回答已采纳
发布于 2009-01-21 09:14:08
人们似乎把这件事复杂化了。只需合并这两个列表，然后对它们进行排序：
>>> 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]..or更短(且不修改l1)：
>>> sorted(l1 + l2)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]..easy！此外，它只使用了两个内置函数，因此假设列表的大小合理，它应该比在循环中实现排序/合并更快。更重要的是，上面的代码要少得多，而且可读性很好。
如果你的列表很大(我猜超过几十万)，使用替代/自定义排序方法可能会更快，但可能还需要先进行其他优化(例如，不存储数百万个datetime对象)。
使用timeit.Timer().repeat() (它将函数重复1000000次)，我将其与ghoseb's解决方案进行了松散的基准测试，sorted(l1+l2)的速度要快得多：
merge_sorted_lists带了..。
[9.7439379692077637, 9.8844599723815918, 9.552299976348877]sorted(l1+l2)带了..。
[2.860386848449707, 2.7589840888977051, 2.7682540416717529]Stack Overflow用户
发布于 2009-01-27 10:09:04
长话短说，除非len(l1 + l2) ~ 1000000使用：
L = l1 + l2
L.sort()
图中的描述和源代码可以在here上找到。
该图是由以下命令生成的：
$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtinStack Overflow用户
发布于 2009-01-21 07:36:52
这就是简单的合并。将每个列表视为堆栈，并连续弹出两个堆栈头中较小的一个，将项目添加到结果列表中，直到其中一个堆栈为空。然后将所有剩余项添加到结果列表中。
res = []
while l1 and l2:
if l1[0] < l2[0]:
res.append(l1.pop(0))
else:
res.append(l2.pop(0))
res += l1
res += l2页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/464342
复制相关文章
相似问题