Générique de la file d'attente de priorité pour Python

Question

J'ai besoin d'utiliser une file d'attente de priorité dans mon code Python. En regardant autour de quelque chose d'efficace, je suis tombé sur heapq. Il semble bien, mais semble être spécifié que pour les entiers. Je suppose que cela fonctionne avec tous les objets qui ont les opérateurs de comparaison, mais il ne précise pas ce que les opérateurs de comparaison dont il a besoin.

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

Êtes-vous au courant de toutes les implémentations rapides pour les files d'attente de priorité en Python ? Idéalement, je voudrais la file d'attente pour être générique (c'est à dire bien travailler pour n'importe quel objet avec un certain opérateur de comparaison).

Merci d'avance

Mise à jour:

Re comparaison en heapq, je peux soit utiliser un (priority, object) que Charlie Martin suggère, ou tout simplement mettre en oeuvre __cmp__ pour mon objet.

Je suis toujours à la recherche de quelque chose de plus rapide que d' heapq.

Answer 1

Euh, La File D'Attente.PriorityQueue ? Rappelons que Python n'est pas fortement typé, de sorte que vous pouvez enregistrer tout ce que vous voulez: il suffit de faire un n-uplet de (priorité,chose) et vous êtes fixés.

Answer 2

J'ai fini par mettre en place un wrapper pour heapq, l'ajout d'un dict pour le maintien de la file d'attente d'éléments 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.

            items:
                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. The item will be added only
            if it doesn't already exist in the queue.
        """
        if not (item in self.set):
            self.set[item] = True
            heapq.heappush(self.heap, item)

Answer 3

Comment savez-vous qu'il est trop lent? Avez-vous profilé-il encore? Aussi depuis la 2.4, il y a un C mise en œuvre de heapq dans la bibliothèque standard qui est utilisé.

Answer 4

Je ne l'ai pas utilisé, mais vous pouvez essayer de PyHeap. Il est écrit en C alors j'espère qu'il est assez rapide pour vous.

Êtes-vous positif heapq/PriorityQueue ne sera pas assez rapide? Il pourrait être intéressant d'aller avec l'un d'entre eux pour commencer, puis de profilage pour voir si il est vraiment de votre performance bottlneck.

Answer 5

Avez-vous regardé l' "Afficher la Source" lien sur la heapq page? Il y a un exemple un peu moins de la moitié de l'aide d'un segment de mémoire avec une liste de (int, char) n-uplets d'une file d'attente de priorité.