Практические способы замера скорости кода на Python для алгоритмов
Основные способы оценки времени выполнения алгоритмов
Измерение времени работы алгоритма необходимо для выбора наиболее эффективного решения. В Python существует несколько инструментов: от простого замера с помощью time до специализированного модуля timeit и профилировщиков. Каждый подход имеет свои цели и случаи использования.
Модуль timeit - стандартное средство для точных замеров
Модуль timeit предназначен для измерения времени выполнения небольших фрагментов кода. Он автоматически отключает сборщик мусора и выполняет код несколько раз, возвращая наилучшее или среднее время. Это наиболее эффективный способ получить точные результаты, особенно для коротких операций.
import timeit
t = timeit.timeit('sum(range(1000))', number=1000)
print(f'Время: {t:.6f} сек')
время алгоритма python (оценка времени алгоритма в python)
Время: 0.001234 сек (значение может отличаться)
Здесь number задаёт количество повторений. Чем больше повторений, тем точнее результат, но дольше измерение. timeit также позволяет замерять время выполнения функций, объявленных в коде, с помощью строкового выражения или callable.
Типичная ошибка: передача в timeit функции с аргументами без правильной настройки. Например, если функция требует аргументов, следует использовать строку с вызовом или передать callable в виде lambda. Также нужно помнить, что timeit не видит глобальные переменные, если они не указаны в параметре globals.
Решение: использовать аргумент globals=globals() или оборачивать вызов в lambda.
Как измерить время участка кода без использования timeit?
Модуль time предоставляет функции time() и perf_counter(). perf_counter() используется для замера коротких интервалов с максимально доступной точностью. Этот способ подходит для однократных замеров или когда нужно встроить таймер непосредственно в код.
import time
start = time.perf_counter()
result = sum(range(1000))
end = time.perf_counter()
print(f'Время: {end - start:.6f} сек')
Проблема: на точность могут влиять фоновые процессы, загрузка CPU, сборка мусора. Для коротких операций погрешность может превышать само время.
Решение: выполнять замер несколько раз и усреднять, либо перейти на timeit.
Как автоматически замерять время выполнения любой функции без дублирования кода?
Создание декоратора для замера времени - удобный способ добавить логирование времени к произвольным функциям. Декоратор возвращает обёртку, которая замеряет время выполнения и выводит результат.
import functools
import time
def timer(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
start = time.perf_counter()
result = func(*args, **kwargs)
end = time.perf_counter()
print(f'{func.__name__} выполнена за {end - start:.6f} сек')
return result
return wrapper
@timer
def compute():
return sum(range(1000))
compute()
compute выполнена за 0.000345 сек
Ошибка: декоратор может добавить накладные расходы из-за вызова обёртки. Для очень быстрых функций это искажает время. Также декоратор не позволяет настроить количество повторений.
Решение: для точных измерений использовать декоратор в паре с timeit внутри, либо применять только для относительно медленных функций.
Как узнать, какие части программы занимают больше всего времени?
Модуль cProfile позволяет провести профилирование - пошаговый замер времени выполнения каждой функции. Это нужно для оптимизации больших программ, где узкие места не очевидны.
import cProfile
import re
def search():
text = "Python" * 10000
re.search("th", text)
cProfile.run('search()')
4 function calls in 0.000 seconds
...
Результат показывает количество вызовов, общее и кумулятивное время. Для анализа можно использовать pstats для сортировки.
Сложность: профилировщик замедляет выполнение программы, что может исказить времена. Для высокоточных замеров отдельных функций он не подходит, но помогает найти узкие места.
Решение: использовать cProfile на этапе отладки, а для окончательных замеров применять timeit.
Как получить усреднённое время выполнения с учётом выбросов?
Модуль timeit уже предоставляет статистику, но можно также использовать его метод repeat, который возвращает список времен. Затем можно вычислить среднее, медиану или минимальное значение.
import timeit
times = timeit.repeat('sum(range(1000))', repeat=5, number=1000)
avg = sum(times) / len(times)
print(f'Среднее: {avg:.6f} сек, минимальное: {min(times):.6f} сек')
Среднее: 0.001456 сек, минимальное: 0.001234 сек
Проблема: при первом запуске может быть большее время из-за прогрева кэша и компиляции. Наилучшей практикой считается отбрасывание первого замера или использование минимального времени.
Решение: выполнять repeat с большим числом повторений и брать минимальное время как наиболее чистое от накладных расходов.
Расширенные примеры замера времени алгоритмов
Рассмотрим полный сценарий сравнения двух алгоритмов: линейного поиска и бинарного поиска в отсортированном списке. Оценим время выполнения для разных размеров входных данных.
import timeit
import random
n = 10000
data = list(range(n))
target = random.randint(0, n-1)
def linear_search(arr, x):
for i, val in enumerate(arr):
if val == x:
return i
return -1
def binary_search(arr, x):
lo, hi = 0, len(arr)-1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
lo = mid + 1
else:
hi = mid - 1
return -1
linear_time = timeit.timeit(lambda: linear_search(data, target), number=1000)
binary_time = timeit.timeit(lambda: binary_search(data, target), number=1000)
print(f'Линейный поиск (n={n}): {linear_time:.6f} сек за 1000 вызовов')
print(f'Бинарный поиск (n={n}): {binary_time:.6f} сек за 1000 вызовов')
print(f'Бинарный быстрее в {linear_time / binary_time:.2f} раз')
Линейный поиск (n=10000): 0.345678 сек за 1000 вызовов Бинарный поиск (n=10000): 0.001234 сек за 1000 вызовов Бинарный быстрее в 280.00 раз
Для более детального анализа полезно замерить время для нескольких значений n, чтобы увидеть зависимость сложности. Используем timeit.repeat и построим таблицу (вывод в консоль).
import timeit
sizes = [1000, 5000, 10000, 20000]
linear_times = []
binary_times = []
for n in sizes:
data = list(range(n))
target = n // 2
lt = timeit.repeat(lambda: linear_search(data, target), number=100, repeat=3)
bt = timeit.repeat(lambda: binary_search(data, target), number=100, repeat=3)
linear_times.append(min(lt))
binary_times.append(min(bt))
print(f'n={n:5d}: linear min={min(lt):.6f}, binary min={min(bt):.6f}')
n= 1000: linear min=0.034567, binary min=0.000123 n= 5000: linear min=0.178901, binary min=0.000134 n=10000: linear min=0.345678, binary min=0.000140 n=20000: linear min=0.689012, binary min=0.000145
Видно, что время линейного поиска растёт пропорционально n, а бинарного - остаётся практически постоянным (O(log n)).
Другой полезный приём - использование timeit.Timer для более тонкой настройки, например, с заданием контекста через setup.
import timeit
setup = "data = list(range(1000))"
code = "sum(data)"
t = timeit.Timer(code, setup=setup)
result = t.repeat(number=1000, repeat=5)
print(result)
Также можно замерять время выполнения небольших фрагментов непосредственно в IPython или Jupyter Notebook с помощью магической команды %timeit, которая автоматически использует модуль timeit с оптимальными параметрами.
# В Jupyter или IPython:
%timeit sum(range(1000))
1.23 µs ± 12 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Для проверки влияния сборщика мусора можно временно его отключить с помощью gc.disable() и потом включить, но timeit делает это автоматически в своих замерах.
В случае использования cProfile для более глубокого анализа можно сохранить результат в файл и открыть его в специальном визуализаторе, например, snakeviz.
import cProfile, pstats
profiler = cProfile.Profile()
profiler.enable()
result = sum([i**2 for i in range(10000)])
profiler.disable()
stats = pstats.Stats(profiler)
stats.sort_stats('cumtime')
stats.print_stats(10)
Эти расширенные примеры показывают, как на практике оценивать время работы алгоритмов и выбирать оптимальный вариант.