Оптимизация: непосредственная модификация списка в памяти Python

В предыдущем разделе мы пытались повысить скорость выполнения операций проталкивания в стек и выталкивания со стека, применив иную организацию данных, однако скорость работы стека можно также повысить, вернувшись к объекту списка Python и воспользовавшись его изменяемостью. Поскольку списки могут изменяться непосредственно в памяти, их можно модифицировать быстрее, чем во всех предыдущих примерах. Операции непосредственной модификации списков, такие как append, могут приводить к осложнениям, когда к списку обращаются из нескольких мест. Но так как список внутри объекта стека не предназначается для прямого доступа, то здесь, вероятно, мы защищены.

Модуль, представленный в примере 18.5, демонстрирует один из способов реализации стека с непосредственными изменениями в памяти.

Для простоты некоторые методы перегрузки операторов опущены. Новый метод pop, используемый здесь, эквивалентен доступу по индексу и удалению элемента со смещением -1 (здесь вершина находится в конце списка). По сравнению с непосредственным использованием встроенных списков, этот класс имеет более низкую производительность, что обусловлено дополнительными вызовами методов, но он поддерживает дальнейшее усовершенствование, инкапсулируя операции со стеком.

Пример 18.5. PP4E\Dstruct\Basic\stack4.py

" оптимизация за счет непосредственного изменения списка в памяти"

class error(Exception): pass # при импортировании: локальное исключение

class Stack:

def __init__(self, start=[]): # self — объект экземпляра self.stack = [] # start — любая последовательность: stack…

for x in start: self.push(x)

def push(self, obj): # методы: подобно модулю + self

self.stack.append(obj) # вершина в конце списка

def pop(self):

if not self.stack: raise error(‘underflow’)

return self.stack.pop() # подобно извлечению и удалению stack[-1]

def top(self):

if not self.stack: raise error(‘underflow’)

return self.stack[-1]

def empty(self): return not self.stack # instance.empty()

def __len__(self): return len(self.stack) # len(instance), not instance

def __getitem__(self, offset):

return self.stack[offset] # instance[offset], in, for

def __repr__(self):

return ‘[Stack:%s]’ % self.stack

Эта версия работает, как оригинал в модуле stack2, — просто замените stack2 на stack4 в предыдущем примере интерактивного сеанса, и вы получите представление о его работе. Единственное заметное отличие в том, что элементы стека выводятся в обратном порядке (то есть вершиной стека является конец списка):

>>> from stack4 import Stack

>>> x = Stack()

>>> x.push(‘spam’)

>>> x.push(123)

>>> x

[Stack:[‘spam’, 123]]

>>>

>>> y = Stack()

>>> y.push(3.1415)

>>> y.push(x.pop())

>>> x, y

([Stack:[‘spam’]], [Stack:[3.1415, 123]])