Объект стека, модифицируемый непосредственно в памяти, представленный в прошлом разделе, работает, вероятно, быстрее, чем первоначальная версия и версия на основе дерева кортежей, но единственный способ действительно выяснить, насколько быстрее, — это провести хронометраж альтернативных реализаций. Поскольку такая операция может потребоваться неоднократно, определим сначала общий модуль функций хронометража в Python. Встроенный модуль time в примере 18.6 предоставляет функцию clock, с помощью которой можно получить текущее время CPU в виде секунд, выраженных числом с плавающей точкой, а функция timer.test просто вызывает нужную функцию reps раз и возвращает количество истекших секунд, вычитая время конца из времени начала.
Пример 18.6. PP4E\Dstruct\Basic\timer.py
"универсальный инструмент хронометража"
def test(reps, func, *args): # или лучший из N? см. "Изучаем Python"
import time
start = time.clock() # текущее время CPU в секундах
for i in range(reps): # вызвать функцию reps раз
func(*args) # отбросить возвращаемое значение
return time.clock() — start # время конца — время начала
Существуют также другие способы хронометража, включая подход «лучший из N» и собственный модуль Python timeit, но для наших целей вполне достаточно будет и этого модуля. Если вам интересно познакомиться с более удачными решениями, обращайтесь к четвертому изданию книги «Изучаем Python», где приводятся более крупные примеры по этой теме, или поэкспериментируйте с собственными решениями. Далее, определим управляющий сценарий теста, как показано в примере 18.7. Он принимает три аргумента командной строки: количество операций проталкивания в стек, выталкивания со стека и обращения по индексу (будем менять эти аргументы для проверки разных ситуаций). При запуске в виде самостоятельного сценария он создает 200 экземпляров исходного и оптимизированного классов стека и выполняет заданное количество операций с каждым стеком. Операции проталкивания в стек и выталкивания со стека изменяют стек; при индексировании происходит только выборка значений из него.
Пример 18.7. PP4E\Dstruct\Basic\stacktime.py
"сравнение производительности альтернативных реализаций стека"
import stack2 # стек на основе списка: [x]+y
import stack3 # стек на основе дерева кортежей: (x,y)
import stack4 # стек, выполняющий модификацию списка в памяти: y.append(x) import timer # вспомогательная функция хронометража
rept = 200
from sys import argv
pushes, pops, items = (int(arg) for arg in argv[1:])
def stackops(stackClass):
x = stackClass(‘spam’) # создать объект стека
for i in range(pushes): x.push(i) # применить его методы for i in range(items): t = x[i] # 3.X: range — генератор
for i in range(pops): x.pop()
# или mod = __import__(n)
for mod in (stack2, stack3, stack4): # rept*(push+pop+ix) print(‘%s:’ % mod.__name__, end=’ ‘) print(timer.test(rept, stackops, getattr(mod, ‘Stack’)))
Использованная литература:
Марк Лутц — Программирование на Python, 4-е издание, II том, 2011
