|
очередью вы удаляете элемент, который был добавлен в нее
раньше всех (метод «первым пришел — первым ушел», или FIFO); однако
в случае со
стеком вы удаляете элемент, который был добавлен в него
позже всех (метод «последним пришел — первым ушел», или LIFO).
С точки зрения производительности предполагается, что надлежащая
реализация стека будет занимать O(1) времени на операции вставки
и удаления.
Стеки находят широкое применение в алгоритмах, например в синтакси-
ческом анализе языка и управлении рабочей памятью времени исполне-
ния («стек вызовов»). Короткий и красивый алгоритм с использованием
стека представлен поиском в глубину (DFS) на древовидной или графо-
вой структуре данных.
Python поставляется с несколькими реализациями стека, каждая из
которых имеет слегка отличающиеся характеристики. Сейчас мы их рас-
смотрим и сравним их характеристики.
186 Глава 5 • Общие структуры данных Python
list — простые встроенные стеки
Встроенный в Python тип
list
создает нормальную стековую структуру
данных, поскольку он поддерживает операции вталкивания и выталкива-
ния за амортизируемое O(1) время
1
.
На внутреннем уровне списки Python реализованы как динамические
массивы, а значит, при добавлении или удалении элементов им время от
времени нужно изменять пространство оперативной памяти для храня-
щихся в них элементов. Список выделяет избыточную резервную память,
с тем чтобы не каждая операция вталкивания и выталкивания требовала
изменения размера памяти, и, как результат, для этих операций вы полу-
чаете амортизируемую временную сложность O(1).
Недостаток же состоит в том, что это делает показатели их производитель-
ности менее надежными, чем стабильные вставки и удаления с временной
сложностью O(1), которые обеспечиваются реализацией на основе связ-
ного списка (такого, как
collections.deque
, см. ниже). С другой стороны,
списки реально обеспечивают быстрый (со временем O(1)) произвольный
доступ к элементам в стеке, и это может быть дополнительным преиму-
ществом.
Используя списки в качестве стеков, необходимо учитывать одно важное
предостережение относительно производительности.
Чтобы получить производительность с амортизируемым временем O(1)
для вставок и удалений, новые элементы должны добавляться в конец
списка методом
append()
и снова удалятся из конца методом
pop()
. Для
оптимальной производительности стеки на основе списков Python долж-
ны расти по направлению к более высоким индексам и сжиматься к более
низким.
Добавление и удаление элементов в начале списка намного медленнее
и занимает O(n) времени, поскольку существующие элементы должны
сдвигаться, чтобы создать место для нового элемента. Такого антишаблона
производительности следует избегать.
1
См. документацию Python «Использование списков в качестве стеков»:
https://docs .
python .org/3/tutorial/datastructures .html
5 .5 . Стеки (с дисциплиной доступа LIFO) 187
>>> s = []
>>> s.append('есть')
>>> s.append('спать')
>>> s.append('программировать')
>>> s
['есть', 'спать', 'программировать']
>>> s.pop()
'программировать'
>>> s.pop()
'спать'
>>> s.pop()
'есть'
>>> s.pop()
IndexError: "pop from empty list"
collections .deque — быстрые и надежные стеки
Класс
deque
реализует очередь с двусторонним доступом, которая под-
держивает добавление и удаление элементов с любого конца за O(1)
(неамортизируемое) время. Поскольку двусторонние очереди одинаково
хорошо поддерживают добавление и удаление элементов с любого конца,
они могут служить и в качестве очередей, и в качестве стеков
1
.
Объекты Python
deque
реализованы как двунаправленные связные спи-
ски, что дает им стабильную производительность для операций вставки
и удаления элементов, но при этом плохую O(n) производительность для
произвольного доступа к элементам в середине очереди
2
.
В целом двусторонняя очередь
collections.deque
– отличный выбор,
если вы ищете стековую структуру данных в стандартной библиотеке
Python, которая обладает характеристиками производительности, ана-
логичными реализации на основе связного списка.
1
См. документацию Python «collections.deque»:
https://docs .python .org/3 .6/library/collections .
html#collections .deque
2
См. CPython «_collectionsmodule.c»:
https://github .com/python/cpython/blob/master/Modules/_
collectionsmodule .c
188 Глава 5 • Общие структуры данных Python
>>> from collections import deque
>>> s = deque()
>>> s.append('есть')
>>> s.append('спать')
>>> s.append('программировать')
>>> s
deque(['есть', 'спать', 'программировать'])
>>> s.pop()
Do'stlaringiz bilan baham: |
