Iterieren über eine Priority-Queue, in Python?

Ich versuche zu implementieren, die Uniform-cost-Suche in python und dafür brauche ich eine priority-queue, die ich bin mit queue.py aus der standard-Bibliothek. Aber das Ende des Algorithmus überprüft, ob es irgendeinen Pfad mit höheren Kosten in der Warteschlange. Wie kann ich prüfen, ob es nicht einen beliebigen Wert in meiner Warteschlange, wenn es nicht durchsuchbar?

Dank

  • Ich würde empfehlen, das schreiben Ihrer eigenen Priorität-Warteschlange verwenden einfach eine einfache list und heapq. Es ist nicht so schlimm. Siehe die implementation notes in der heapq docs.
  • Das ist genau wie queue.PriorityQueue umgesetzt wird 🙂
InformationsquelleAutor Rodrigo Souza | 2014-09-13
  1. 6

    queue.PriorityQueue tatsächlich umgesetzt wird mit einem list, und die put/get Methoden verwenden heapq.heappush/heapq.heappop zur Aufrechterhaltung der Priorität der Reihenfolge in das list. Also, wenn Sie wollten, könnten Sie einfach Durchlaufen der internen Liste, die enthalten ist in der queue Attribut:

    >>> from queue import PriorityQueue
>>> q = PriorityQueue()
>>> q.put((5, "a"))
>>> q.put((3, "b"))
>>> q.put((25, "c"))
>>> q.put((2, "d"))
>>> print(q.queue)
[(2, 'd'), (3, 'b'), (25, 'c'), (5, 'a')]
    • Die erste Zeile sollte sein: from Queue import PriorityQueue. Hinweis die Hauptstadt F.
    • Ja, für Python 2. In Python 3.x, es ist ein Kleinbuchstabe q.
    • Als mein guter Freund T. Payne zeigte sich in einem seiner videos: <blink> ` try: import-queue als Queue-Ausnahme: import-Queue <\blink> Und du bist abgedeckt für beide
    InformationsquelleAutor dano
  2. 4

    Den PriorityQueue implementiert binary heap, die umgesetzt wird mit einem list (array) in python. Die zum Durchlaufen der Warteschlange müssen Sie wissen, die Regeln darüber, wo Kinder sind gespeichert in der Liste.

    Die Regeln, dass alle Knoten haben zwei Kinder, es sei denn, Sie sind der Letzte Knoten haben Kinder in welchem Fall Sie möglicherweise haben ein Kind, statt. Alle Knoten, die sich nach dem letzten Knoten die Kinder haben keine Kinder (duh).

    Die untergeordneten Knoten eines Knotens gespeichert werden, in Bezug auf die Knoten die eigene position in der Liste. Wo i ist der index der Knoten in die Liste ein dann sind es die Kinder sind gespeichert unter:

    • 2 * i + 1
    • 2 * i + 2

    Jedoch nur die Voraussetzung für einen heap ist, dass alle Knoten, die Kinder haben einen Wert, der größer als oder gleich des Knotens Wert (oder größer je nach Implementierung).

    Beispielsweise in der oben verlinkten wiki-Seite über binrary heap findest du Folgendes Bild. Das erste Element in der queue ist die Wurzel. Ganz offensichtlich ist. Das zweite Element ist die größere der root-Kinder. Das Dritte Element könnte entweder werden die verbleibenden Knoten des root-Knotens, oder eines der Kinder des zweiten Knotens in die Warteschlange. Das ist, das Dritte Element in der Warteschlange (25) hätte in der gleichen position entweder 19 oder 1.

    Iterieren über eine Priority-Queue, in Python?

    Damit die zum Durchlaufen der Warteschlange, die Sie benötigen, um zu halten verfolgen von alle der aktuell "sichtbaren" Knoten. Zum Beispiel:

    def iter_priority_queue(queue):

    if queue.empty():
        return

    q = queue.queue
    next_indices = [0]
    while next_indices:
        min_index = min(next_indices, key=q.__getitem__)
        yield q[min_index]
        next_indices.remove(mix_index)
        if 2 * min_index + 1 < len(q):
            next_indices.append(2 * min_index + 1)
        if 2 * min_index + 2 < len(q):
            next_indices.append(2 * min_index + 2)

    Ist die Methode monkey gepatcht auf queue.PriorityQueue wenn du bist Gefühl faul, aber ich möchte Sie ermutigen, um Ihre eigenen priority-queue-Klasse, die mit der heapq Modul wie die PriorityQueue kommt mit einer Menge von überschüssigen Funktionen (vor allem ist es thread-sicher, die fast sicher nicht brauchen). Es sollte angemerkt werden, dass die oben genannte Methode ist nicht thread-sicher. Wenn ein anderer thread ändert die Warteschlange, während es über die iteriert dann über die oben genannte Methode wird gestartet, woraus sich die falsche zahlen und wenn man Glück hat, kann es eine Ausnahme erzeugen.

    InformationsquelleAutor Dunes
  3. 1

    Es sei denn, Sie brauchen die thread-Sicherheit, die queue.queue gibt, wie es war vor allem gedacht als ein thread-sicherer job-Warteschlange und nicht als eine Allgemeine Warteschlange, könnten Sie besser dran mit einem Sammlungen.deque direkt, wie Sie sind durchsuchbar.

    • aber wie verwende ich es als eine PriorityQueue?
    InformationsquelleAutor Dan D.
Schreibe einen Kommentar