python中堆模塊中的元組合

Question

我想知道heap.merge()的合併行爲。 heapq.merge（）如何在合併元組列表時決定順序。

我給每個兩個列表與一個三元組，

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? 

Answer 1

的Python在lexicographic order排序元組：

第一頭兩個項目進行比較，如果不同，就 確定比較的結果;如果它們相等，則比較兩個項目的下一個 ，依此類推，直到任一序列被耗盡。

---

舉個例子，

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中刪除所有相互無法訂購的項目。