合并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

Python标准库为它提供了一种方法:heapq.merge.
正如文档所说,它与使用itertools非常相似(但有更多限制); 如果您不能忍受这些限制(或者如果您不使用Python 2.6),您可以执行以下操作:

sorted(itertools.chain(args), cmp)

但是,我认为它与您自己的解决方案具有相同的复杂性,尽管使用迭代器应该会给出一些非常好的优化和速度提升.