python - カスタムオブジェクトからフィールドごとにヒープ化する方法

Question

クライアントからサーバーオブジェクトを受信して​​います（すべてのオブジェクトは同じ構造を持ち、そのオブジェクトの作成時刻を含むフィールドself.utc_timeを持っています）。何らかの構造で格納する必要があるので、常に昇順で並べ替えているので、ポップするときは、受信する時間ではなく、utc_timeで最も古いオブジェクトをポップします。heapqの優先キューを使用することを考えましたが、カスタムオブジェクトのutc_timeフィールドでheaifyする方法は？より良い解決策はありますか？

Answer 1

Maksimが説明するタプル装飾を行う必要がないように、魔法の__cmp__比較メソッドをクラスに追加します。

>>> import heapq
>>> class MyObject(object):
...     def __init__(self, val):
...         self.val = val
...     def __cmp__(self, other):
...         return cmp(self.val, other.val)
...         
...     
... 
>>> q = []
>>> heapq.heappush(q, MyObject(50))
>>> heapq.heappush(q, MyObject(40))
>>> heapq.heappush(q, MyObject(30))
>>> heapq.heappush(q, MyObject(20))
>>> heapq.heappush(q, MyObject(200))
>>> obj = heapq.heappop(q)
>>> print obj.val
20

注：Python 3でのオーバーライド__lt__、 Python2でのみ__cmp__

Answer 2

Pythonのドキュメントは、暗黙的に次のソリューションを提供します。

ヒープ要素はタプルにすることができます。これは、追跡されるメインレコードと一緒に比較値（タスクの優先順位など）を割り当てる場合に役立ちます。

 h = []
 heappush(h, (5, 'write code'))
 heappush(h, (7, 'release product'))
 heappush(h, (1, 'write spec'))
 heappush(h, (3, 'create tests'))
 heappop(h)
   => (1, 'write spec')

同様の方法でそれを行うことができます-最初の要素がutc_timePQに配置されるオブジェクトのを含み、2番目の要素がオブジェクト自体への参照を含むタプルを格納します。

同様のSOの質問では、優先キューをよりクリーンに操作できるようにする使いやすいラッパーを作成することが提案されています。