Une file d'attente prioritaire générique pour Python

Question

Je dois utiliser une file d'attente prioritaire dans mon code Python. En cherchant quelque chose d'efficacité, je suis tombé sur heapq . Cela a l'air bien, mais ne semble être spécifié que pour les entiers. Je suppose que cela fonctionne avec tous les objets ayant des opérateurs de comparaison, mais cela ne précise pas de quels opérateurs de comparaison il a besoin.

En outre, heapq semble être implémenté en Python, donc ce n'est pas rapide.

Êtes-vous au courant d'implémentations rapides pour les files d'attente prioritaires en Python? De manière optimale, j'aimerais que la file d'attente soit générique (c'est-à-dire qu'elle fonctionne bien pour tout objet avec un opérateur de comparaison spécifié).

Merci d'avance

Mise à jour:

Comparaison dans heapq , je peux utiliser un (priorité, objet) comme le suggère Charlie Martin ou simplement mettre en œuvre __ cmp __ pour mon objet.

Je cherche toujours quelque chose de plus rapide que heapq .

Answer 1

Vous pouvez utiliser Queue.PriorityQueue .

Rappelez-vous que Python n'est pas fortement typé, vous pouvez donc sauvegarder ce que vous voulez: créez simplement un tuple de (priorité, chose) et vous êtes défini.

Answer 2

J'ai fini par implémenter un wrapper pour heapq , en ajoutant un dict pour maintenir les éléments de la file d'attente uniques. Le résultat devrait être assez efficace pour tous les opérateurs:

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

Lorsque vous utilisez une file d'attente prioritaire, une touche de réduction est une opération indispensable pour de nombreux algorithmes (Algorithme de Dijkstra, A *, OPTICS), je me demande pourquoi la file d'attente prioritaire intégrée de Python ne la prend pas en charge. Aucune des autres réponses n'offre une solution prenant en charge cette fonctionnalité.

Une file d'attente prioritaire prenant également en charge l'opération de réduction de clé est la cette mise en œuvre par Daniel Stutzbach a parfaitement fonctionné pour moi. avec 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

Je ne l'ai pas utilisé, mais vous pouvez essayer PyHeap . C'est écrit en C alors espérons que c'est assez rapide pour vous.

Êtes-vous certain que heapq / PriorityQueue ne sera pas assez rapide? Cela vaut peut-être la peine de commencer par l’un d’eux, puis de faire un profil pour voir si c’est vraiment votre performance.

Answer 5

Vous pouvez utiliser heapq pour des éléments non entiers (tuples)

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

Avez-vous consulté le " Afficher la source " lien sur la page heapq? Voici un exemple un peu moins de la moitié de l'utilisation d'un segment de mémoire avec une liste de tuples (int, char) comme file d'attente prioritaire.

Answer 7

Ceci est efficace et fonctionne aussi pour les chaînes ou tout type d'entrée -:)

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

Référence: http://docs.python.org/library/heapq.html

Answer 8

J'ai un segment de file d'attente prioritaire / fibonacci à l'adresse https: //pypi.python. .org / pypi / fibonacci-heap-mod

Ce n'est pas rapide (grande constante c sur delete-min, qui est O (c * logn)). Mais trouver-min, insérer, diminuer-touche et fusionner sont tous O (1) - IOW, c'est paresseux.

S'il est trop lent sur CPython, vous pouvez essayer Pypy, Nuitka ou même CPython + Numba:)

Answer 9

  

Je peux soit utiliser un (priorité, objet) comme le suggère Charlie Martin, ou simplement mettre en œuvre __ cmp __ pour mon objet.

Si vous souhaitez que les objets insérés soient hiérarchisés par une règle spécifique, j'ai trouvé très utile d'écrire une simple sous-classe de PriorityQueue qui accepte une fonction de clé. Vous n’aurez pas à insérer (priorité, objet) manuellement et vous aurez l’impression que la manipulation est plus naturelle.

Démonstration du comportement souhaité :

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

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

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

Évidemment, appeler put liera (et devrait!) une erreur si vous essayez d'insérer un objet que votre fonction de clé ne peut pas traiter.