В стандартную библиотеку Python включены два модуля для профилирования: timeit и cProfile. Функция timeit.timeit() полезна для выполнения небольших фрагментов кода с целью сравнения времени их выполнения. Функция cProfile.run() компилирует подробный отчет по большим функциям и может выявить любые узкие места.
Важно измерять быстродействие вашего кода, а не делать предположения относительно него. Хитроумные трюки для ускорения работы программы на самом деле могут замедлить ее. Или есть вероятность, что вы потратите много времени на оптимизацию фрагмента, который будет незначительно влиять на скорость вашей программы. Закон Амдала отражает этот факт в математическом виде: формула описывает, как ускорение работы одного компонента влияет на ускорение программы в целом.
Пожалуй, из всех концепций теории вычислений именно нотация «О-большое» находит наибольшее практическое применение. Для ее понимания необходимы определенные знания математики, но концепция определения закономерности замедления кода с ростом объема данных позволяет описывать алгоритмы без длинных формул.
Известны семь основных порядков сложности нотации «О-большое». Низкие порядки: O(1), или постоянное время, описывает код, время выполнения которого не изменяется с увеличением размера данных n; O(log n), или логарифмическое время, описывает код, сложность которого увеличивается на один шаг при увеличении размера данных n вдвое; O(n), или линейное время, описывает код, который замедляется пропорционально росту размера данных n; O(n log n), или время n-log-n, описывает код, который работает немного медленнее O(n) — многие алгоритмы сортировки относятся к этому порядку. Более высокие порядки работают медленнее, потому что их время выполнения растет намного быстрее размера входных данных: O(n2), или полиномиальное время, описывает код, время выполнения которого растет в квадратичной зависимости от размера входных данных n; порядки O(2n), или экспоненциальное время, и O(n!), или факториальное время, встречаются не так часто — в основном там, где в вычислениях используются комбинации и перестановки соответственно.
Помните: хотя нотация «О-большое» является полезным аналитическим инструментом, она не заменит выполнения кода в профилировщике для выявления узких мест. Однако если вы будете понимать нотацию «О-большое» и закономерности замедления кода с ростом данных, это позволит избежать написания кода, который работает значительно медленнее, чем мог бы.
Кіру не тіркелу пікір қалдыру үшін