python 合并python中的排序列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1158128/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Merge sorted lists in python
提问by Paul Tarjan
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 magiclook like? My current implementation is
哪些呢magic样子？我目前的实现是
def magic(*args) :
r = []
for a in args : r += a
return sorted(r, cmp)
but that is quite inefficient. Better answers?
但这效率很低。更好的答案？
回答by rob
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:
Python 标准库为此提供了一种方法：heapq.merge.
正如文档所说，它与使用itertools非常相似（但有更多限制）；如果您不能忍受这些限制（或者如果您不使用 Python 2.6），您可以执行以下操作：
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.
但是，我认为它与您自己的解决方案具有相同的复杂性，尽管使用迭代器应该可以提供一些非常好的优化和速度提升。
回答by hughdbrown
I like Roberto Liffredo's answer. I didn't know about heapq.merge(). Hmmmph.
我喜欢 Roberto Liffredo 的回答。我不知道 heapq.merge()。嗯嗯。
Here's what the complete solution looks like using Roberto's lead:
以下是使用 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
Or:
或者：
for item in heapq.merge(a,b,c):
print item
回答by ThibThib
Instead of using a list, you can use a [heap](http://en.wikipedia.org/wiki/Heap_(data_structure).
您可以使用 [heap]( http://en.wikipedia.org/wiki/Heap_(data_structure)，而不是使用列表。
The insertion is O(log(n)), so merging a, b and c will be O(n log(n))
插入是 O(log(n))，所以合并 a、b 和 c 将是 O(n log(n))
In Python, you can use the heapqmodule.
在 Python 中，您可以使用heapq模块.
回答by codeape
Use the bisectmodule. From the documentation: "This module provides support for maintaining a list in sorted order without having to sort the list after each insertion."
使用bisect模块。来自文档：“此模块支持按排序顺序维护列表，而无需在每次插入后对列表进行排序。”
import bisect
def magic(*args):
r = []
for a in args:
for i in a:
bisect.insort(r, i)
return r
回答by Jiri
One line solution using sorted:
使用排序的一行解决方案：
def magic(*args):
return sorted(sum(args,[]), key: lambda x: x.points)
IMO this solution is very readable.
IMO 这个解决方案非常具有可读性。
Using heapq module, it could be more efficient, but I have not tested it. You cannot specify cmp/key function in heapq, so you have to implement Obj to be implicitly sorted.
使用 heapq 模块可能会更有效，但我还没有测试过。heapq 中不能指定 cmp/key 函数，所以必须实现 Obj 进行隐式排序。
import heapq
def magic(*args):
h = []
for a in args:
heapq.heappush(h,a)
return [i for i in heapq.heappop(h)
回答by hughdbrown
Here you go: a fully functioning merge sort for lists (adapted from my sort here):
给你：一个功能齐全的列表合并排序（改编自我在这里的排序）：
def merge(*args):
import copy
def merge_lists(left, right):
result = []
while left and right:
which_list = (left if left[0] <= right[0] else right)
result.append(which_list.pop(0))
return result + left + right
lists = list(args)
while len(lists) > 1:
left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0))
result = merge_lists(left, right)
lists.append(result)
return lists.pop(0)
Call it like this:
像这样调用它：
merged_list = merge(a, b, c)
for item in merged_list:
print item
For good measure, I'll throw in a couple of changes to your Obj class:
为了更好地衡量，我将对您的 Obj 类进行一些更改：
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
- Derive from object
- Pass
selfto__init__() - Make
__cmp__a member function - Add a
str()member function to presentObjas string
- 从对象派生
- 传递
self到__init__() - 制作
__cmp__成员函数 - 添加
str()成员函数以显示Obj为字符串
回答by dmw
I asked a similar question and got some excellent answers:
我问了一个类似的问题并得到了一些很好的答案：
The best solutions from that question are variants of the merge algorithm, which you can read about here:
该问题的最佳解决方案是合并算法的变体，您可以在此处阅读：
回答by aong152
Below is an example of a function that runs in O(n) comparisons.
下面是在 O(n) 比较中运行的函数的示例。
You could make this faster by making a and b iterators and incrementing them.
您可以通过创建 a 和 b 迭代器并增加它们来加快速度。
I have simply called the function twice to merge 3 lists:
我只是简单地调用了该函数两次以合并 3 个列表：
def zip_sorted(a, b):
'''
zips two iterables, assuming they are already sorted
'''
i = 0
j = 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
result.append(a[i])
i += 1
else:
result.append(b[j])
j += 1
if i < len(a):
result.extend(a[i:])
else:
result.extend(b[j:])
return result
def genSortedList(num,seed):
result = []
for i in range(num):
result.append(i*seed)
return result
if __name__ == '__main__':
a = genSortedList(10000,2.0)
b = genSortedList(6666,3.0)
c = genSortedList(5000,4.0)
d = zip_sorted(zip_sorted(a,b),c)
print d
However, heapq.mergeuses a mix of this method and heaping the current elements of all lists, so should perform much better
但是，heapq.merge混合使用了这种方法和堆所有列表的当前元素，所以应该表现得更好
回答by DrAl
I don't know whether it would be any quicker, but you could simplify it with:
我不知道它是否会更快，但你可以简化它：
def GetObjKey(a):
return a.points
return sorted(a + b + c, key=GetObjKey)
You could also, of course, use cmprather than keyif you prefer.
当然，如果您愿意，您也可以使用cmp而不是key。
