Pythonの一般的な優先度キュー

StackOverflow https://stackoverflow.com/questions/407734

  •  03-07-2019
  •  | 
  •  

質問

Pythonコードで優先度キューを使用する必要があります。効率的なものを探して、 heapq に出会いました。良さそうに見えますが、整数に対してのみ指定されているようです。比較演算子を持つすべてのオブジェクトで機能すると思いますが、必要な比較演算子を指定しません。

さらに、 heapq はPythonで実装されているようですので、高速ではありません。

Pythonの優先度キューの高速実装を知っていますか？最適には、キューをジェネリックにする（つまり、指定された比較演算子を持つオブジェクトに対して適切に機能する）ことを望んでいます。

事前に感謝

更新：

heapq の比較では、Charlie Martinが提案するように（priority、object）を使用するか、単に __ cmp __ を実装することができますオブジェクト。

heapq よりも高速なものを探しています。

役に立ちましたか？

解決

Queue.PriorityQueue を使用できます。

Pythonは強く型付けされていないので、好きなものを保存できることを思い出してください：（priority、thing）のタプルを作成するだけで設定できます。

他のヒント

最終的に heapq のラッパーを実装し、キューの要素を一意に維持するための辞書を追加しました。結果はすべてのオペレーターにとって非常に効率的です：

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)

優先度キューを使用する場合、多くのアルゴリズム（Dijkstraのアルゴリズム、A *、OPTICS）で減少キーは必須の操作であるため、Pythonの組み込み優先度キューがそれをサポートしないのはなぜでしょうか。他の回答では、この機能をサポートするソリューションは提供されていません。

減少キー操作もサポートする優先度キューは、このの実装です。 Python 3.5で。

from heapdict import heapdict

hd = heapdict()
hd["two"] = 2
hd["one"] = 1
obj = hd.popitem()
print("object:",obj[0])
print("priority:",obj[1])

# object: one
# priority: 1

使用していませんが、 PyHeap を試すことができます。それはCで書かれているので、うまくいけばそれがあなたにとって十分に速いです。

正のheapq / PriorityQueueは十分に高速ではないでしょうか？それらのうちの1つを使用して開始し、それが実際にパフォーマンスの問題であるかどうかをプロファイリングする価値があるかもしれません。

非整数要素（タプル）にはheapqを使用できます

from heapq import *

heap = []
data = [(10,"ten"), (3,"three"), (5,"five"), (7,"seven"), (9, "nine"), (2,"two")]
for item in data:
    heappush(heap, item)
sorted = []
while heap:
    sorted.append(heappop(heap))
print sorted
data.sort()
print data == sorted

＆quot;ソースを表示＆quot; heapqページのリンク？優先キューとして（int、char）タプルのリストを持つヒープを使用する方法の半分以下の例があります。

これは効率的で、文字列または任意のタイプの入力でも機能します-：）

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')

参照： http://docs.python.org/library/heapq.html

https：//pypi.pythonに優先キュー/フィボナッチヒープがあります。 .org / pypi / fibonacci-heap-mod

高速ではありません（delete-minの大きな定数c、O（c * logn））。ただし、find-min、insert、decrease-key、mergeはすべてO（1）-IOW、怠け者です。

CPythonで遅すぎる場合は、Pypy、Nuitka、またはCPython + Numbaを試してみてください：）

  

Charlie Martinが提案するように（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 を呼び出すとエラーが発生します（そうすべきです！）

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top