在Python中组合两个sorting列表
我有两个对象列表。 每个列表已经被date时间types的对象的属性sorting。 我想将这两个列表组合成一个sorting列表。 只是做一个sorting的最好方法，还是有更聪明的方法来在Python中做到这一点？
人们似乎已经过分复杂化了。只需将两个列表合并，然后对其进行sorting：
>>> 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]
..简单！ 另外，它只使用了两个内置函数，所以假设列表的大小合理，应该比在循环中执行sorting/合并更快。 更重要的是，上面的代码less得多，而且非常可读。
如果您的列表很大（超过几十万，我猜），使用替代/自定义sorting方法可能会更快，但是有可能首先进行其他优化（例如，不存储数百万个datetime对象）
使用timeit.Timer().repeat() （重复函数1000000次），我松散地将其与ghoseb的解决scheme进行比较， sorted(l1+l2)
merge_sorted_lists花了..
[9.7439379692077637, 9.8844599723815918, 9.552299976348877]
sorted(l1+l2)
[2.860386848449707, 2.7589840888977051, 2.7682540416717529]
有没有更聪明的方法来做到这一点在Python中
这个没有提到，所以我会继续 – python 2.6+的heapq模块中有一个合并的stdlib函数 。 如果你所要做的只是让事情完成，这可能是一个更好的主意。 当然，如果你想实现你自己的，merge-sort的合并是一条路。
>>> 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]
长话短说，除非len(l1 + l2) ~ 1000000使用：
L = l1 + l2 L.sort()
图的描述和源代码可以在这里find。
该图是由以下命令生成的：
$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin
这只是合并。 将每个列表视为一个堆栈，并不断popup两个堆栈头中较小的一个，将该项添加到结果列表中，直到其中一个堆栈为空。 然后将所有剩余的项目添加到结果列表中。
ghoseb的解决scheme有一个小缺陷，使得它是O（n ** 2），而不是O（n）。
问题是这是performance：
item = l1.pop(0)
使用链接列表或deques，这将是一个O（1）操作，所以不会影响复杂性，但是由于python列表是作为向量实现的，因此这会复制剩下的一个空格剩余空格，一个O（n）操作。 由于这是每次通过列表完成，它将一个O（n）algorithm变成一个O（n ** 2）。 这可以通过使用不改变源列表的方法来纠正，但只是跟踪当前位置。
我已经尝试了一个修正后的algorithm与一个简单的sorting（l1 + l2）如dbrbuild议的基准
def merge(l1,l2): if not l1: return list(l2) if not l2: return list(l1) # l2 will contain last element. if l1[-1] > l2[-1]: l1,l2 = l2,l1 it = iter(l2) y = it.next() result = [] for x in l1: while y < x: result.append(y) y = it.next() result.append(x) result.append(y) result.extend(it) return result
我已经用生成的列表testing过这些
l1 = sorted([random.random() for i in range(NITEMS)]) l2 = sorted([random.random() for i in range(NITEMS)])
对于各种大小的列表，我得到以下时间（重复100次）：
# items: 1000 10000 100000 1000000 merge : 0.079 0.798 9.763 109.044 sort : 0.020 0.217 5.948 106.882
所以实际上，看起来像dbr是正确的，只要使用sorted（）是可取的，除非你期望非常大的列表，尽pipe它algorithm复杂性更差。 每个来源清单（总计200万）的收支平衡点约为100万件。
合并方法的一个优点是重写为一个生成器，这将使用less得多的内存（不需要中间列表）是微不足道的。
[编辑]我已经重试了一个更接近问题的情况 – 使用一个包含一个date对象的“ date ”字段的对象列表。 上面的algorithm改为与.date进行比较，sorting方法改为：
return sorted(l1 + l2, key=operator.attrgetter('date'))
这确实改变了一些事情。 比较成本更高意味着我们执行的数量相对于实现的恒定时间速度变得更重要。 这意味着合并弥补了失地，反而超过了100000项的sort（）方法。 基于更复杂的对象（例如大string或列表）进行比较可能会进一步改变这种平衡。
# items: 1000 10000 100000 1000000[1] merge : 0.161 2.034 23.370 253.68 sort : 0.111 1.523 25.223 313.20
[1]：注意：实际上我只做了10次重复100万个项目，并相应地放大了，因为它非常慢。
from datetime import datetime from itertools import chain from operator import attrgetter class DT: def __init__(self, dt): self.dt = dt list1 = [DT(datetime(2008, 12, 5, 2)), DT(datetime(2009, 1, 1, 13)), DT(datetime(2009, 1, 3, 5))] list2 = [DT(datetime(2008, 12, 31, 23)), DT(datetime(2009, 1, 2, 12)), DT(datetime(2009, 1, 4, 15))] list3 = sorted(chain(list1, list2), key=attrgetter('dt')) for item in list3: print item.dt
输出：
2008-12-05 02:00:00 2008-12-31 23:00:00 2009-01-01 13:00:00 2009-01-02 12:00:00 2009-01-03 05:00:00 2009-01-04 15:00:00
我敢打赌，这比任何奇特的纯Python合并algorithm都快，即使是大数据。 Python 2.6的heapq.merge是另一回事。
这是两个sorting列表的简单合并。 看看下面的示例代码，它合并两个sorting的整数列表。
#!/usr/bin/env python ## merge.py -- Merge two sorted lists -*- Python -*- ## Time-stamp: "2009-01-21 14:02:57 ghoseb" l1 = [1, 3, 4, 7] l2 = [0, 2, 5, 6, 8, 9] def merge_sorted_lists(l1, l2): """Merge sort two sorted lists Arguments: - `l1`: First sorted list - `l2`: Second sorted list """ sorted_list = [] # Copy both the args to make sure the original lists are not # modified l1 = l1[:] l2 = l2[:] while (l1 and l2): if (l1[0] <= l2[0]): # Compare both heads item = l1.pop(0) # Pop from the head sorted_list.append(item) else: item = l2.pop(0) sorted_list.append(item) # Add the remaining of the lists sorted_list.extend(l1 if l1 else l2) return sorted_list if __name__ == '__main__': print merge_sorted_lists(l1, l2)
这应该适用于date时间对象。 希望这可以帮助。
Python的sorting实现“timsort”专门针对包含有序部分的列表进行了优化。 另外，它是用C写成的
http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort
正如人们所提到的那样，它可以通过一些常数因子来多次调用比较函数（但是在很多情况下可能会在更短的时间内多次调用它）。
然而，我绝不会依赖这个。 – Daniel Nadasi
我相信Python开发人员致力于保持timsort，或者至less在这种情况下保持一种O（n）。
通用sorting（即将有限域内的基数sorting）
在串行机器上不能less于O（n log n）。 – 巴里凯利
对，在一般情况下sorting不能比这更快。 但是由于O（）是一个上界，所以在任意input上的timsort是O（n log n）并不违背给定sorting（L1）+sorting（L2）的O（n）。
使用合并sorting的“合并”步骤，它运行在O（n）时间。
从维基百科 （伪代码）：
function merge(left,right) var list result while length(left) > 0 and length(right) > 0 if first(left) ≤ first(right) append first(left) to result left = rest(left) else append first(right) to result right = rest(right) end while while length(left) > 0 append left to result while length(right) > 0 append right to result return result
recursion实现如下。 平均performance是O（n）。
def merge_sorted_lists(A, B, sorted_list = None): if sorted_list == None: sorted_list = [] slice_index = 0 for element in A: if element <= B[0]: sorted_list.append(element) slice_index += 1 else: return merge_sorted_lists(B, A[slice_index:], sorted_list) return sorted_list + B
或发生器，改善了空间复杂性：
def merge_sorted_lists_as_generator(A, B): slice_index = 0 for element in A: if element <= B[0]: slice_index += 1 yield element else: for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]): yield sorted_element return for element in B: yield element
如果你想以更符合迭代的方式学习，可以尝试一下
def merge_arrays(a, b): l= [] while len(a) > 0 and len(b)>0: if a[0] < b[0]: l.append(a.pop(0)) else:l.append(b.pop(0)) l.extend(a+b) print( l )
import random n=int(input("Enter size of table 1")); #size of list 1 m=int(input("Enter size of table 2")); # size of list 2 tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100 tb1.sort(); #sort the list 1 tb2.sort(); # sort the list 2 fus=[]; # creat an empty list print(tb1); # print the list 1 print('------------------------------------'); print(tb2); # print the list 2 print('------------------------------------'); i=0;j=0; # varialbles to cross the list while(i<n and j<m): if(tb1[i]<tb2[j]): fus.append(tb1[i]); i+=1; else: fus.append(tb2[j]); j+=1; if(i<n): fus+=tb1[i:n]; if(j<m): fus+=tb2[j:m]; print(fus); # this code is used to merge two sorted lists in one sorted list (FUS) without #sorting the (FUS)
使用了合并sorting的合并步骤。 但我用过发电机 时间复杂度 O（n）
def merge(lst1,lst2): len1=len(lst1) len2=len(lst2) i,j=0,0 while(i<len1 and j<len2): if(lst1[i]<lst2[j]): yield lst1[i] i+=1 else: yield lst2[j] j+=1 if(i==len1): while(j<len2): yield lst2[j] j+=1 elif(j==len2): while(i<len1): yield lst1[i] i+=1 l1=[1,3,5,7] l2=[2,4,6,8,9] mergelst=(val for val in merge(l1,l2)) print(*mergelst)
那么，天真的方法（将2个列表合并为一个大的sorting）将是O（N * log（N））复杂度。 另一方面，如果您手动实现合并（我不知道任何就绪的代码在Python库中，但我不是专家）复杂性将是O（N），这显然更快。 这个想法在Barry Kelly的post里描述得很好。
def compareDate(obj1, obj2): if obj1.getDate() < obj2.getDate(): return -1 elif obj1.getDate() > obj2.getDate(): return 1 else: return 0 list = list1 + list2 list.sort(compareDate)
将sorting清单。 定义自己的函数来比较两个对象，并将该函数传递给内置的sorting函数。
不要使用冒泡sorting，它有可怕的performance。
def merge_sort(a,b): pa = 0 pb = 0 result = [] while pa < len(a) and pb < len(b): if a[pa] <= b[pb]: result.append(a[pa]) pa += 1 else: result.append(b[pb]) pb += 1 remained = a[pa:] + b[pb:] result.extend(remained) return result
