在Python中合并有序列表

Question

我有一堆已经排好序的对象列表，还有一个比较函数。

class Obj :
    def __init__(p) :
        self.points = p
def cmp(a, b) :
    return a.points < b.points

a = [Obj(1), Obj(3), Obj(8), ...]
b = [Obj(1), Obj(2), Obj(3), ...]
c = [Obj(100), Obj(300), Obj(800), ...]

result = magic(a, b, c)
assert result == [Obj(1), Obj(1), Obj(2), Obj(3), Obj(3), Obj(8), ...]

那么这个magic应该是什么样子的呢？我现在的实现方式是：

def magic(*args) :
    r = []
    for a in args : r += a
    return sorted(r, cmp)

不过这样效率挺低的。有没有更好的方法？

Answer 1

使用 bisect 模块。根据文档的说明：“这个模块可以帮助你保持一个列表的顺序整齐，而不需要在每次添加新元素后都去排序。”

import bisect

def magic(*args):
    r = []
    for a in args:
        for i in a:
            bisect.insort(r, i)
    return r

Answer 2

我很喜欢Roberto Liffredo的回答。我之前不知道有heapq.merge()这个东西。唔。

下面是根据Roberto的思路，完整的解决方案：

class Obj(object):
    def __init__(self, p) :
        self.points = p
    def __cmp__(self, b) :
        return cmp(self.points, b.points)
    def __str__(self):
        return "%d" % self.points

a = [Obj(1), Obj(3), Obj(8)]
b = [Obj(1), Obj(2), Obj(3)]
c = [Obj(100), Obj(300), Obj(800)]

import heapq

sorted = [item for item in heapq.merge(a,b,c)]
for item in sorted:
    print item

或者：

for item in heapq.merge(a,b,c):
    print item

Answer 3

Python的标准库里有一个方法可以做到这一点：heapq.merge。
根据文档的说法，这个方法和使用itertools很相似（不过有一些限制）；如果你觉得这些限制太麻烦（或者你用的不是Python 2.6），你可以尝试下面这种方法：

sorted(itertools.chain(args), cmp)

不过，我觉得这个方法的复杂度和你自己的解决方案差不多，虽然使用迭代器应该能带来一些不错的优化和速度提升。