За счёт какого механизма добавление элементов в список Python обычно имеет амортизированную сложность O(1), хотя иногда сопровождается перераспределением памяти?
Список в CPython реализован как динамический массив ссылок с запасом незанятой ёмкости. При добавлении элемент обычно записывается в уже выделенную область, а при её заполнении массив расширяется с некоторым запасом, поэтому редкие дорогие перераспределения амортизируются до O(1) на одну операцию добавления.
Динамические массивы решают общую проблему хранения последовательности, размер которой заранее неизвестен. Выделение нового блока памяти под каждый добавляемый элемент давало бы лишние системные операции и приводило бы к линейной стоимости каждого добавления.
Стратегия расширения с запасом используется как компромисс между быстрым ростом и экономией памяти. В Python она скрывает управление ёмкостью от разработчика, сохраняя удобство изменяемого списка.
Если бы список увеличивался ровно на один элемент, каждое расширение требовало бы выделить новый блок, скопировать туда все ссылки и освободить старый блок. Для последовательности из большого числа добавлений суммарное время могло бы стать квадратичным.
Однако запас ёмкости тоже расходует память. Кроме того, при перераспределении временно могут существовать старый и новый массивы ссылок, поэтому кратковременный пик потребления памяти способен быть выше обычного.
Внутри список хранит логический размер и выделенную ёмкость. Пока размер меньше ёмкости, добавление меняет существующий массив ссылок без копирования всех прежних элементов. Сами объекты обычно не перемещаются: копируются только ссылки на них.
Когда свободное место заканчивается, CPython запрашивает более крупный блок памяти и переносит в него ссылки. Точная формула перераспределения является деталью реализации CPython и может меняться; на неё нельзя опираться как на универсальную гарантию языка Python.
Если расширения происходят геометрически, например с некоторым коэффициентом роста, после каждого перераспределения появляется запас для нескольких следующих добавлений. Отдельное расширение может стоить O(n), но суммарная стоимость серии добавлений составляет O(n), то есть средняя стоимость одного добавления — амортизированно O(1).
Удаление элементов обычно не означает немедленное уменьшение выделенной ёмкости. Это позволяет избежать постоянного расширения и сжатия при колебаниях размера, но означает, что список после массового удаления может продолжать удерживать заметный объём памяти.
Модель применима к массиву ссылок, а не к размеру самих объектов. Список из миллиона коротких чисел и список из миллиона больших словарей имеют сопоставимую память под ссылки, но резко различаются по памяти, занятой объектами.
Для последовательной обработки данных иногда лучше не накапливать список вообще, а использовать итератор или генератор. Если нужен произвольный доступ и изменяемая последовательность, список обычно остаётся подходящим выбором; если важна компактность однотипных числовых данных, стоит рассмотреть специализированные структуры, например массивы из стандартной библиотеки или библиотек численных вычислений.
Сервис собирал результаты пакетной обработки в список. При росте пакета задержка периодически увеличивалась, а профиль памяти показывал кратковременные пики во время расширения списка.
Рассматривались три варианта. Предварительное формирование списка нужного размера уменьшало число расширений, но требовало заранее знать объём и могло оставить неиспользованные элементы. Замена списка на генератор снижала память, но лишала систему необходимости повторно обходить уже полученные результаты. Использование специализированного числового массива экономило память, но не подходило для разнородных объектов.
Выбрали генератор для потоковой отправки результатов, поскольку повторный произвольный доступ не требовался. Пиковое потребление памяти снизилось, а периодические задержки из-за перераспределений исчезли; для сценариев, где результаты должны были сохраняться целиком, оставили список и ограничили размер пакета.
Почему амортизированная O(1) не означает, что каждое добавление выполняется за постоянное время?
Отдельная операция расширения может потребовать выделить новый блок и скопировать в него все ссылки, поэтому её стоимость составляет O(n). Амортизированная оценка относится к суммарной стоимости длинной последовательности операций, где редкие дорогие расширения распределяются по множеству дешёвых добавлений.
Что именно копируется при перераспределении списка — объекты или их содержимое?
Обычно копируется массив ссылок на объекты. Сами объекты, на которые указывают эти ссылки, не дублируются и не перемещаются из-за расширения списка. Поэтому стоимость перераспределения зависит от количества элементов-ссылок, но не требует копирования содержимого каждого вложенного объекта.
Почему уменьшение длины списка не гарантирует немедленного возврата всей памяти операционной системе?
Список может сохранить ранее выделенную ёмкость для последующих добавлений. Даже если внутренний массив уменьшен или освобождён, Python-аллокатор и системный аллокатор могут оставить полученные страницы в пуле процесса для повторного использования. Поэтому изменение длины списка, его ёмкости и RSS процесса — разные наблюдаемые величины.