Una cola de prioridad genérica para Python

Question

Necesito usar una cola de prioridad en mi código de Python. Buscando algo eficiente, encontré heapq . Se ve bien, pero parece estar especificado solo para enteros. Supongo que funciona con cualquier objeto que tenga operadores de comparación, pero no especifica qué operadores de comparación necesita.

Además, heapq parece implementarse en Python, por lo que no es rápido.

¿Conoce alguna implementación rápida para colas de prioridad en Python? De manera óptima, me gustaría que la cola fuera genérica (es decir, funciona bien para cualquier objeto con un operador de comparación específico).

Gracias de antemano

Actualización :

En comparación con heapq , puedo usar un (prioridad, objeto) como sugiere Charlie Martin, o simplemente implementar __cmp__ para mi objeto.

Todavía estoy buscando algo más rápido que heapq .

Answer 1

Puede usar Queue.PriorityQueue .

Recuerda que Python no está fuertemente tipado, así que puedes guardar lo que quieras: solo haz una tupla de (prioridad, cosa) y listo.

Answer 2

Acabé de implementar un contenedor para heapq , agregando un dictado para mantener los elementos de la cola únicos. El resultado debería ser bastante eficiente para todos los operadores:

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

Cuando se utiliza una cola de prioridad, la tecla de disminución es una operación obligatoria para muchos algoritmos (el algoritmo de Dijkstra, A *, OPTICS), me pregunto por qué la cola de prioridad incorporada de Python no lo admite. Ninguna de las otras respuestas proporciona una solución que admita esta funcionalidad.

Una cola de prioridad que también admite la operación de reducción de teclas es esta implementación de Daniel Stutzbach funcionó perfectamente para mí con 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

No lo he usado, pero puedes probar PyHeap . Está escrito en C, así que espero que sea lo suficientemente rápido para ti.

¿Eres positivo heapq / PriorityQueue no será lo suficientemente rápido? Puede que valga la pena ir con uno de ellos para comenzar, y luego hacer un perfil para ver si realmente es su rendimiento.

Answer 5

Puede usar heapq para elementos no enteros (tuplas)

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

¿Miraste la " Mostrar fuente " enlace en la página heapq? Hay un ejemplo un poco menos que a mitad de camino de usar un montón con una lista de tuplas (int, char) como una cola de prioridad.

Answer 7

Esto es eficiente y también funciona con cadenas o cualquier tipo de entrada - :)

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

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

Answer 8

Tengo una cola de prioridad / pila de fibonacci en https: //pypi.python .org / pypi / fibonacci-heap-mod

No es rápido (gran constante c en delete-min, que es O (c * logn)). Pero encontrar-min, insertar, disminuir tecla y fusionar son todos O (1): IOW, es perezoso.

Si es demasiado lento con CPython, puedes probar Pypy, Nuitka o incluso CPython + Numba :)

Answer 9

  

Puedo usar un (prioridad, objeto) como sugiere Charlie Martin, o simplemente implementar __cmp__ para mi objeto.

Si quiere que los objetos insertados sean priorizados por una regla específica, encontré muy útil escribir una subclase simple de PriorityQueue que acepta una función de tecla. No tendrá que insertar las tuplas (prioridad, objeto) manualmente y el manejo se sentirá más natural.

Demostración del comportamiento deseado :

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

Código 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]

Código 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]

Obviamente, llamar a put (y debería!) generará un error si intenta insertar un objeto que su función clave no puede procesar.