3

のマージ動作について知りたかったのheap.merge()です。タプルのリストをマージするとき、heapq.merge() はどのように順序を決定しますか?

それぞれ 3 タプルを持つ 2 つのリストが与えられ、

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

3 タプルのタイプは(int, int, str). 2 つのリストを結合したかったのです。heapq.merge()大規模なリストに対して効率的で最適化されているため、操作を使用しています。A と B には、数百万の 3 タプルが含まれる可能性があります。

heap.merge()2つのタプルが与えられた場合に注文を出力することが保証されていますか?

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

1 に答える 1

3

Python はタプルを辞書順でソートします:

最初に最初の 2 つの項目が比較され、それらが異なる場合は、比較の結果が決定されます。それらが等しい場合は、次の 2 つの項目が比較され、いずれかのシーケンスが使い果たされるまで続きます。

たとえば、

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 に答える