Эмпирическая оценка алгоритмов на Python
Ниже представлен перевод главы из книги Python Algorithms: Mastering Basic Algorithms in the Python Language (Expert's Voice in Open Source).
В этой книге описывается проектирование алгоритмов (и тесно связанный с ним анализ алгоритмов). Но в разработке есть также и другой немаловажный процесс, жизненно необходимый при создании крупных реальных проектов, это — оптимизация алгоритмов. С точки зрения такого разделения, проектирование алгоритма можно рассматривать как способ достижения заданного асимптотического времени работы (с помощью разработки эффективного алгоритма), а оптимизацию — как процесс уменьшения скрытых временных затрат при сохранении асимптотической сложности алгоритма.
Хотя я могу дать несколько советов по алгоритмам проектирования в Python, может быть трудно предсказать, какие именно хитрости и хаки дадут вам лучшую производительность в конкретной задаче, над которой вы работаете, или для вашего оборудования или версии Python. (Это именно тот вид особенностей асимптотики, который нужно избегать.) А в некоторых случаях такие хитрости и хаки могут вовсе не потребоваться, потому что ваша программа и так достаточно быстра. Самое простое, что вы можете делать в большинстве случаев, это просто пробовать и смотреть. Если у вас есть идея твика или хака, то просто опробуйте его! Реализуйте твик и запустите несколько тестов. Есть ли улучшения? А если твик делает ваш код менее читаемым, а прирост производительности мал, то подумайте — а стоит ли оно того?
Хотя есть теоретические аспекты так называемой экспериментальной алгоритмики (то есть, экспериментальной оценки алгоритмов и их реализации), которые выходят за рамки этой книги, я дам вам несколько практических советов, которые, могут быть очень полезны.
Совет 1: Если возможно, то не беспокойтесь об этом
Беспокойство об асимптоматической сложности может быть очень важным. Иногда это разница между решением и его отсутствием. Однако, постоянные составляющие времени исполнения часто совсем не критичны. Попробуйте простую реализацию алгоритма для начала, и убедитесь, что она работатет стабильно. Работает — не трогай.
Совет 2: Для измерения времени выполнения используйте timeit
timeit это модуль предназначенный для измерения времени исполнения. Хотя для получения действительно надежных данных вам потребуется выполнить кучу работы, для практических целей timeit вполне сгодится. Например:
timeit можно использовать прямо из командной строки, например:
Существует одна вещь, с которой вы должны быть осторожны при использовании timeit: побочные эффекты, которые будут влиять на повторное исполнение timeit. Функция timeit будет запускать ваш код несколько раз, чтобы увеличить точность, и если прошлые запуски влияют на последующие, то вы окажетесь в затруднительном положении. Например, если вы измеряете скорость выполнения чего-то типа mylist.sort(), список будет отсортирован только в первый раз. Во время остальных тысяч запусков список уже будет отсортированным и это даст нереально маленький результат.
Больше об этом модуле и как он работает можно найти в стандартной документации библиотеки.
Совет 3: Чтобы найти узкие места, используйте профайлер
Часто, для того чтобы понять, какие части программы требуют оптимизации, делаются разные догадки и предположения. Такие предположения нередко оказываются ошибочными. Вместо того, чтобы гадать, воспользуйтесь профайлером. В стандартной поставке Python идет
несколько профайлеров, но рекомендуется использовать cProfile. Им так же легко пользоваться, как timeit, но он дает больше подробной информации о том, на что тратится время при выполнении программы. Если основная функция вашей программы называется main, вы можете использовать профайлер следующим образом:
Такой код выведет на печать отчет о времени исполнения различных функций программы. Если в вашей системе нет модуля cProfile, используйте profile вместо него. Больше информации об этих модулях можно найти в документации. Если же вам не так интересны детали реализации, а просто нужно оценить поведение алгоритма на конкретном наборе данных, воспользуйтесь модулем trace из стандартной библиотеки. С его помощью можно посчитать, сколько раз будут выполнены то или иное выражение или вызов в программе.
Совет 4. Показывайте результаты графически
Визуализация может стать прекрасным способом, чтобы понять что к чему. Для исследования производительности часто применяются графики (например, для оценки связи количества данных и времени исполнения) и коробчатые диаграммы, отображающие распределение временных затрат при нескольких запусках. Примеры можно увидеть на рисунке. Отличная библиотека для построения графиков и диаграмм из Python — matplotlib (можно взять на http://matplotlib.sf.net).
Совет 5. Будьте внимательны в выводах, основанных на сравнении времени исполнения
Этот совет довольно расплывчатый, потому что существует много ловушек, в которые можно попасть, делая выводы о том, какой способ лучше, на основании сравнения времени исполнения. Во-первых, любая разница, которую вы видите, может определяться случайностью. Если вы используете специальные инструменты вроде timeit, риск такой ситуации меньше, потому что они повторяют измерение времени вычисления выражения несколько раз (или даже повторяют весь замер несколько раз, выбирая лучший результат). Таким образом, всегда будут случайные погрешности и если разница между двумя реализациями не превышает некоторой погрешности, нельзя сказать, что эти реализации различаются (хотя и то, что они одинаковы, тоже нельзя утверждать).
Проблема усложняется, если вы сравниваете больше двух реализаций. Количество пар для сравнения увеличивается пропорционально квадрату количества сравниваемых версий (это объяснено в гл. 3), сильно увеличивая вероятность того, что как минимум две из версий будут казаться слегка различными. (Это называется проблемой множественного сравнения). Существуют статистические решения этой проблемы, но самый простой способ — повторить эксперимент с двумя подозрительными версиями. Возможно, потребуется сделать это несколько раз. Они по-прежнему выглядят похожими?
Во-вторых, есть несколько моментов, на которые нужно обращать внимание при сравнении средних величин. Как минимум, вы должны сравнивать средние значения реального времени исполнения. Обычно, чтобы получить показательные числа при измерении производительности, время исполнения каждой программы нормируется делением на время исполнения какого-нибудь стандартного, простого алгоритма. Действительно, это
может быть полезным, но в ряде случаев сделает бессмысленными результаты замеров. Несколько полезных указаний на эту тему можно найти в статье «How not to lie with statistics: The correct way to summarize benchmark results» Fleming and Wallace. Также можно почитать Bast and Weber's «Don't compare averages,» или более новую статью Citron et al., «The harmonic or geometric mean: does it really matter?»
И в-третьих, возможно, ваши выводы нельзя обобщать. Подобные измерения на другом наборе входных данных и на другом железе могут дать другие результаты. Если кто-то будет пользоваться результаты ваших измерений, необходимо последовательно задокументировать, каким образом вы их получили.
Совет 6: Будьте осторожны, делая выводы об асимптотике из экспериментов
Если вы хотите что-то сказать окончательно об асимптотике алгоритма, то необходимо проанализировать ее, как описано ранее в этой главе. Эксперименты могут дать вам намеки, но они очевидно проводятся на конечных наборах данных, а асимптотика — это то, что происходит при сколь угодно больших размерах данных. С другой стороны, если только вы не работаете в академической сфере, цель асимптотического анализа — сделать какой-то вывод о поведении алгоритма, реализованного конкретным способом и запущенного на определенном наборе данных, а это значит, что измерения должны быть соответствующими.
Предположим, вы подозреваете, что алгоритм работает c квадратичной сложностью времени, но вы не в состоянии окончательно доказать это. Можете ли вы использовать эксперименты для поддержки вашего подозрения? Как уже говорилось, эксперименты (и проектирование алгоритмов) имеют дело в основном с постоянными коэффициентами, но есть способ. Основной проблемой является то, что ваша гипотеза на самом деле не проверяема (через эксперименты). Если вы утверждаете, что алгоритм имеет сложность О(n²), то данные не могут это ни подтвердить, ни опровергнуть. Тем не менее, если вы сделаете вашу гипотезу более конкретной, то она станет проверяемой. Вы могли бы, например, обоснованно на некоторых данных положить, что время работы программы никогда не будет превышать 0.24n²+0.1n+0.03 секунд в вашем окружении. Это проверяемые (или, более точно, опровергаемые) гипотезы. Если вы делаете много измерений, и так и не можете найти контр-примеры, значит ваша гипотеза в какой-то степени верна. Занятная деталь — это, косвенно, подтверждает квадратичную сложность алгоритма.
В этой книге описывается проектирование алгоритмов (и тесно связанный с ним анализ алгоритмов). Но в разработке есть также и другой немаловажный процесс, жизненно необходимый при создании крупных реальных проектов, это — оптимизация алгоритмов. С точки зрения такого разделения, проектирование алгоритма можно рассматривать как способ достижения заданного асимптотического времени работы (с помощью разработки эффективного алгоритма), а оптимизацию — как процесс уменьшения скрытых временных затрат при сохранении асимптотической сложности алгоритма.
Хотя я могу дать несколько советов по алгоритмам проектирования в Python, может быть трудно предсказать, какие именно хитрости и хаки дадут вам лучшую производительность в конкретной задаче, над которой вы работаете, или для вашего оборудования или версии Python. (Это именно тот вид особенностей асимптотики, который нужно избегать.) А в некоторых случаях такие хитрости и хаки могут вовсе не потребоваться, потому что ваша программа и так достаточно быстра. Самое простое, что вы можете делать в большинстве случаев, это просто пробовать и смотреть. Если у вас есть идея твика или хака, то просто опробуйте его! Реализуйте твик и запустите несколько тестов. Есть ли улучшения? А если твик делает ваш код менее читаемым, а прирост производительности мал, то подумайте — а стоит ли оно того?
Хотя есть теоретические аспекты так называемой экспериментальной алгоритмики (то есть, экспериментальной оценки алгоритмов и их реализации), которые выходят за рамки этой книги, я дам вам несколько практических советов, которые, могут быть очень полезны.
Совет 1: Если возможно, то не беспокойтесь об этом
Беспокойство об асимптоматической сложности может быть очень важным. Иногда это разница между решением и его отсутствием. Однако, постоянные составляющие времени исполнения часто совсем не критичны. Попробуйте простую реализацию алгоритма для начала, и убедитесь, что она работатет стабильно. Работает — не трогай.
Совет 2: Для измерения времени выполнения используйте timeit
timeit это модуль предназначенный для измерения времени исполнения. Хотя для получения действительно надежных данных вам потребуется выполнить кучу работы, для практических целей timeit вполне сгодится. Например:
>>> import timeit
>>> timeit.timeit("x = 2 + 2")
0.034976959228515625
>>> timeit.timeit("x = sum(range(10))")
0.92387008666992188
timeit можно использовать прямо из командной строки, например:
$ python -m timeit -s"import mymodule as m" "m.myfunction()"Существует одна вещь, с которой вы должны быть осторожны при использовании timeit: побочные эффекты, которые будут влиять на повторное исполнение timeit. Функция timeit будет запускать ваш код несколько раз, чтобы увеличить точность, и если прошлые запуски влияют на последующие, то вы окажетесь в затруднительном положении. Например, если вы измеряете скорость выполнения чего-то типа mylist.sort(), список будет отсортирован только в первый раз. Во время остальных тысяч запусков список уже будет отсортированным и это даст нереально маленький результат.
Больше об этом модуле и как он работает можно найти в стандартной документации библиотеки.
Совет 3: Чтобы найти узкие места, используйте профайлер
Часто, для того чтобы понять, какие части программы требуют оптимизации, делаются разные догадки и предположения. Такие предположения нередко оказываются ошибочными. Вместо того, чтобы гадать, воспользуйтесь профайлером. В стандартной поставке Python идет
несколько профайлеров, но рекомендуется использовать cProfile. Им так же легко пользоваться, как timeit, но он дает больше подробной информации о том, на что тратится время при выполнении программы. Если основная функция вашей программы называется main, вы можете использовать профайлер следующим образом:
import cProfile
cProfile.run('main()')
Такой код выведет на печать отчет о времени исполнения различных функций программы. Если в вашей системе нет модуля cProfile, используйте profile вместо него. Больше информации об этих модулях можно найти в документации. Если же вам не так интересны детали реализации, а просто нужно оценить поведение алгоритма на конкретном наборе данных, воспользуйтесь модулем trace из стандартной библиотеки. С его помощью можно посчитать, сколько раз будут выполнены то или иное выражение или вызов в программе.
Совет 4. Показывайте результаты графически
Визуализация может стать прекрасным способом, чтобы понять что к чему. Для исследования производительности часто применяются графики (например, для оценки связи количества данных и времени исполнения) и коробчатые диаграммы, отображающие распределение временных затрат при нескольких запусках. Примеры можно увидеть на рисунке. Отличная библиотека для построения графиков и диаграмм из Python — matplotlib (можно взять на http://matplotlib.sf.net).
Совет 5. Будьте внимательны в выводах, основанных на сравнении времени исполнения
Этот совет довольно расплывчатый, потому что существует много ловушек, в которые можно попасть, делая выводы о том, какой способ лучше, на основании сравнения времени исполнения. Во-первых, любая разница, которую вы видите, может определяться случайностью. Если вы используете специальные инструменты вроде timeit, риск такой ситуации меньше, потому что они повторяют измерение времени вычисления выражения несколько раз (или даже повторяют весь замер несколько раз, выбирая лучший результат). Таким образом, всегда будут случайные погрешности и если разница между двумя реализациями не превышает некоторой погрешности, нельзя сказать, что эти реализации различаются (хотя и то, что они одинаковы, тоже нельзя утверждать).
Проблема усложняется, если вы сравниваете больше двух реализаций. Количество пар для сравнения увеличивается пропорционально квадрату количества сравниваемых версий (это объяснено в гл. 3), сильно увеличивая вероятность того, что как минимум две из версий будут казаться слегка различными. (Это называется проблемой множественного сравнения). Существуют статистические решения этой проблемы, но самый простой способ — повторить эксперимент с двумя подозрительными версиями. Возможно, потребуется сделать это несколько раз. Они по-прежнему выглядят похожими?
Во-вторых, есть несколько моментов, на которые нужно обращать внимание при сравнении средних величин. Как минимум, вы должны сравнивать средние значения реального времени исполнения. Обычно, чтобы получить показательные числа при измерении производительности, время исполнения каждой программы нормируется делением на время исполнения какого-нибудь стандартного, простого алгоритма. Действительно, это
может быть полезным, но в ряде случаев сделает бессмысленными результаты замеров. Несколько полезных указаний на эту тему можно найти в статье «How not to lie with statistics: The correct way to summarize benchmark results» Fleming and Wallace. Также можно почитать Bast and Weber's «Don't compare averages,» или более новую статью Citron et al., «The harmonic or geometric mean: does it really matter?»
И в-третьих, возможно, ваши выводы нельзя обобщать. Подобные измерения на другом наборе входных данных и на другом железе могут дать другие результаты. Если кто-то будет пользоваться результаты ваших измерений, необходимо последовательно задокументировать, каким образом вы их получили.
Совет 6: Будьте осторожны, делая выводы об асимптотике из экспериментов
Если вы хотите что-то сказать окончательно об асимптотике алгоритма, то необходимо проанализировать ее, как описано ранее в этой главе. Эксперименты могут дать вам намеки, но они очевидно проводятся на конечных наборах данных, а асимптотика — это то, что происходит при сколь угодно больших размерах данных. С другой стороны, если только вы не работаете в академической сфере, цель асимптотического анализа — сделать какой-то вывод о поведении алгоритма, реализованного конкретным способом и запущенного на определенном наборе данных, а это значит, что измерения должны быть соответствующими.
Предположим, вы подозреваете, что алгоритм работает c квадратичной сложностью времени, но вы не в состоянии окончательно доказать это. Можете ли вы использовать эксперименты для поддержки вашего подозрения? Как уже говорилось, эксперименты (и проектирование алгоритмов) имеют дело в основном с постоянными коэффициентами, но есть способ. Основной проблемой является то, что ваша гипотеза на самом деле не проверяема (через эксперименты). Если вы утверждаете, что алгоритм имеет сложность О(n²), то данные не могут это ни подтвердить, ни опровергнуть. Тем не менее, если вы сделаете вашу гипотезу более конкретной, то она станет проверяемой. Вы могли бы, например, обоснованно на некоторых данных положить, что время работы программы никогда не будет превышать 0.24n²+0.1n+0.03 секунд в вашем окружении. Это проверяемые (или, более точно, опровергаемые) гипотезы. Если вы делаете много измерений, и так и не можете найти контр-примеры, значит ваша гипотеза в какой-то степени верна. Занятная деталь — это, косвенно, подтверждает квадратичную сложность алгоритма.
0 комментариев