在Python中组合两个排序列表

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

1> dbr..：

---

人们似乎过度复杂了.只需将两个列表合并,然后对它们进行排序:

>>> 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]

---

对通过附加两个列表创建的非常短的列表进行排序确实非常快,因为常量开销将占主导地位.尝试为包含数百万个项目的列表或具有数十亿个项目的磁盘上的文件执行此操作,您很快就会发现为什么合并更可取.

---

@Deestan:我不同意 - 有时候速度会受到其他因素的支配.例如.如果你在磁盘上排序数据(合并2个文件),IO时间可能会占主导地位,而python的速度也不会太大,只需要你操作的次数(以及算法).

---

最后一个明智的答案,考虑实际*基准*.:-) ---另外,1行维持而不是15-20是很受欢迎的.

---

@Barry:如果你有"数十亿项"和速度要求,那么*Python中的任何*都是错误的答案.

---

真的吗？使用10个条目列表对排序函数进行基准测试？

2> sykora..：

---

有没有更聪明的方法在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]

这是文档.

---

我添加了到heapq.py的链接.`merge()`是作为一个纯python函数实现的,所以很容易将它移植到较旧的Python版本.

---

“ heapq.merge”的卖点是它不需要输入或输出都是“ list”。它可以消耗迭代器/生成器并生成一个生成器，因此可以合并大量输入/输出（不立即存储在RAM中）而不会发生交换颠簸。它还可以以低于预期的开销来处理任意数量的输入可迭代项的合并（它使用堆来协调合并，因此开销与可迭代项数的对数成比例地扩展，而不是线性地缩放，但是正如所指出的那样，与“两个可迭代”情况无关）。

3> jfs..：

---

长话短说,除非len(l1 + l2) ~ 1000000使用:

L = l1 + l2
L.sort()

可以在此处找到图形和源代码的描述.

该图由以下命令生成:

$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin

4> Barry Kelly..：

---

这只是合并.将每个列表视为堆栈,并连续弹出两个堆栈头中较小的一个,将项添加到结果列表中,直到其中一个堆栈为空.然后将所有剩余项添加到结果列表中.

---

这只是一个合并,而不是合并排序.

---

但它比使用Python的内置排序更快吗？

---

@akaihola:如果`len(L1 + L2)<1000000`那么`排序(L1 + L2)`更快http://stackoverflow.com/questions/464342/combining-two-sorted-lists-in-python/482848 #482848

5> Brian..：

---

ghoseb溶液存在轻微缺陷,使其为O(n**2),而不是O(n).
问题是这是在执行:

item = l1.pop(0)

对于链接列表或deques,这将是一个O(1)操作,因此不会影响复杂性,但由于python列表是作为向量实现的,因此复制剩余的l1个元素剩下的一个空格,一个O(n)操作.由于每次都通过列表,因此将O(n)算法转换为O(n**2)算法.这可以通过使用不改变源列表的方法来纠正,但只是跟踪当前位置.

我已经尝试将校正算法与dbr建议的简单排序(l1 + l2)进行基准测试

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

我已经使用生成的列表测试了这些

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()是可取的,除非你期望非常大的列表,尽管它的算法复杂度更差.收支平衡点在每个源列表中大约有一百万个项目(总计200万).

然而,合并方法的一个优点是重写为生成器是微不足道的,它将使用更少的内存(不需要中间列表).

[编辑] 我在接近问题的情况下重试了这个问题 - 使用包含字段" date" 的对象列表,这是一个日期时间对象.改为将上述算法改为比较.date,并将sort方法更改为:

return sorted(l1 + l2, key=operator.attrgetter('date'))

这确实改变了一些事情.比较更昂贵意味着我们执行的数量相对于实现的恒定时间速度变得更加重要.这意味着合并弥补了失地,超过了100,000个项目的sort()方法.基于更复杂的对象(例如,大字符串或列表)进行比较可能会更加平衡这种平衡.

# 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]:注意:我实际上只对1,000,000个项目进行了10次重复,并且相应地按比例放大,因为它非常慢.