私はpython2.6を使用しています。それはPythonのより高いバージョンで利用可能ですか？
これ以外の方法で、私は非自明なクラスのオブジェクトのリストの優先順位キューを維持できますか？ 私が必要とするものは次のようなものですPythonでは、heapq.heapifyはソートされたように、cmpやkey関数を引数として受け取りません
>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
... return x[1]-y[1]
>>> heap = heapify(l, cmp=foo)
ご意見はありますか？
伝統的な解決策は、ヒープ上（優先度、タスク）のタプルを格納することです：これは限りどの2つのタスクが同じ優先順位を持っていないと正常に動作します
pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)
。さもなければ、タスク自体が比較されます（これはPython 3では全く機能しません）。
定期的なドキュメントがheapqを使用して優先度キューを実装する方法に関する指針を与える：
http://docs.python.org/library/heapq.html#priority-queue-implementation-notes
だけので、彼らの並べ替えが正しくリスト内のオブジェクトのための適切な__lt__方法書き込み：それは比較または使用のすべてを定義するのは良い考えですけれどものみ__lt__をソートするためのPythonが必要とされ
class FirstList(list):
def __lt__(self, other):
return self[0] < other[0]
lst = [ ['a', 3], ['b', 1] ]
lst = [FirstList(item) for item in lst]
同じ最初の値と異なる2番目の値を持つ2つのアイテムを使用することで、動作していることがわかります。 lst[0] < lst[1]は常にFalseになるため、2つ目の値が何であっても、heapifyのときに2つのオブジェクトが場所を入れ替えます。 heapifyが安定している必要がある場合は、より複雑な比較が必要です。
PEP 8では、6つの比較をすべて定義し、コンシューマ機能の実装の詳細には依存しないことをお勧めします。 –
@RaymondHettinger私はこれが一般的なアドバイスだと知っていますが、この場合は必要です。ユースケースは、任意の比較ではなく、特定の目的のためです。 「混乱が他のコンテキストでは発生しないように、6つの操作をすべて実装するのが最善です」というのは、1つのコンテキストでしか動作していない場合には当てはまりません。 – agf
6つの操作すべてを楽にサポートするために '' @ functools.total_ordering''を追加するのは簡単です。 FWIWでは、PEP 8のアドバイスはヒープを処理する内容に適用されます。 \ _ \ _ lt \ _ \ _（）の使用は実装固有の詳細であり、変更される可能性があります。まあまあ、代わりに\ _ \ _ le \ _ \ _（）を呼び出しました。 –
まあ、これは恐ろしいことですが、間違いはありません...しかし、heapqモジュールdefines a cmp_lt functionのように見えます。カスタム比較機能が本当に必要な場合は、これを修正することができます。
なぜそれはひどいですか？わたしにはできる！この手法を使ってmax-heapを実装することもできます。 – Nullpoet
あなたが慎重でなければ、 'heapq'モジュールを使う他のコードを壊し、' horribly * 'heapq'モジュールを猿のパッチにしようとする他のコードを壊すので、ひどいと恐ろしいです。このようなアルゴリズムを実装している多くのPythonモジュールの作者であるRaymond Hettingerのアドバイスに従う方がよいでしょう。 –
これは良いですが、それはレイモンドヘッティンガーのソリューションのようなものですが、優先順位がから決定された場合、私は知りませんオブジェクト。
これをあなたのオブジェクトとし、x属性でソートしたいとします。
class Item:
def __init__(self, x):
self.x = x
は、次に次に私に次のような出力を与えたheapq.merge
list(heapq.merge(create_pairs([Item(1), Item(3)]),
create_pairs([Item(2), Item(5)])))
への入力としてリストに関数を適用ペアリングに
def create_pairs(items):
return map(lambda item: (item.x, item), items)
を適用する機能を持っている
[(1, <__main__.Item instance at 0x2660cb0>),
(2, <__main__.Item instance at 0x26c2830>),
(3, <__main__.Item instance at 0x26c27e8>),
(5, <__main__.Item instance at 0x26c2878>)]
[ heapqが特定の属性のヒープを評価する方法？]（http://stackoverflow.com/questions/3954530/how-to-make-heapq-evaluate-the-heap-off-of-a-specific-attribute ） –