Я ищу более эффективный способ перераспределить элементы в очереди с приоритетами.У меня есть (довольно наивная) реализация очереди приоритетов на основе heapq.Соответствующие части выглядят так:
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)
А вот простая сопрограмма для демонстрации характеристик перераспределения в моем реальном приложении.
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)
С тестированием
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
производит:
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
Теперь, мой вопрос: существует ли какая-либо структура данных, которая могла бы избежать вызовов к heapify(.) при переориторизации очереди с приоритетами?Я здесь готов обменять память на скорость, но должна быть возможность реализовать ее на чистом Python (очевидно, с гораздо лучшими временами, чем моя наивная реализация).
Обновление :
Чтобы дать вам возможность лучше понять конкретный случай, давайте предположим, что никакие элементы не добавляются в очередь после начальных (пакетных) нажатий, а затем каждый выбор (извлечение) из очереди будет генерировать количество повторных преобразований, примерно как в этой схеме.:
- 0 *
n, очень редко - 0,05 *
n, обычно n, очень редко
где n - текущее число items в очереди.Таким образом, в любом раунде есть более или менее только относительно небольшое количество предметов для переориентации.Поэтому я надеюсь, что может существовать структура данных, которая сможет использовать этот шаблон и, следовательно, превзойти стоимость выполнения обязательных heapify(.) в каждом раунде (для удовлетворения инварианта кучи).
Обновление 2 :
Пока что кажется, что подход heapify(.) действительно весьма эффективен (условно говоря).Все альтернативы, которые я смог выяснить, должны использовать heappush(.), и это кажется более дорогим, чем я первоначально ожидал.(В любом случае, если состояние проблемы остается таким, я вынужден найти лучшее решение из области python).