Создание очереди приоритетов с использованием кучи в Python - PullRequest
Новая
       21

Создание очереди приоритетов с использованием кучи в Python

0 голосов
/ 05 октября 2018

Я новичок в Python, так что извините за глупые ошибки ... Я пытаюсь создать приоритетную очередь, используя кучу в python (2.7.15), и мой код явно не работает. 

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

def push(pq,task,priority=0):
    'Add a new task'
    count = count+1
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def update(pq,task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = count+1
    entry = [priority, count, 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(pq):
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

def IsEmpty(pq):
    if not pq:
    print("List is empty")

Это то, что я сделал, большинство из них взяты здесь: https://docs.python.org/2/library/heapq.html. Моя проблема, когда я пытаюсь запустить его на Python Interprenter, я получаю это: 

>>> pq=[]
>>> pq.push("task1",1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute 'push'

МойВопрос в том, что я могу сделать, чтобы избежать этой ошибки, и если мой код имеет какие-либо недостатки, которые, возможно, могут вызвать дальнейшие ошибки?

Ответы [ 2 ]

0 голосов
/ 06 октября 2018

Как вы определили функцию push, вам нужно передать список, представляющий очередь, в качестве первого аргумента:

Вместо 

pq = []
pq.push("task1", 1)

до 

pq = []
push(pq, "task1", 1)
0 голосов
/ 06 октября 2018

Вы создаете класс в "объектно-ориентированном C" -стиле, который включает передачу контекста объекта в функцию, например, do_something(instance, arg).Это возможно, но не является естественным для Python, который поддерживает классы и ключевое слово с именем self, которое представляет экземпляр объекта, позволяя написать instance.do_something(arg), как вы делали, когда вызывали свою функцию push.

При таком подходе класс инкапсулирует все данные о состоянии, которые вы в настоящее время имеете в глобальной области видимости: 

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

Даже так, как написано в стиле "C"программа не имеет состояния экземпляра вне этих глобальных переменных;вам понадобится какая-то структура, чтобы хранить эти переменные вместе и передавать их в функции, или использовать ключевое слово global для каждой переменной внутри каждой из ваших функций, что не очень хорошее решение с точки зрения безопасности состояния, возможности повторного использования,понятность или любая другая метрика проектирования.

Вот пример программы, реорганизованной в класс: 

from heapq import heappush, heappop


class PQ:
    def __init__(self):
        self.pq = []
        self.entry_finder = {}
        self.REMOVED = '<removed-task>'
        self.count = 0

    def push(self, task, priority=0):
        '''Add a new task
        '''
        self.count += 1
        entry = [priority, self.count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def update(self, task, priority=0):
        '''Add a new task or update the priority of an existing task
        '''
        if task in self.entry_finder:
            self.remove_task(task)

        self.count += 1
        entry = [priority, self.count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        '''Mark an existing task as REMOVED.  Raise KeyError if not found.
        '''
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop(self):
        '''Remove and return the lowest priority task. Raise KeyError if empty.
        '''
        while self.pq:
            priority, count, task = heappop(self.pq)

            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task

        raise KeyError('pop from an empty priority queue')

    def empty(self):
        return len(self.pq) == 0

Сделав это, теперь вы можете импортировать класс в ваш интерпретатор (убедитесь, чтоИсходный код находится в той же папке, pq.py), создайте экземпляр класса и начните использовать его: 

>>> from pq import PQ
>>> pq = PQ()
>>> pq.push(1, 20)
>>> pq.push(2, 30)
>>> pq.push(3, 10)
>>> while not pq.empty(): print pq.pop()
...
3
1
2
>>>

Еще одна распространенная практика - добавить тестирование прямо в файл класса с помощью if __name__ == '__main__':условно: 

if __name__ == '__main__':
    pq = PQ()
    pq.push(1, 20)
    pq.push(2, 30)
    pq.push(3, 10)

    while not pq.empty():
        print pq.pop()

Это можно запустить на терминале с помощью python pq.py.

Попробуйте!

...