Une queue prioritaire générique pour Python

Je dois utiliser une queue prioritaire dans mon code Python. En cherchant quelque chose d’efficacité, je suis tombé sur heapq . Il semble bon, mais semble être spécifié uniquement pour les entiers. Je suppose que cela fonctionne avec tous les objects qui ont des opérateurs de comparaison, mais cela ne spécifie pas les opérateurs de comparaison dont il a besoin.

De plus, heapq semble être implémenté en Python, donc ce n’est pas rapide.

Avez-vous connaissance d’implémentations rapides pour les files d’attente prioritaires en Python? De manière optimale, j’aimerais que la queue soit générique (c.-à-d. Fonctionne bien pour n’importe quel object avec un opérateur de comparaison spécifié).

Merci d’avance

Mettre à jour:

En comparaison avec heapq , je peux soit utiliser (priority, object) comme le suggère Charlie Martin, ou simplement implémenter __cmp__ pour mon object.

Je cherche toujours quelque chose de plus rapide que heapq .

Um, Queue.PriorityQueue ? Rappelez-vous que Python n’est pas fortement typé, vous pouvez donc enregistrer tout ce que vous voulez: créez un tuple de (priorité, chose) et vous êtes défini.

J’ai fini par implémenter un wrapper pour heapq , en ajoutant un dict pour maintenir les éléments de la queue 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 (ie 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) 

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

Êtes-vous positif heapq / PriorityQueue ne sera pas assez rapide? Il peut être utile de commencer par l’un d’entre eux, puis de profiler pour voir si c’est vraiment votre performance.

Avez-vous regardé le lien “Afficher la source” sur la page heapq? Il y a un exemple un peu moins de la moitié de l’utilisation d’un tas avec une liste de tuples (int, char) en tant que queue prioritaire.