在Python的堆模块中合并元组

Question

在Python的堆模块中合并元组

3

我希望了解heap.merge()的合并行为。当合并元组列表时，heapq.merge()如何决定顺序？

我有两个包含3个元素的元组列表：

A = [(a, b, c)]
B = [(x, y, z)]

这里的3元组类型为(int, int, str)。我想要将两个列表合并，使用 heapq.merge() 操作可以在处理大型列表时保证效率和优化。A 和 B 可能包含数百万个3元组。

请问heap.merge() 保证输出的顺序是给定两个元组的顺序吗？

a >= x and b >= y and c >= z?

- user1867185

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- unutbu · Accepted Answer

Python按词典顺序排序元组：

首先比较前两个项目，如果它们不同，则确定比较结果; 如果它们相等，则比较下两个项目，依此类推，直到任一序列用尽。

例如，

In [33]: import heapq    
In [34]: A = [(1,100,2)]    
In [35]: B = [(2,0,0)]

In [40]: list(heapq.merge(A,B))
Out[40]: [(1, 100, 2), (2, 0, 0)]

In [41]: (1, 100, 2) < (2, 0, 0)
Out[41]: True

因此，并不一定是真的。

a >= x and b >= y and c >= z

可以在包括自定义类实例在内的任何可排序对象集合上使用heapq。使用自定义类，您可以安排任何类型的排序规则。例如，

class MyTuple(tuple):
    def __lt__(self, other):
        return all(a < b for a, b in zip(self, other))
    def __eq__(self, other):
        return (len(self) == len(other)
                and all(a == b for a, b in zip(self, other)))
    def __gt__(self, other):
        return not (self < other or self == other)            
    def __le__(self, other):
        return self < other or self == other
    def __ge__(self, other):
        return not self < other

A = [MyTuple((1,100,2))]
B = [MyTuple((2,0,0))]
print(list(heapq.merge(A,B)))
# [(2, 0, 0), (1, 100, 2)]

请注意，虽然这改变了我们对于 MyTuple 中 < 的概念，但是由 heapq.merge 返回的结果不能保证满足。

a <= x and b <= y and c <= z

为了实现这一点，我们首先需要从A和B中删除所有无序的项目。