Python コードでプライオリティ キューを使用する必要があります。
効率的なものを探し回って、 heapqに出くわしましたが、:
heapqネイティブの Python で実装されている よりも高速なものを探しているので、高速ではありません。heapq、チャーリー・マーティンが提案するように a を使用するか(priority, object)、単に__cmp__オブジェクトに実装することができます。Queue.PriorityQueueを使用できます。
Python は強く型付けされていないので、好きなものを保存できることを思い出してください: のタプルを作成するだけで準備完了(priority, thing)です。
最終的に のラッパーを実装しheapq、キューの要素を一意に維持するための dict を追加しました。結果は、すべての演算子にとって非常に効率的です。
class PriorityQueueSet(object):
"""
Combined priority queue and set data structure.
Acts like a priority queue, except that its items are guaranteed to be
unique. Provides O(1) membership test, O(log N) insertion and O(log N)
removal of the smallest item.
Important: the items of this data structure must be both comparable and
hashable (i.e. must implement __cmp__ and __hash__). This is true of
Python's built-in objects, but you should implement those methods if you
want to use the data structure for custom objects.
"""
def __init__(self, items=[]):
"""
Create a new PriorityQueueSet.
Arguments:
items (list): An initial item list - it can be unsorted and
non-unique. The data structure will be created in O(N).
"""
self.set = dict((item, True) for item in items)
self.heap = self.set.keys()
heapq.heapify(self.heap)
def has_item(self, item):
"""Check if ``item`` exists in the queue."""
return item in self.set
def pop_smallest(self):
"""Remove and return the smallest item from the queue."""
smallest = heapq.heappop(self.heap)
del self.set[smallest]
return smallest
def add(self, item):
"""Add ``item`` to the queue if doesn't already exist."""
if item not in self.set:
self.set[item] = True
heapq.heappush(self.heap, item)
非整数要素 (タプル) には heapq を使用できます。
import heapq
heap = []
data = [(10,"ten"), (3,"three"), (5,"five"), (7,"seven"), (9, "nine"), (2,"two")]
for item in data:
heapq.heappush(heap, item)
sorted_data = []
while heap:
sorted_data.append(heapq.heappop(heap))
print(sorted_data)
data.sort()
print(data == sorted_data)
queue.PriorityQueueこれは、一番上の回答で推奨されているオプションよりも大幅に高速であり、 とは異なりqueue.PriorityQueue、heapq空のヒープからポップしようとしてもハングすることはありません。
私は使用していませんが、PyHeapを試すことができます。C で書かれているので、十分に速いことを願っています。
heapq/PriorityQueue が十分に速くないと確信していますか? それらの 1 つから始めて、それが本当にパフォーマンスのボトルネックであるかどうかを確認するためにプロファイリングを行う価値があるかもしれません。
heapq ページの「Show Source」リンクを見ましたか? (int, char) タプルのリストを持つヒープをプライオリティ キューとして使用する例は、半分以下です。
これは効率的で、文字列や任意のタイプの入力に対しても機能します -:)
import itertools
from heapq import heappush, heappop
pq = [] # list of entries arranged in a heap
entry_finder = {} # mapping of tasks to entries
REMOVED = '<removed-task>' # placeholder for a removed task
counter = itertools.count() # unique sequence count
def add_task(task, priority=0):
'Add a new task or update the priority of an existing task'
if task in entry_finder:
remove_task(task)
count = next(counter)
entry = [priority, count, task]
entry_finder[task] = entry
heappush(pq, entry)
def remove_task(task):
'Mark an existing task as REMOVED. Raise KeyError if not found.'
entry = entry_finder.pop(task)
entry[-1] = REMOVED
def pop_task():
'Remove and return the lowest priority task. Raise KeyError if empty.'
while pq:
priority, count, task = heappop(pq)
if task is not REMOVED:
del entry_finder[task]
return task
raise KeyError('pop from an empty priority queue')
https://pypi.python.org/pypi/fibonacci-heap-modにプライオリティ キュー/フィボナッチ ヒープがあります。
高速ではありません（O（c * logn）であるdelete-minの大きな定数c）。しかし、find-min、insert、decrease-key、merge はすべて O(1) - IOW であり、怠惰です。
CPython で遅すぎる場合は、Pypy、Nuitka、または CPython+Numba を試すこともできます:)
Charlie Martin が提案するように a を使用するか
(priority, object)、単に__cmp__オブジェクトに実装することができます。
挿入されたオブジェクトに特定のルールで優先順位を付けたい場合PriorityQueueは、キー関数を受け入れる単純なサブクラスを作成すると非常に役立つことがわかりました。(priority, object)タプルを手動で挿入する必要がなくなり、処理がより自然になります。
望ましい動作のデモ:
>>> h = KeyHeap(sum)
>>> h.put([-1,1])
>>> h.put((-1,-2,-3))
>>> h.put({100})
>>> h.put([1,2,3])
>>> h.get()
(-1, -2, -3)
>>> h.get()
[-1, 1]
>>> h.get()
[1, 2, 3]
>>> h.get()
set([100])
>>> h.empty()
True
>>>
>>> k = KeyHeap(len)
>>> k.put('hello')
>>> k.put('stackoverflow')
>>> k.put('!')
>>> k.get()
'!'
>>> k.get()
'hello'
>>> k.get()
'stackoverflow'
Python 2 コード
from Queue import PriorityQueue
class KeyHeap(PriorityQueue):
def __init__(self, key, maxsize=0):
PriorityQueue.__init__(self, maxsize)
self.key = key
def put(self, x):
PriorityQueue.put(self, (self.key(x), x))
def get(self):
return PriorityQueue.get(self)[1]
Python 3 コード
from queue import PriorityQueue
class KeyHeap(PriorityQueue):
def __init__(self, key, maxsize=0):
super().__init__(maxsize)
self.key = key
def put(self, x):
super().put((self.key(x), x))
def get(self):
return super().get()[1]
put明らかに、キー関数が処理できないオブジェクトを挿入しようとすると、呼び出しによってエラーが発生します (発生するはずです!)。