Многие думают, что
list — это связный список. На самом деле это динамический массив указателей. 1. Как он хранится в памяти
В структуре
PyListObject на языке C список состоит из трех ключевых полей:—
ob_item — указатель на массив, где лежат адреса объектов.—
ob_size — текущее количество элементов (то, что выдает `len()`).—
allocated — сколько ячеек памяти зарезервировано на самом деле.2. Магия Append и «переезд» памяти
Python не выделяет память под каждый новый элемент. Он делает это «на вырост» (over-allocation). Если вы создаете пустой список и делаете
append, Python выделит сразу 4 ячейки. Когда они закончатся — 8, потом 16, 24 и так далее.Почему
append быстрый? В 99% случаев вы просто записываете адрес в уже готовую ячейку ().Что такое Resize? Когда лимит (`allocated`) исчерпан, Python ищет в памяти новый кусок побольше и копирует туда все указатели. Это , но из-за редких «переездов» амортизированная сложность остается .
3. Почему в списке может лежать «всё что угодно»
Размер самого списка не зависит от того, лежат там строки или другие списки. Массив
ob_item хранит только указатели (адреса в памяти), а они всегда фиксированного размера — 8 байт на 64-битной системе.Благодаря этому Python мгновенно находит любой элемент по индексу. Адрес -го элемента вычисляется по простой формуле:
адрес = начало_массива + i * 8 байт.📍 Навигация: Вакансии • Задачи • Собесы
🐸 Библиотека питониста
#буст