18. Очереди¶
Эта глава рассказывает о двух абстрактных типах данных: очередь и очередь с приоритетом. Все мы видели очередь клиентов, ожидающих обслуживания. Чаще всего, первый клиент в очереди будет обслужен следующим. Хотя бывают и исключения. В аэропортах, пассажиры рейсов, которые вскоре отправляются, иногда обслуживаются вне очереди. В супермаркете вежливый покупатель может пропустить другого, с одной-двумя покупками, перед собой.
Правило, определяющее, кто будет обслужен следующим, называется политикой очереди. Простейшая политика очереди называется FIFO, от английского first in — first out, что означает: первым пришел — первым вышел. А наиболее обобщенной политикой является приоритетное обслуживание, при которой каждому клиенту назначается приоритет, и клиент с наивысшим приоритетом обслуживается первым, независимо от времени его прихода. Мы назвали такую политику обобщенной потому, что приоритет может назначаться, исходя из чего угодно: времени отправления рейсов, количества покупок у покупателя, важности конкретного клиента.
Абстрактные типы данных очередь и очередь с приоритетом имеют один и тот же набор операций. Различие состоит в семантике операций; очередь использует политику FIFO; очередь с приоритетом, как следует из названия типа, использует политику приоритетного обслуживания.
18.2. Абстрактная очередь¶
Абстрактный тип данных очередь имеет следующие операции:
__init__ Создать новую пустую очередь. insert Добавить в очередь новый элемент. remove Удалить и вернуть элемент из очереди. Возвращаемый элемент — тот, который был добавлен первым. is_empty Проверить, пуста ли очередь.
18.3. Связная очередь¶
Первая из реализаций очереди, которую мы рассмотрим, будет связная очередь, построенная из связанных объектов Node . Вот определение класса Queue (англ.: очередь):
class Queue: def __init__(self): self.length = 0 self.head = None def is_empty(self): return (self.length == 0) def insert(self, cargo): node = Node(cargo) node.next = None if self.head == None: # if list is empty the new node goes first self.head = node else: # find the last node in the list last = self.head while last.next: last = last.next # append the new node last.next = node self.length += 1 def remove(self): if self.length == 0: return cargo = self.head.cargo self.head = self.head.next self.length -= 1 return cargo
Методы is_empty и remove достаточно просты и похожи на подобные методы класса LinkedList . Метод insert существенно новый и чуть более сложный.
Нам нужно добавить новый элемент в конец списка. Если очередь пуста, мы просто присваиваем атрибуту head ссылку на новый узел.
В противном случае, мы проходим по всему списку до последнего узла, и присоединяем новый узел в конец списка. Мы определяем, что достигли последнего узла, когда значением атрибута next является None .
Для правильно построенного объекта Queue существуют два инварианта. Переменная length должна содержать количество узлов в очереди, и последний узел должен иметь атрибут next со значением None . Убедитесь, что метод insert сохраняет оба инварианта.
18.4. Показатели производительности¶
Обычно, когда мы вызываем метод, нас не заботят детали его реализации. Но есть одна вещь, которую нам хотелось бы знать — показатели производительности метода. Каково время выполнения метода, и как это время изменяется при изменении числа элементов в коллекции?
Вначале посмотрим на метод remove . В этом методе нет ни циклов, ни вызовов функций, значит, время выполнения этого метода всегда одно и то же. Такие операции называются операциями с постоянным временем выполнения. В действительности, этот метод выполняется немного быстрее, когда список пуст, поскольку в этом случае выполняется только условное предложение; но эта разница незначительна.
Поведение метода insert разительно отличается. В общем случае необходимо пройти весь список для того, чтобы найти последний элемент.
Время прохода списка пропорционально длине списка. Поскольку время выполнения есть линейная функция от размера списка, такие операции называются операциями с линейным временем выполнения. По сравнению с операциями с постоянным временем выполнения, такие операции сильно проигрывают.
18.5. Улучшенная связная очередь¶
Хочется иметь реализацию очереди, которая выполняла бы все операции за постоянное время. Один из способов добиться этого — изменить класс Queue так, чтобы он поддерживал ссылку как на первый, так и на последний узел в списке!
Класс ImprovedQueue выглядит так:
class ImprovedQueue: def __init__(self): self.length = 0 self.head = None self.last = None def is_empty(self): return (self.length == 0)
Все, что мы пока изменили в коде, — добавили атрибут last . Он используется в методах insert и remove :
class ImprovedQueue: . def insert(self, cargo): node = Node(cargo) node.next = None if self.length == 0: # if list is empty, the new node is head and last self.head = self.last = node else: # find the last node last = self.last # append the new node last.next = node self.last = node self.length += 1
Поскольку атрибут last указывает на последний узел, нам не нужно искать его. В результате, данный метод является методом с постоянным временем выполнения.
За скорость, однако, нужно платить. Придется добавить условное предложение в remove для того, чтобы присваивать last значение None в случае, когда удален последний узел:
class ImprovedQueue: . def remove(self): if self.length == 0: return cargo = self.head.cargo self.head = self.head.next self.length -= 1 if self.length == 0: self.last = None return cargo
Эта реализация очереди несколько сложнее, чем реализация Queue . Также стало сложнее убедиться в ее корректности. Но преимущество состоит в том, что теперь и insert и remove являются операциями с постоянным временем выполнения.
18.6. Очередь с приоритетом¶
Абстрактный тип данных очередь с приоритетом имеет тот же интерфейс, что и очередь, но семантика отличается. Приведем интерфейс:
__init__ Создать новую пустую очередь. insert Добавить в очередь новый элемент. remove Удалить и вернуть элемент из очереди. Возвращаемый элемент — тот, у которого наивысший приоритет. is_empty Проверить, пуста ли очередь.
Семантическое отличие состоит в том, что извлекаемый из очереди элемент не обязательно тот, который был добавлен в очередь первым. Это элемент, имеющий наивысший приоритет. Что такое приоритет, и как выполняется сравнение приоритетов, не определяется в интерфейсе. Мы также не станем определять этого в нашей реализации очереди с приоритетом! О приоритете будут “знать” только сами элементы, помещаемые в очередь.
Например, если элементы в очереди имеют имена, они могут извлекаться из очереди в алфавитном порядке. Если элементы содержат очки, набранные при игре в боулинг, можно извлекать их в порядке от наибольшего значения к наименьшему. Если элементы, стоящие в очереди, можно сравнивать друг с другом, значит, можно найти среди них элемент с наивысшим приоритетом и извлечь его.
Следующая реализация очереди с приоритетом хранит элементы очереди в списке Python.
class PriorityQueue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def insert(self, item): self.items.append(item)
Методы __init__ , is_empty и insert используют операции над списком. Единственный интересный метод remove :
class PriorityQueue: . def remove(self): maxi = 0 for i in range(1, len(self.items)): if self.items[i] > self.items[maxi]: maxi = i item = self.items[maxi] self.items[maxi:maxi+1] = [] return item
В начале каждой итерации maxi содержит индекс самого большого (с наивысшим приоритетом) элемента из рассмотренных до сих пор. Каждый раз в цикле программа сравнивает i -й элемент с элементом-чемпионом. Если i -й элемент оказывается больше, переменной maxi присваивается i .
Когда цикл for завершается, maxi содержит индекс элемента с наивысшим приоритетом. Этот элемент удаляется из списка и возвращается.
Протестируем нашу реализацию очереди с приоритетом:
>>> q = PriorityQueue() >>> q.insert(11) >>> q.insert(12) >>> q.insert(14) >>> q.insert(13) >>> while not q.is_empty(): print q.remove() 14 13 12 11
Если очередь содержит числа или строки, они будут извлекаться в числовом или алфавитном порядке, от наибольшего к наименьшему. Python может найти наибольшее целое число или строку потому, что он сравнивает числа и строки при помощи встроенных операторов сравнения.
Если же очередь содержит объекты пользовательских классов, то класс должен предоставить метод __cmp__ . Когда метод remove использует оператор > для сравнения двух элементов, Python вызывает __cmp__ для одного элемента, передавая другой в качестве параметра. Если метод __cmp__ работает корректно, очередь с приоритетом также будет работать корректно.
18.7. Класс Golfer ¶
В качестве примера объекта с необычным приоритетом, реализуем класс Golfer (англ.: игрок в гольф), который хранит имя игрока и набранные им очки. Как всегда, начнем с определения методов __init__ и __str__ :
class Golfer: def __init__(self, name, score): self.name = name self.score= score def __str__(self): return "%-16s: %d" % (self.name, self.score)
__str__ использует оператор форматирования для того, чтобы расположить имена и очки игроков в виде аккуратных столбцов.
Далее, определим метод __cmp__ , в котором наименьшее число очков означает наивысший приоритет. Как всегда, __cmp__ возвращает 1, если self больше other , -1, если self меньше other , и 0 в случае их равенства.
class Golfer: . def __cmp__(self, other): if self.score other.score: return 1 # less is more if self.score > other.score: return -1 return 0
Теперь мы готовы протестировать работу очереди с приоритетом с классом Golfer :
>>> tiger = Golfer("Tiger Woods", 61) >>> phil = Golfer("Phil Mickelson", 72) >>> hal = Golfer("Hal Sutton", 69) >>> >>> pq = PriorityQueue() >>> pq.insert(tiger) >>> pq.insert(phil) >>> pq.insert(hal) >>> while not pq.is_empty(): print pq.remove() Tiger Woods : 61 Hal Sutton : 69 Phil Mickelson : 72
18.8. Глоссарий¶
FIFO First In, First Out, или первым вошел — первым вышел, политика очереди, при которой элемент, первым добавленный в очередь, будет излечен первым. очередь Упорядоченный набор объектов, ожидающих обслуживания. очередь с приоритетом Очередь, в которой которой каждый элемент имеет приоритет, зависящий от внешних факторов (то есть, независимый от самой очереди). Первым извлекается из очереди элемент с наивысшим приоритетом. политика очереди Правило, определяющее, какой элемент очереди будет извлечен (обслужен) следующим. программа с линейным временем выполнения Программа, время выполнения которой есть линейная функция от размера структуры данных. программа с постоянным временем выполнения Программа, время выполнения которой не зависит от размера структуры данных. связная очередь Реализация очереди с использованием связного списка.
18.9. Упражнения¶
- Напишите реализацию очереди, используя список Python. Сравните производительность вашей реализации с реализацией ImprovedQueue для очередей различной длины.
- Напишите реализацию очереди с приоритетом, используя связный список. Поддерживайте список отсортированным, так, чтобы извлечение из списка было операцией с постоянным временем выполнения. Сравните производительность этой реализации с реализацией при помощи списка Python.
Просмотр
© Copyright 2009, 2012, Джеффри Элкнер, Аллен Б. Дауни, Крис Мейерс, Андрей Трофимов. При создании использован Sphinx 1.1.3.