проверка членства в heapq и замена - PullRequest
Новая
       43

проверка членства в heapq и замена

1 голос
/ 19 января 2020

Для примера из официального heapq: 

>>> heap = []
>>> data = [(1, 'J'), (4, 'N'), (3, 'H'), (2, 'O')]
>>> for item in data:
...     heappush(heap, item)
...
>>> while heap:
...     print(heappop(heap)[1])
J
O
H
N

Я хочу дополнительно реализовать эффективный selected_pu sh такой, чтобы

  1. селективный_pu sh ((1, «M»)) эквивалентно heappu sh, поскольку «M» отсутствует в куче
  2. селективный_pu sh ((3.5, «N»)) эквивалентно куче [2] = (3.5 , 'N'); heapify (heap), так как 3.5 <4 </li>
  3. селективный_pu sh ((4.5, 'N')) ничего не делает, так как 4.5> 4

Следующая реализация объясняет цель, но медленно : 

def selective_push(heap,s):
   NotFound=True
   for i in range(len(heap)): #linear search
        if heap[i][1]==s[1]:
            if s[0]<heap[i][0]:
                 heap[i]=s      #replacement
                 heapify(heap)
            NotFound=False
            break
    if NotFound:
       heappush(heap,s)

Я думаю, что это медленно из-за линейного поиска, который разрушает сложность log (n) heapq.push. Коэффициент замещения низкий, но линейный поиск всегда выполняется.

1 Ответ

1 голос
/ 20 января 2020

Документы heapq содержат пример того, как изменить приоритет существующих элементов. (В примере также используется count, чтобы гарантировать, что элементы с одинаковым приоритетом возвращаются в том же порядке, в котором они были добавлены: поскольку вы не упомянули об этом как требование, я упростил код, удалив эту часть. ) Я также добавил логику c, которую вы упомянули, касающуюся замены существующих элементов.

По сути, она сводится к ведению словаря (entry_finder) для быстрого поиска элементов и маркировки элементы как удаленные, не удаляя их сразу из кучи, и пропуская отмеченные элементы при извлечении из кучи. 

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task

def add_task(task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        old_priority, _ = entry_finder[task]
        if priority < old_priority:
            # new priority is lower, so replace
            remove_task(task)
        else:
            # new priority is same or higher, so ignore
            return
    entry = [priority, 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, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

Некоторые примечания:

  • heappush эффективен, потому что может предполагать, что список, к которому вы добавляете, уже упорядочен как куча; heapify должен проверять все элементы каждый раз, когда он называется

  • На самом деле удаление элементов, а не просто удаление их - это быстро, но это означает, что если вы сбрасываете много приоритетов тогда некоторое хранилище эффективно тратится впустую; будет ли это подходить, будет зависеть от вашего варианта использования

  • вам потребуется создать аналогичные оболочки для любых других heapq функций, которые вы хотите использовать, так как вам всегда нужно убедиться, что справочный словарь entry_finder хранится в синхронизации c с данными в heapq

...