Python: оценка времени и памяти программы

Программа, быстро работающая на десяти элементах, может оказаться непригодной для большого файла. До запуска полезно оценить, сколько раз она обращается к данным и что хранит одновременно. Такая оценка объясняет рост затрат, но не предсказывает точное время в секундах на любом компьютере.

Размер данных и число действий

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

Запись O(n) обозначает линейную верхнюю оценку. Если для каждого элемента просматриваются все остальные, получается порядка n^2 действий — квадратичная оценка O(n^2).

a = [2, 5, 8]
checks = 0
for x in a:
    for y in a:
        checks += 1
print(checks)

Результат равен 9. Для шести элементов было бы 36: удвоение длины увеличивает число пар в четыре раза. В строке из десяти миллионов символов перебор всех начал вместе со всеми концами требует порядка 10^{14} сочетаний. Короткая запись такого перебора не делает его коротким вычислением.

Стоимость скрывается внутри команды

Одна строка кода может просматривать целую последовательность. Вызовы sum(a) и max(a) проходят список. Если неизменный максимум нужен при каждой проверке соседней пары, его вычисляют один раз до цикла и сохраняют. Повторный вызов внутри цикла превратил бы два линейных прохода в квадратичную работу.

При работе с обычными строками Python срез переменной длины тоже требует внимания: создание длинного фрагмента и подсчёт в нём всех пар на каждом шаге повторяют уже сделанную работу. В программе №24 используется двухсимвольный срез s[r-1:r+1], поэтому его размер не растёт вместе с окном. Длина окна получается арифметически через r-l+1.

Два вложенных цикла не всегда означают квадрат

В программе окна внешний for передвигает правую границу, внутренний while — левую. Левая граница не возвращается к нулю при каждом новом конце. За весь запуск обе границы проходят строку не более одного раза каждая. Поэтому суммарное число их сдвигов не превышает примерно 2n, хотя циклы вложены.

Для списка записей сортировка в худшем случае требует порядка n\log n сравнений. Последующий один проход обычно не меняет общую оценку. Но вычисляемый ключ может быть дорогим: сортировка по готовому числу отличается от ключа, который каждый раз анализирует большой текст.

Что занимает память

Нужно различать входные данные и дополнительное хранилище. Строка из файла занимает память, растущую с её длиной. Несколько счётчиков поверх неё дают постоянное количество дополнительных переменных. Список всех найденных фрагментов, напротив, растёт вместе с количеством сохранённых результатов и их длиной.

Вызов sorted(a) создаёт новый список: прежний и новый некоторое время существуют одновременно. Метод a.sort() изменяет исходный список, но это не означает полного отсутствия временной памяти внутри сортировки. Оценивать следует одновременно существующие данные, а не только число имён переменных.

Измерение и проверка

Замеры дополняют оценку: один и тот же способ запуска сравнивается на разных размерах входа, отдельно от печати тысяч промежуточных строк. Для коротких фрагментов подходит стандартный модуль timeit, повторяющий измерение. Результат зависит от оборудования, версии Python и самих данных; единого обещания «столько-то операций в секунду» нет.

Сначала проверяется правильность на маленьком примере, затем рост затрат. Какие действия повторяются без необходимости и какая граница движется только вперёд? Ответы объясняют, почему программа окна обрабатывает большой файл без перебора всех фрагментов.