Estoy buscando una forma más eficiente de volver a priorizar elementos en una cola de prioridad. Tengo una implementación de cola de prioridad (bastante ingenua) basada en heapq
. Las partes pertinentes son como:Repriorización de la cola de prioridad (manera eficiente)
from heapq import heapify, heappop
class pq(object):
def __init__(self, init= None):
self.inner, self.item_f= [], {}
if not None is init:
self.inner= [[priority, item] for item, priority in enumerate(init)]
heapify(self.inner)
self.item_f= {pi[1]: pi for pi in self.inner}
def top_one(self):
if not len(self.inner): return None
priority, item= heappop(self.inner)
del self.item_f[item]
return item, priority
def re_prioritize(self, items, prioritizer= lambda x: x+ 1):
for item in items:
if not item in self.item_f: continue
entry= self.item_f[item]
entry[0]= prioritizer(entry[0])
heapify(self.inner)
Y aquí es un simple compañero de rutina para simplemente demostrar las características nuevas prioridades en mi aplicación real.
def fecther(priorities, prioritizer= lambda x: x+ 1):
q= pq(priorities)
for k in xrange(len(priorities)+ 1):
items= (yield k, q.top_one())
if not None is items:
q.re_prioritize(items, prioritizer)
Con las pruebas
if __name__ == '__main__':
def gen_tst(n= 3):
priorities= range(n)
priorities.reverse()
priorities= priorities+ range(n)
def tst():
result, f= range(2* n), fecther(priorities)
k, item_t= f.next()
while not None is item_t:
result[k]= item_t[0]
k, item_t= f.send(range(item_t[0]))
return result
return tst
producción:
In []: gen_tst()()
Out[]: [2, 3, 4, 5, 1, 0]
In []: t= gen_tst(123)
In []: %timeit t()
10 loops, best of 3: 26 ms per loop
Ahora, mi pregunta es, ¿existe ninguna estructura de datos que evite las llamadas a heapify(.)
, cuando repriorizating la cola de prioridad ? Estoy aquí dispuesto a cambiar la memoria por velocidad, pero debería ser posible implementarla en Python puro (obviamente con tiempos mucho mejores que mi implementación ingenua).
actualización:
el fin de que usted pueda entender más en el caso concreto, supongamos que no hay elementos se agregan a la cola después inicial (por lotes) empuja y luego cada fetch (pop) de la cola se generar número de repriorizations más o menos igual que este esquema:
- 0 *
n
, muy rara vez - 0,05 *
n
, típicamente n
, muy rara vez
donde n
es el número actual de items
en la cola. Por lo tanto, en cualquier ronda, hay más o menos pocos elementos relativos para volver a priorizar. Por lo tanto, espero que exista una estructura de datos que pueda explotar este patrón y, por lo tanto, supere el costo de hacer obligatorio heapify(.)
en cada ronda (para satisfacer el invariante de montón).
Actualización 2:
Hasta ahora parece que el enfoque heapify(.)
es bastante eficiente (en términos relativos) de hecho. Todas las alternativas que he podido descifrar necesitan utilizar heappush(.)
y parece ser más costoso de lo que originalmente anticipé. (De todos modos, si el estado de la cuestión sigue así, me veo obligado a encontrar una mejor solución fuera del dominio python
).
¿Hay algún conocimiento previo sobre los dos esquemas de prioridad? ¿Hay algún tipo de relación entre ellos? No puede asumir nada, entonces me temo que tendrá que llamar a 'heapify (.)' Para hacer el trabajo. –
@ André Caron: De hecho, puede haber varios "esquemas de prioridad".Sin embargo, están algo implícitos (enterrados en los datos) y esperaba mantener esto como una "caja negra". Gracias – eat