3

我想知道heap.merge(). 合并元组列表时，heapq.merge() 如何决定顺序？

我得到了两个列表，每个列表都有一个 3 元组，

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

其中 3 元组的类型为(int, int, str)。我想合并这两个列表。我正在使用heapq.merge()操作，因为它高效且针对大型列表进行了优化。A 和 B 可以包含数百万个三元组。

是否保证heap.merge()会在给定两个元组的情况下输出一个订单，

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

1 回答 1

3

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

但是请注意，尽管这改变了我们对<for的概念MyTuple，但不能保证返回的结果heapq.merge满足

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

为此，我们必须首先删除所有相互不可排序的项目A。B

于 2012-12-28T02:42:12.980 回答