Скорость и память программы

Программа проверяет все пары чисел файла. На десяти числах она отвечает мгновенно, на ста тысячах — не дождаться. Код тот же, данные больше. Скорость программы определяется тем, как растёт число действий с ростом данных, а не тем, насколько коротко она записана.

Научимся оценивать этот рост для одного прохода, всех пар и деления пополам, узнаем цену знакомых операций и памяти и измерим время сами.

Временная сложность описывает, как растёт работа с размером входа. Размер входа обозначают n — например, число строк файла. Один проход по файлу делает около n действий, и это записывают O(n) — «порядка n». Все пары — около n² действий, O(n²). Это не секунды, а то, во сколько раз вырастет работа, если данных станет больше.

Порядки роста удобно сравнить на одном размере входа. Каждая клетка шкалы — в тысячу раз больше предыдущей:

Такой разрыв важнее любых сокращений записи: никакая короткая запись не превратит 10 миллиардов действий в 100 тысяч.

Число шагов считают по реальным границам циклов. Два вложенных цикла не всегда дают n². Если внутренний всегда делает 10 шагов, всего их 10n, то есть O(n). Если внутренний цикл идёт только по номерам после i, каждая пара проверяется один раз:

n = 1000steps = 0for i in range(n):    for j in range(i + 1, n):        steps += 1print(steps, n * (n - 1) // 2)

Откуда формула, видно на сетке всех пар: пары с i < j — треугольник над диагональю.

Если на каждом шаге число делится на 2, после k шагов оно уменьшается в 2 ** k раз. Поэтому до единицы нужно около log₂(n) шагов — столько раз n можно делить пополам:

n = 1_000_000steps = 0while n > 1:    n //= 2    steps += 1print(steps)

Миллион делится пополам до единицы всего 19 раз: 2¹⁹ ≈ 524 тысячи, 2²⁰ ≈ 1,05 миллиона. Запись 1_000_000 — то же число 1000000, подчёркивания только облегчают чтение.

Стоимость скрыта и внутри отдельных операций. Одна строка кода может пройти весь список. Ориентиры для знакомых операций:

Отсюда две частые ошибки. Срез a[i:i + k] в цикле каждый раз копирует до k элементов. Множество для проверок in строят один раз до цикла, а не внутри каждого запроса.

Память тоже растёт с данными, если их сохранять. Пространственная сложность описывает, сколько памяти нужно алгоритму. В уроке о файлах сумму и наибольшее считали двумя способами. Первый сохраняет все числа в список — память растёт с числом строк:

with open("numbers.txt", encoding="utf-8") as file:    numbers = [int(line) for line in file]print(sum(numbers), max(numbers))

Второй проходит файл один раз и хранит только total и best — два числа при любом размере файла:

total = 0best = Nonewith open("numbers.txt", encoding="utf-8") as file:    for line in file:        number = int(line)        total += number        if best is None or number > best:            best = numberprint(total, best)

Время у обоих O(n), а память — растущая и постоянная. Словарь частот занимает место по числу различных значений. Если в конце нужен sorted, все элементы всё равно придётся собрать. Рекурсия хранит незавершённые вызовы, кэш — вычисленные результаты; это тоже память.

Время измеряют разностью показаний часов, но сначала улучшают порядок роста. perf_counter() из модуля time возвращает показание часов в секундах. Само показание ничего не значит, важна разность до и после. Проверим таблицу на опыте: ищем отсутствующее число тысячу раз в списке из ста тысяч чисел и в множестве из тех же чисел.

from time import perf_counter numbers = list(range(100_000))as_set = set(numbers) start = perf_counter()for _ in range(1000):    found = -1 in numbersprint("список:", perf_counter() - start) start = perf_counter()for _ in range(1000):    found = -1 in as_setprint("множество:", perf_counter() - start)

Запусти у себя и сравни два числа. Множество окажется быстрее в тысячи раз: в списке каждый поиск проходит все сто тысяч чисел, в множестве — сразу смотрит на нужное место. Сами секунды зависят от компьютера и немного меняются от запуска к запуску, поэтому вывод здесь не показан.

Один запуск шумный: влияют другие программы на компьютере. Поэтому сначала улучшают порядок роста алгоритма, а секунды меряют, чтобы найти самое медленное место.