Eine generische Prioritätswarteschlange für Python

Question

Ich brauche eine Prioritätswarteschlange in meinem Python-Code zu verwenden. Suchen Sie nach etwas effizienter, kam ich auf heapq . Es sieht gut aus, scheint aber nur für ganze Zahlen angegeben werden. Ich nehme an, es mit allen Objekten arbeitet, die Vergleichsoperatoren haben, aber es ist nicht festgelegt, welche Vergleichsoperatoren die es braucht.

Außerdem heapq scheint in Python implementiert werden, so dass es nicht schnell.

Haben Sie Kenntnis von irgendwelchen schnellen Implementierungen für Prioritätswarteschlangen in Python? Optimalerweise würde ich die Warteschlange wie generisch zu sein (das heißt gut für jedes Objekt mit einem angegebenen Vergleichsoperator).

Vielen Dank im Voraus

Update:

Re Vergleich in heapq, kann ich entweder einen (priority, object) als Charlie Martin schlägt vor, oder einfach nur __cmp__ für mein Objekt implementieren.

Ich bin noch auf der Suche nach etwas schneller als heapq.

Answer 1

Sie können mit Queue.PriorityQueue .

Daran erinnern, dass Python ist nicht stark typisiert, so dass Sie alles speichern, die Sie mögen. Nur ein Tupel von (priority, thing) machen und Sie setzen

Answer 2

beendete ich einen Wrapper für heapq Umsetzung up, ein dict Zugabe für die Warteschlange der Elemente einzigartig zu halten. Das Ergebnis sollte für alle Betreiber sehr effizient sein:

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)

Answer 3

Wenn Sie eine Prioritätswarteschlange verwenden, verringern-Taste ist ein Must-Have Betrieb für viele Algorithmen (Dijkstra-Algorithmus, A *, OPTIK), frage ich mich, warum Python eingebaute in Prioritätswarteschlange nicht unterstützt. Keiner der anderen Antworten liefert eine Lösung, die diese Funktionalität unterstützt.

Eine Prioritätswarteschlange, die auch Abnahme-Tasten-Bedienung unterstützt diese Implementierung von Daniel Stutzbach perfekt für mich gearbeitet mit 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

Answer 4

Ich habe es nicht benutzt, aber man könnte versuchen, PyHeap . Es ist in C geschrieben, so hoffentlich ist es schnell genug für Sie.

Sind Sie positive heapq / Priorityqueue nicht schnell genug sein wird? Es könnte mit einem von ihnen geht wert sein, zu starten und dann Profilierung, um zu sehen, ob es wirklich Ihre Leistung bottlneck ist.

Answer 5

Sie können heapq für nicht ganzzahlige Elemente verwenden (Tupel)

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

Answer 6

Haben schauen Sie auf der „Quelltext anzeigen“ -Link auf dem heapq Seite? Es ist ein Beispiel etwas weniger als halb nach unten von einem Haufen mit einer Liste von (int, char) Tupeln als Prioritätswarteschlange verwendet wird.

Answer 7

Das ist effizient und arbeitet für Strings oder jede Art Eingang als auch -:)

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

Hinweis: http://docs.python.org/library/heapq.html

Answer 8

Ich habe eine Prioritätswarteschlange / Fibonacci Haufen bekam unter https: //pypi.python .org / pypi / Fibonacci-Heap-mod

Es ist nicht schnell (großer Konstante c auf Lösch-min, die O (c * logn ist)). Aber find-min, einfügen, verringern-Taste und verschmelzen alle O (1) -. IOW, es ist faul

Wenn es auf CPython zu langsam ist, können Sie versuchen, PyPy, Nuitka oder sogar CPython + Numba:)

Answer 9

  

Ich kann entweder eine (priority, object) verwenden, wie Charlie Martin schlägt vor, oder einfach nur __cmp__ für mein Objekt implementieren.

Wenn Sie einfügten Objekte wollen von einer bestimmten Regel priorisiert werden, fand ich es sehr hilfreich, eine einfache Unterklasse von PriorityQueue zu schreiben, die eine Schlüsselfunktion übernimmt. Sie werden nicht (priority, object) Tupeln manuell einfügen müssen und die Handhabung fühlt sich natürlicher.

Demo des gewünschten Verhaltens :

>>> 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-Code

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-Code

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]

Offensichtlich Aufruf put (und soll!) Einen Fehler auslösen, wenn Sie versuchen, ein Objekt, das Ihre Schlüsselfunktion nicht verarbeiten kann einzufügen.