Оптимизация: стеки в виде деревьев кортежей Python

Одной из замечательных особенностей обертывания объектов в классы является возможность изменения базовой реализации без нарушения работы остальной части программы. Например, в будущем можно выполнить оптимизацию с минимальным воздействием — интерфейс сохранится неизменным, даже если изменится внутреннее устройство. Существуют разные способы реализации стеков, обладающих различной эффективностью. До сих пор для обмена данными с нашими стеками использовались операции получения среза и конкатенации. Это довольно неэффективно: обе операции создают копии заключенного в оболочку объекта списка. Для больших стеков такой способ будет отнимать много времени.

Одним из способов добиться ускорения является полное изменение базовой структуры данных. Например, помещаемые на стек объекты можно хранить в двоичном дереве кортежей: каждый элемент можно записать как пару (object, tree), где object — это элемент, помещенный на стек, а tree — это либо другой кортеж, определяющий остальной стек, либо None для обозначения пустого стека. Стек элементов [1,2,3,4] внутренне будет храниться как дерево кортежей (1,(2,(3,(4,None)))).

Такое представление, основанное на кортежах, аналогично понятию списков в семействе языков Lisp: объект слева — это car (голова списка), а остальная часть дерева справа — это cdr (остальная часть списка). Так как при помещении элемента в стек или снятии со стека мы добавляем или удаляем только верхний кортеж, использование такой структуры позволяет избежать копирования всего стека. Для больших стеков преимущество может оказаться весьма существенным. Эти идеи реализованы в следующем классе, представленном в примере 18.4.

Пример 18.4. PP4E\Dstruct\Basic\stack3.py

"оптимизация за счет использования дерева кортежей"

class Stack:

def __init__(self, start=[]): # инициализируется любой последоват.

self.stack = None # даже другими (быстрыми) стеками

for i in range(-len(start), 0):

self.push(start[-i — 1]) # втолкнуть в обратном порядке

def push(self, node): # дерево растет ‘вверх/влево’

self.stack = node, self.stack # новый корневой кортеж: (node, tree)

def pop(self):

node, self.stack = self.stack # удалить корневой кортеж

return node # TypeError, если пустой

def empty(self):

return not self.stack # ‘None’?

def __len__(self): # для операций: len, not

len, tree = 0, self.stack while tree:

len, tree = len+1, tree[1] # обойти правые поддеревья return len

def __getitem__(self, index): # для операций: x[i], in, for

len, tree = 0, self.stack while len < index and tree: # обход/подсчет узлов

len, tree = len+1, tree[1] if tree:

return tree[0] # IndexError, при выходе за границы

else:

raise IndexError() # остановка для ‘in’ и ‘for’

def __repr__(self):

return ‘[FastStack:’ + repr(self.stack) + ‘]’

Метод __getitem__ этого класса обрабатывает операции обращения по индексу, проверки in и итерации в цикле for, как и прежде (в случае отсутствия метода __iter__), но в этой версии нужно выполнить обход дерева, чтобы найти узел по индексу. Обратите внимание, что это не подкласс первоначального класса Stack. Так как здесь почти все операции реализованы иначе, от наследования пользы мало. Но клиенты, использующие только общие для обоих классов операции, могут использовать их взаимозаменяемым образом — чтобы перейти на другую реализацию, нужно лишь импортировать класс стека из другого модуля. Ниже приводится листинг сеанса использования этой версии стека — если придерживаться только операций проталкивания, выталкивания, индексирования и итераций, эта версия, по существу, неотличима от первоначальной:

> >> from stack3 import Stack

> >> x = Stack()

> >> y = Stack()

> >> for c in ‘spam’: x.push(c)

…

>>> for i in range(3): y.push(i)

…

>>> x

[FastStack:(‘m’, (‘a’, (‘p’, (‘s’, None))))]

>>> y

[FastStack:(2, (1, (0, None)))]

>>> len(x), x[2], x[-1]