Ponowne priorytetyzowanie kolejki priorytetowej (efektywny sposób)

Question

Poszukuję bardziej efektywnego sposobu priorytetyzacji elementów w kolejce priorytetowej. Mam (dość naiwny) priorytet kolejki realizacji na podstawie heapq. Odpowiednie części są jak:

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) 

i tutaj jest prosta ko-rutyna po prostu wykazać cechy reprioritize w moim rzeczywistym aplikacji.

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) 

Z badań

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 

produkujące:

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 

Teraz moje pytanie brzmi, czy istnieją jakichkolwiek danych struktury, która będzie uniknąć połączeń do heapify(.), gdy repriorizating kolejkę priorytetową ? Jestem tutaj gotowy do wymiany pamięci na szybkość, ale powinno być możliwe zaimplementowanie jej w czystym Pythonie (oczywiście z dużo lepszymi synchronizacjami niż moja naiwna implementacja).

Aktualizacja:
Aby umożliwić Ci zrozumieć bardziej od konkretnego przypadku, pozwala przypuszczać, że żadne elementy są dodawane do kolejki po początkowym (partia) popycha, a następnie każdy fetch (pop) z kolejki będzie generowanie liczby repriorizations przybliżeniu jak schematu:

• 0 * n, rzadko
• 0,05 * n, typowo
• n, rzadko

gdzie n jest aktualna liczba items w kolejce. W związku z tym w dowolnej rundzie jest mniej lub więcej tylko względnie niewiele przedmiotów do zmiany kolejności. Mam więc nadzieję, że mogłaby istnieć struktura danych, która byłaby w stanie wykorzystać ten wzorzec iw związku z tym przewyższać koszt przeprowadzania obowiązkowej heapify(.) w każdej rundzie (w celu spełnienia niezmiennego sterty).

Aktualizacja 2:
Jak dotąd wydaje się, że podejście heapify(.) jest dość wydajna (relatywnie) rzeczywiście. Wszystkie alternatywy, które udało mi się wymyślić, muszą wykorzystać heappush(.) i wydaje się droższe, niż początkowo przypuszczałem. (W każdym razie, jeśli stan emisji pozostaje taki, jestem zmuszony znaleźć lepsze rozwiązanie z dziedziny python).

Answer 1

Ponieważ nowa funkcja priorytetyzacji może nie mieć żadnego związku z poprzednią, musisz zapłacić koszt, aby uzyskać nowe zamówienie (i jest to minimum O (n) tylko po to, aby znaleźć minimalny element w nowym zamówieniu). Jeśli masz małą, ustaloną liczbę funkcji priorytetyzacji i często przełączasz się między nimi, możesz mieć korzyść z utrzymywania oddzielnej sterty dla każdej funkcji (chociaż nie z heapq, ponieważ nie obsługuje to taniej lokalizacji i usuwania oraz obiektów z środek sterty).