合并在python有序列表 [英] Merge sorted lists in python

问题描述

我有一堆的对象排序列表，以及一个比较函数

I have a bunch of sorted lists of objects, and a comparison function

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), ...]

什么呢魔术什么样子的？我目前的实施

what does magic look like? My current implementation is

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

但这是相当低效的。更好的答案？

but that is quite inefficient. Better answers?

推荐答案

Python标准库提供了它的方法：的 heapq.merge 。

由于文件说，这是非常类似于使用和itertools （但有更多的限制）;如果你不能与那些限制生活（或者，如果你不使用Python 2.6），你可以做这样的事情：

Python standard library offers a method for it: heapq.merge.
As the documentation says, it is very similar to using itertools (but with more limitations); if you cannot live with those limitations (or if you do not use Python 2.6) you can do something like this:

sorted(itertools.chain(args), cmp)

不过，我认为它具有相同的复杂性作为自己的解决方案，尽管使用迭代器应该给予一些相当不错的优化和速度的提升。

However, I think it has the same complexity as your own solution, although using iterators should give some quite good optimization and speed increase.

这篇关于合并在python有序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！