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

这是文档.

Answer 3

长话短说,除非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

Answer 4

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

Answer 5

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次重复,并且相应地按比例放大,因为它非常慢.

Answer 6

这是两个排序列表的简单合并。看看下面的示例代码，它合并了两个排序的整数列表。

#!/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)

这应该适用于日期时间对象。希望这可以帮助。