Файл: Чистыйкод дляпродолжающи х.pdf

13
Измерение быстродействия
и анализ сложности алгоритмов
Для многих небольших программ быстродействие не так уж важно. Можно потратить целый час на написание сце- нария для автоматизации задачи, который выполняется за несколько секунд. Даже если выполнение потребует больше времени, то программа, вероятно, завершится к тому моменту, когда вы вернетесь к столу с чашкой кофе.
Иногда стоит озадачиться ускорением работы сценария. Но чтобы понять, приве- ли ли изменения к повышению быстродействия, необходимо знать, как измерить скорость программы. На помощь приходят модули Python timeit и cProfile
. Они не только изменяют время выполнения кода, но и строят профиль, показывающий, какие части кода уже выполняются быстро, а какие можно улучшить.
Кроме измерения скорости программ, из этой главы вы также узнаете, как оценивать теоретический рост времени выполнения с увеличением объема данных. В компью- терной науке эта зависимость называется нотацией «O-большое»
1
. Разработчик без подготовки в области традиционной теории обработки данных иногда осознаёт, что в его знаниях есть пробелы. Теория важна, но она не всегда имеет прямое отношение к реальной разработке. Я шучу (но только наполовину), что нотация «O-большое» составляет около 80% полезности моего диплома. В этой главе я кратко познакомлю вас с этой темой, имеющей значительное практическое применение.
1
В современных статьях и в интернете вы часто встретите термин Big-O-нотация.
В классических учебниках по алгоритмам принято использовать обозначение «нотация
“О-большое”». — Примеч. ред.

Модуль timeit
265
Модуль timeit
«Преждевременная оптимизация — корень всех зол» — популярное изречение в об- ласти разработки. (Его часто приписывают знаменитому ученому Дональду Кнуту, который отдает его авторство Тони Хоару. В свою очередь Тони Хоар описывает ситуацию с точностью до наоборот.) Преждевременная оптимизация (то есть оп- тимизация, выполняемая до того, как вы поймете, что же нужно оптимизировать) часто проявляется, когда программисты пытаются использовать хитроумные трюки для экономии памяти или написания более быстрого кода. Например, один из та- ких трюков основан на использовании алгоритма XOR, для того чтобы поменять местами два целых значения без использования третьей временной переменной:
>>> a, b = 42, 101 # Создание двух переменных.
>>> print(a, b)
42 101
>>> # Серия операций ^ XOR меняет значения местами:
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> print(a, b) # Значения поменялись местами.
101 42
Если вы не знакомы с алгоритмом XOR (использующим поразрядный оператор
^
), этот код выглядит загадочно. Недостаток хитроумных программных трюков заклю- чается в том, что они приводят к появлению сложного нечитаемого кода. Вспомните один из принципов «Дзен Python»: удобочитаемость важна.
Что еще хуже, ваш хитроумный трюк может оказаться не таким уж хитроумным.
Нельзя просто решить, что новый прием работает быстрее просто в силу своей затей- ливости или что старый код, который вы заменяете, изначально работал медленно.
Узнать это можно только одним способом — измерить и сравнить время выполне- ния (то есть время, необходимое для выполнения программы или некоторой части кода). Помните, что увеличение времени выполнения означает замедление работы программы: ей требуется больший срок для выполнения того же объема работы.
Модуль timeit стандартной библиотеки Python способен измерить скорость выполнения небольшого фрагмента кода. Для этого его запускают тысячи или миллионы раз, после чего вычисляют среднее время выполнения. Модуль timeit также временно отключает автоматический сборщик мусора для получения более стабильных данных времени выполнения. Если вы хотите вычислить время вы- полнения нескольких строк, передайте многострочный текст или разделите строки кода символами
;
:
>>> import timeit
>>> timeit.timeit('a, b = 42, 101; a = a ^ b; b = a ^ b; a = a ^ b')
0.1307766629999998

266
Глава 13.Измерение быстродействия и анализ сложности алгоритмов
>>> timeit.timeit("""a, b = 42, 101
... a = a ^ b
... b = a ^ b
... a = a ^ b""")
0.13515726800000039
На моем компьютере выполнение этого кода с алгоритмом XOR занимает прибли- зительно 1/10 секунды. Быстро это или нет? Сравним с кодом, меняющим местами два числа с использованием третьей временной переменной:
>>> import timeit
>>> timeit.timeit('a, b = 42, 101; temp = a; a = b; b = temp')
0.027540389999998638
Сюрприз! Код с третьей временной переменной не только лучше читается, но и работает почти вдвое быстрее! Возможно, трюк с XOR экономит несколько бай- тов памяти, но за счет скорости и удобочитаемости кода. Нет смысла жертвовать удобочитаемостью ради нескольких байтов памяти или наносекунд выполнения.
Еще лучше поменять местами две переменные, используя уловку множественного
присваивания, которая также требует меньше времени:
>>> timeit.timeit('a, b = 42, 101; a, b = b, a')
0.024489236000007963
Этот вариант не только читается лучше остальных, но и работает быстрее всего.
И мы знаем это не умозрительно, а потому что провели объективное измерение.
Функция timeit.timeit()
также может получить второй строкой аргумент с под- готовительным кодом, который выполняется только один раз перед выполнением кода первой строки. Также можно изменить количество испытаний по умолчанию, передав целое число в ключевом аргументе number
. Например, следующий тест из- меряет, с какой скоростью модуль Python random генерирует 10 000 000 случайных чисел от 1 до 100. (На моей машине на это потребовалось около 10 секунд.)
>>> timeit.timeit('random.randint(1, 100)', 'import random', number=10000000)
10.020913950999784
По умолчанию код строки, переданной timeit.timeit()
, не может обращаться к переменным и функциям в остальном коде программы:
>>> import timeit
>>> spam = 'hello' # Определяем переменную spam.
>>> timeit.timeit('print(spam)', number=1) # Измеряем время выполнения вывода spam.
Traceback (most recent call last):
File "", line 1, in
File "C:\Users\Al\AppData\Local\Programs\Python\Python37\lib\timeit.py", line 232, in timeit return Timer(stmt, setup, timer, globals).timeit(number)

Профилировщик cProfile
267
File "C:\Users\Al\AppData\Local\Programs\Python\Python37\lib\timeit.py", line 176, in timeit timing = self.inner(it, self.timer)
File "", line 6, in inner
NameError: name 'spam' is not defined
Чтобы решить эту проблему, передадим функции возвращаемое значение globals()
в ключевом аргументе globals
:
>>> timeit.timeit('print(spam)', number=1, globals=globals())
hello
0.000994909999462834
Хорошее правило: сначала добейтесь того, чтобы ваш код работал, а потом зани- майтесь его ускорением. Сначала работоспособность, потом эффективность!
Профилировщик cProfile
Хотя модуль timeit полезен для хронометража небольших фрагментов кода, модуль cProfile более эффективен для анализа целых функций или программ. Процесс профилирования систематически анализирует скорость вашей программы, затра- ты памяти и другие аспекты. Модуль cProfile
— профилировщик Python, то есть программа, измеряющая время выполнения программы, а также строящая профиль времени выполнения отдельных вызовов функций программы. Эта информация предоставляет намного более детализированные результаты хронометража вашего кода.
Чтобы воспользоваться профилировщиком cProfile
, передайте код, для которого хотите провести измерения, при вызове cProfile.run()
. Следующий пример по- казывает, как cProfiler измеряет и выводит время выполнения короткой функции, суммирующей все числа от 1 до 1 000 000:
import time, cProfile def addUpNumbers():
total = 0
for i in range(1, 1000001):
total += i cProfile.run('addUpNumbers()')
Результат выполнения этой программы выглядит примерно так:
4 function calls in 0.064 seconds
Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.064 0.064 :1()
1 0.064 0.064 0.064 0.064 test1.py:2(addUpNumbers)

268
Глава 13.Измерение быстродействия и анализ сложности алгоритмов
1 0.000 0.000 0.064 0.064 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.
Profiler' objects}
Каждая строка представляет некоторую функцию и время, требуемое для выпол- нения этой функции. Столбцы выходных данных cProfile.run()
:
ncalls
— количество вызовов функции;
tottime
— общее время, требуемое для выполнения функции, не считая времени в подфункциях;
percall
— общее время, разделенное на количество вызовов;
cumtime
— накопленное время для выполнения функции и ее подфункций;
percall
— общее время, деленное на количество вызовов;
filename:lineno(function)
— файл, в котором определяется функция, и но- мер строки.
Например, загрузите файлы rsaCipher.py и al_sweigart_pubkey.txt на https://
nostarch.com/crackingcodes/. Программа RSA Cipher была представлена в книге
Cracking Codes with Python (издательство No Starch Press, 2018)
1
. Введите сле- дующий фрагмент в интерактивной оболочке, чтобы профилировать функцию encryptAndWriteToFile()
. Эта функция шифрует сообщение из 300 000 символов, созданное выражением 'abc'
*
100000
:
>>> import cProfile, rsaCipher
>>> cProfile.run("rsaCipher.encryptAndWriteToFile('encrypted_file.txt', 'al_sweigart_pubkey.
txt', 'abc'*100000)")
11749 function calls in 28.900 seconds
Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 28.900 28.900 :1()
2 0.000 0.000 0.000 0.000 _bootlocale.py:11(getpreferredencoding)
--snip--
1 0.017 0.017 28.900 28.900 rsaCipher.py:104(encryptAndWriteToFile)
1 0.248 0.248 0.249 0.249 rsaCipher.py:36(getBlocksFromText)
1 0.006 0.006 28.873 28.873 rsaCipher.py:70(encryptMessage)
1 0.000 0.000 0.000 0.000 rsaCipher.py:94(readKeyFile)
--snip--
2347 0.000 0.000 0.000 0.000 {built-in method builtins.len}
2344 0.000 0.000 0.000 0.000 {built-in method builtins.min}
2344 28.617 0.012 28.617 0.012 {built-in method builtins.pow}
2 0.001 0.000 0.001 0.000 {built-in method io.open}
1
Свейгарт Эл. Криптография и взлом шифров на Python.

Анализ алгоритмов с использованием нотации «O-большое»
269 4688 0.001 0.000 0.001 0.000 {method 'append' of 'list' objects}
--snip--
Мы видим, что выполнение кода, переданного cProfile.run()
, заняло 28,9 секунды.
Обратите внимание на функции с наибольшим общим временем; в данном случае на работу встроенной функции Python pow()
потребовалось 28,617 секунды. Это почти все время выполнения кода! Изменить этот фрагмент нельзя (он является частью реализации Python), но можно ли изменить наш код, чтобы он в меньшей степени зависел от этой функции?
В данном случае ответ «нет», потому что программа rsaCipher.py уже неплохо оп- тимизирована. Даже при этом профилирование кода дало нам информацию о том, что главным узким местом является функция pow()
. А значит, нет смысла пытаться улучшить, скажем, функцию readKeyFile()
(выполнение которой занимает так мало времени, что cProfile сообщает, что ее время выполнения равно
0
).
Эта идея отражена в законе Амдала — формуле, которая вычисляет, насколько ускорится выполнение программы при улучшении одного из ее фрагментов. Со- гласно этой формуле ускорение всей операции равно
1
/
((1 —
p)
+
(p
/
s))
, где s
— ускорение компонента, а p
— доля этого компонента в общем времени вы- полнения программы. Таким образом, если увеличить вдвое скорость фрагмента, требующего 90% от общего времени выполнения программы, общее ускорение составит 1/((1 – 0,9) + (0,9/2)) = 1,818, или 82%. Это лучше, чем, скажем, утроение скорости элемента, который занимает всего 25% от общего времени выполнения; в этом случае общее ускорение составит 1 / ((1 – 0,25) + (0,25/2)) = 1,143, или 14%.
Заучивать эту формулу не нужно. Просто запомните, что удвоение скорости самых медленных или длинных частей вашего кода более продуктивно, чем удвоение скорости уже быстрых или коротких частей. Этот вывод подтверждается здравым смыслом: 10-процентная скидка на изделие дорогого модного дома лучше 10-про- центной скидки на пару дешевой обуви.
Анализ алгоритмов с использованием нотации
«O-большое»
Нотация «О-большое» — метод анализа алгоритмов, описывающий масштабиро- вание времени выполнения кода. Код классифицируется по нескольким порядкам сложности, каждый из которых в общем виде показывает, насколько увеличится время выполнения кода при возрастании объема выполняемой работы. Разработчик
Python Нед Бэтчелдер (Ned Batchelder) описывает нотацию «О-большое» как метод анализа, который определяет «насколько замедлится код с ростом объема данных»; этой теме был посвящен его доклад на конференции PyCon 2018, доступный на
https://youtu.be/duvZ-2UK0fc/.

270
Глава 13.Измерение быстродействия и анализ сложности алгоритмов
Представьте следующую ситуацию: имеется объем работы, на выполнение которой уходит час. Если объем работы увеличится вдвое, сколько времени потребуется в этом случае? Кто-то скажет, что вдвое больше, но на самом деле ответ зависит от выполняемой работы. Если на чтение короткой книги уходит час, то на чтение двух коротких книг потребуется около двух часов. Но если вы выстраиваете по алфавиту 500 книг в час, то расстановка по алфавиту 1000 книг займет больше двух часов, потому что вам придется найти правильное место для каждой книги в значительно большем наборе книг. С другой стороны, если вы просто проверяете, пуста ли книжная полка, то совершенно неважно, сколько книг стоит на полке — 0,
10 или 1000. Ответ будет понятен с первого взгляда. Время выполнения остается приблизительно постоянным независимо от количества книг. И хотя некоторые люди могут быстрее или медленнее справляться с чтением или алфавитной рас- становкой книг, общая картина остается неизменной.
Нотация «O-большое» описывает эту картину. Алгоритм может выполняться на быстром или медленном компьютере, но нотация «O-большое» все равно может использоваться для описания быстродействия алгоритма в целом независимо от того, на каком оборудовании этот алгоритм выполняется. В нотации «О-большое» не используются конкретные единицы для описания времени выполнения ал- горитма (секунды, такты процессора и т. д.), потому что эти показатели будут изменяться на разных компьютерах или при использовании разных языков про- граммирования.

Порядки нотации «О-большое»
271
Чтобы использовать нотацию «О-большое», не обязательно понимать точный мате- матический смысл таких терминов, как «логарифмическое» или «полиномиальное».
Все порядки я более подробно опишу в следующем разделе, а пока ограничусь простым обозначением.
O(1) и O(log n) — быстрые алгоритмы.
O(n) и O(n log n) — неплохие алгоритмы.
O(n
2
), O(2
n
) и O(n!) — медленные алгоритмы.
Конечно, можно найти и контрпримеры, но в общем случае эту классифи- кацию можно считать хорошей. Здесь перечислены не все порядки нотации
«О-большое», а только самые распространенные. Рассмотрим примеры задач для каждого из них.
Книжная полка как метафора порядков «О-большое»
В следующих примерах нотации «О-большое» я продолжу использовать метафору с книжной полкой. В описаниях n обозначает количество книг на полке, а порядок
«О-большое» описывает, как растет время выполнения различных операций с уве- личением количества книг.
O(1), постоянное время
Если вы проверяете, пуста ли книжная полка, это операция с постоянным време- нем. Неважно, сколько книг на полке; вы с первого взгляда определите, есть ли на ней книги. Их количество может изменяться, но время выполнения останется постоянным, потому что, если вы видите на полке хотя бы одну книгу, дальше можно не проверять. Значение n не влияет на скорость выполнения задачи, по- этому n не входит в обозначение O(1). Также постоянное время иногда записы- вается в виде O(c).
O(log n), логарифмическое время
Логарифм является операцией, обратной по отношению к возведению в степень; результат 2 4
, или 2
× 2 × 2 × 2, равен 16, тогда как логарифм log
2
(16) (читается
«логарифм 16 по основанию 2») равен 4. В программировании часто предполага- ется, что логарифм вычисляется по основанию 2, поэтому мы используем O(log n) вместо O(log
2
n).
Поиск на полке книги, если они упорядочены по алфавиту, является операцией с логарифмическим временем. Сначала вы проверяете книгу в середине полки.
Если это та книга, которую вы искали, поиск завершен. В противном случае можно