Repriorización de la cola de prioridad (manera eficiente)

Question

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:

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

Answer 1

Dado que la nueva función de priorización puede no tener relación con la anterior, debe pagar el costo para obtener la nueva orden (y es como mínimo O (n) solo para encontrar el elemento mínimo en la nueva orden). Si tiene un número pequeño y fijo de funciones de priorización y cambia con frecuencia entre ellas, entonces puede beneficiarse manteniendo un montón separado para cada función (aunque no con heapq, porque no es económica para localizar y eliminar y objetar desde el en medio de un montón).