Окончательно разбираем списки в питоне / Habr

Какая структура данных стоит за list? Как быстро отрабатывает операция append? Эти вопросы часто задают на собеседованиях, и чтобы на них отвечать, нужно понимать, как список работает под капотом. В этой статье разберём, как же устроен список в питоне, копнём на уровень CPython и позапускаем код. После прочтения вы будете знать о списках больше, чем ваши коллеги.

Эта статья предполагает, что у читателя есть какая‑то база: понимание, как работает память, и что такое О большое. Если нет, можно начать с видео‑версии, там больше визуала и примеров с собеседований. В видео также есть про изменяемость списков и про то, почему нужно использовать copy() вместо =. Данная статья является более углублённым разбором.

Где хранятся переменные

А начнём мы всё равно с банального — где хранятся переменные в питоне. Допустим, мы объявили переменную my_variable = 42. Эта переменная (этот объект) питон складывает в некоторую ячейку памяти. Чтобы найти эту ячейку, мы можем вызвать функцию id(), и она вернёт нам адрес в памяти. На самом деле это будет адрес в виртуальной памяти, да и это верно только для реализации питона на CPython.

Для простоты здесь и далее будем смотреть на CPython версии 3.11, так как там проще код. Также некоторые числа могут отличаться в зависимости от архитектуры ОС. Но общая идея остаётся неизменной.

my_variable = 42
print(f"Значение переменной: {my_variable}")


address_my_variable = id(my_variable)
print(f"Адрес объекта переменной: {address_my_variable}")

Для изучения внутренностей будем использовать пакет ctypes — это пакет, который позволяет изучить «подкорку» на C. Будем походу знакомить с его функциями. Например, если у нас есть указатель на объект, то достать сам объект можно с помощью функции cast. Все питоновские объекты имеют тип py_object, а прочитать их обратно в питон можно с помощью .value.

import ctypes


# cast - это функция, которая превращает указатель на объект в объект
# ctypes.py_object - это тип объекта, который мы хотим получить, стандартный тип объектов в CPython
object_by_address = ctypes.cast(address_my_variable, ctypes.py_object)
print(f"Объект по адресу: {object_by_address}")
print(f"Значение переменной: {object_by_address.value}")

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

Список – это массив?

Вы наверняка знакомы со структурой данных «массив». Она позволяет хранить последовательность элементов и обращаться к элементу по порядковому номеру. Это обращение происходит за О(1), поэтому массив так удобен. Под такой массив выделяются свободные ячейки памяти, идущие подряд (это важно). Под каждый элемент выделяется заранее заданное число байт (это тоже важно). В таком случае мы можем вычислить расположение элемента по формуле:

element_address = array_address + i * element_size

где array_address — это адрес 0-го элемента, а еlement_size — это фиксированный размер элемента.

Иллюстрация, поиска i-ого элемента, где i = 3, а размер элемента - 4 байта.

Например, в С массив определяется вот так:

int my_array[5];

При создании массива мы задаём 2 вещи: тип элементов массива и размер массива. В таком случае понятно, сколько памяти нужно аллоцировать под массив (ведь массиву нужны свободные ячейки, идущие подряд).

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

Взвешиваем список

Размер списка можно измерить с помощью функции sys.getsizeof. Давайте посмотрим, как будет меняться его размер при вызове append.

import sys

my_list = []   
print(f"Размер списка из {len(my_list)} элементов: ", sys.getsizeof(my_list), "байт")  # размер пустого списка в байтах

for i in range(20):
   my_list.append(1)
   print(f"Размер списка из {len(my_list)} элементов: ", sys.getsizeof(my_list), "байт")  # размер списка в байтах

Зависимость занимаемой памяти от количества элементов будет выглядеть как‑то так:

То есть память увеличивается ступенчато. Уже догадались, что происходит при операции append?

Массив переменного размера

Посмотрим на реализацию списка в исходниках CPython. В комментариях создатели питона уже описали всю логику, но сейчас можно не вчитываться, я ниже всё объясню.

Исходный код списка на С (прямо из listobject.h):

typedef struct {
   PyObject_VAR_HEAD
   /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
   PyObject **ob_item;

   /* ob_item contains space for 'allocated' elements.  The number
    * currently in use is ob_size.
    * Invariants:
    *     0 <= ob_size <= allocated
    *     len(list) == ob_size
    *     ob_item == NULL implies ob_size == allocated == 0
    * list.sort() temporarily sets allocated to -1 to detect mutations.
    *
    * Items must normally not be NULL, except during construction when
    * the list is not yet visible outside the function that builds it.
    */
   Py_ssize_t allocated;
} PyListObject;

PyObject_VAR_HEAD

PyObject_VAR_HEAD это макрос объекта PyVarObject, который использу��тся для питоновских объектов переменного размера. Отличается от PyObject наличием ob_size. Код находится в object.h:

/* PyObject_VAR_HEAD defines the initial segment of all variable-size
 * container objects.  These end with a declaration of an array with 1
 * element, but enough space is malloc'ed so that the array actually
 * has room for ob_size elements.  Note that ob_size is an element count,
 * not necessarily a byte count.
 */
#define PyObject_VAR_HEAD      PyVarObject ob_base;


/* Nothing is actually declared to be a PyObject, but every pointer to
 * a Python object can be cast to a PyObject*.  This is inheritance built
 * by hand.  Similarly every pointer to a variable-size Python object can,
 * in addition, be cast to PyVarObject*.
 */
struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    PyTypeObject *ob_type;
};


typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

Если развернуть структуру PyListObject, получится примерно следующее:

PyListObject
├─ ob_refcnt     счётчик ссылок на объект (это кстати тема для отдельной статьи)
├─ ob_type       тип объекта (в данном случае list)
├─ ob_size       количество элементов (именно это возвращает len())
├─ ob_item       массив под списком
└─ allocated     размер массива

Имитируем эту структуру в питоне с помощью ctypes:

import ctypes


class PyListObject(ctypes.Structure):
   _fields_ = [
       ("ob_refcnt", ctypes.c_ssize_t), # количество ссылок на объект
       ("ob_type", ctypes.c_void_p), # тип объекта
       ("ob_size", ctypes.c_ssize_t), # количество элементов в списке
       ("ob_item", ctypes.c_void_p), # массив под списком
       ("allocated", ctypes.c_ssize_t), # размер массива
   ]

Создадим питоновский список и «достанем» эту структуру из памяти:

my_list = []
address_my_list = id(my_list)
py_list = PyListObject.from_address(address_my_list)

Теперь будем добавлять э��ементы в список и смотреть, как меняются ob_size и allocated:

print("Количество элементов в списке: ", py_list.ob_size)
print("Количество аллоцированных элементов: ", py_list.allocated)

for i in range(20):
   my_list.append(1)
   print("Количество элементов в списке: ", py_list.ob_size)
   print("Количество аллоцированных элементов: ", py_list.allocated)

Результат в виде таблицы:

ob_size	allocated
0	0
1	4
...	...
4	4
5	8
...	...
8	8
9	16
...	...
16	16
17	24
...	...

Это тот же ступенчатый график, только в количестве аллоцированных элементов, а не в байтах.

Что же происходит «под капотом» при увеличении allocated? А происходит переаллокация — в памяти выделяется место под новый, более большой массив, и туда переносятся существующие элементы. Это затратная операция, ведь нужно перенести каждый элемент массива. Чтобы не выполнять её каждый раз при добавлении нового элемента, память выделяется с запасом.

Наглядное представление ob_size и allocated

На примере нашего списка:

Мы создаём пустой список. allocated = 0, питон не выделяет под массив ничего.
Мы добавляем один элемент. allocated = 4, питон создаёт массив для 4х элементов, но «занят» только 1.
Добавляем ещё один элемент — allocated = 4, у нас ещё есть место, кладём в тот же самый массив.
Повторяем, пока есть место.
Добавляем 5ый элемент, для него уже места нет, пора создать новый массив, побольше. allocated = 8.
И так далее.

Эта структура данных называется динамический массив.

Какова же алгоритмическая сложность операции append для такой структуры? Когда память не переаллоцируется, нам нужно всего лишь добавить элемент в конец массива, сложность такой операции — O(1). Но иногда нам нужно перенести каждый элемент массива в новое место. Сложность такой операции — O(n). В таком случае считают амортизированную сложность. И окажется, что амортизированная сложность — О(1). Как считается амортизированная сложность можно найти под катом в предпоследнем разделе. А пока посмотрим на исходники CPython.

Операция resize

При вызове метода append (а также extend, pop, del и так далее) CPython делает операцию resize. Исходники можно найти в listobject.c, всё поведение в принципе описано в комментариях, но я разберу подробно:

/* Ensure ob_item has room for at least newsize elements, and set
 * ob_size to newsize.  If newsize > ob_size on entry, the content
 * of the new slots at exit is undefined heap trash; it's the caller's
 * responsibility to overwrite them with sane values.
 * The number of allocated elements may grow, shrink, or stay the same.
 * Failure is impossible if newsize <= self.allocated on entry, although
 * that partly relies on an assumption that the system realloc() never
 * fails when passed a number of bytes <= the number of bytes last
 * allocated (the C standard doesn't guarantee this, but it's hard to
 * imagine a realloc implementation where it wouldn't be true).
 * Note that self->ob_item may change, and even if newsize is less
 * than ob_size on entry.
 */
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    PyObject **items;
    size_t new_allocated, num_allocated_bytes;
    Py_ssize_t allocated = self->allocated;

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }

    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    /* Do not overallocate if the new size is closer to overallocated size
     * than to the old size.
     */
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

    if (newsize == 0)
        new_allocated = 0;
    if (new_allocated <= (size_t)PY_SSIZE_T_MAX / sizeof(PyObject *)) {
        num_allocated_bytes = new_allocated * sizeof(PyObject *);
        items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);
    }
    else {
        // integer overflow
        items = NULL;
    }
    if (items == NULL) {
        PyErr_NoMemory();
        return -1;
    }
    self->ob_item = items;
    Py_SET_SIZE(self, newsize);
    self->allocated = new_allocated;
    return 0;
}

В самом начале (25 строка) выполняется проверка, можем ли мы пропустить переаллокацию:

if (allocated >= newsize && newsize >= (allocated >> 1))

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

Дальше вычисляем, сколько нужно аллоцировать под новый массив (41 строка):

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

На псевдокоде:

new_allocated =
    round_down_to_multiple_of_4(
        newsize + newsize // 8 + 6
    )

Это и есть формула для ресайза.

Строка 45-46

Ниже по коду мы рассматриваем случай резкого увеличения размера:

if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
    new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

На псевдокоде:

if newsize - oldsize > new_allocated - newsize:
    new_allocated = round_down_to_multiple_of_4(newsize + 3)

Например, если у нас был массив длины 3 и мы увеличили его на 1000 элементов, то new_allocated = 1132, и условие выполняется: 1003 - 1 > 1132 - 1003. А значит, мы аллоцируем round_down_to_multiple_of_4(1003 + 3) = 1004.

Проверить через код:

my_list = [1, 1, 1]
address_my_list = id(my_list)
py_list = PyListObject.from_address(address_my_list)

print("Количество элементов в списке: ", py_list.ob_size)
print("Количество аллоцированных элементов: ", py_list.allocated)

my_list.extend(range(1000))
print("Количество элементов в списке: ", py_list.ob_size)
print("Количество аллоцированных элементов: ", py_list.allocated)

Дальше (48–49) идёт проверка на 0, так как на 0 элементов нам не нужно место вообще.

И наконец, если памяти хватает, делаем переаллокацию:

        num_allocated_bytes = new_allocated * sizeof(PyObject *);
        items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);

Вернёмся к самому первому условию, которое представим в данном виде:

if allocated >= newsize and newsize >= allocated // 2

Вторая часть условия определяет, как массив будет уменьшаться. Пока размер списка занимает не меньше половины аллоцированной памяти, массив никуда не переносится. А вот если список занимает уже меньше половины памяти, то пора подыскать ему место поскромнее и освободить память.

Проверим, как работает уменьшение списка с помощью следующего кода:

import ctypes


class PyListObject(ctypes.Structure):
   _fields_ = [
       ("ob_refcnt", ctypes.c_ssize_t), # количество ссылок на объект
       ("ob_type", ctypes.c_void_p), # тип объекта
       ("ob_size", ctypes.c_ssize_t), # количество элементов в списке
       ("ob_item", ctypes.c_void_p), # указатель на массив указателей на элементы списка
       ("allocated", ctypes.c_ssize_t), # количество выделенной памяти для элементов списка
   ]

# Создаём список из 20 элементов
my_list = [1]*20
address_my_list = id(my_list)
py_list = PyListObject.from_address(address_my_list)

print("Количество элементов в списке: ", py_list.ob_size)
print("Количество аллоцированных элементов: ", py_list.allocated)

for i in range(20):
   my_list.pop()
   print("Количество элементов в списке: ", py_list.ob_size)
   print("Количество аллоцированных элементов: ", py_list.allocated)

Получится:

ob_size	allocated
20	20
...	...
10	20
9	16
...	...
8	16
7	12
6	12
5	8
...	...
2	8
1	4
0	0

Как список хранит всё что угодно

В примере выше мы добавляли в список целое число 1. На самом деле, если добавлять не число 1, а строку или даже ещё один список, результат getsizeof от этого не поменяется (проверьте сами). То есть размер элемента списка меняется, а размер списка остаётся неизменным. Как же так получается?

Дело в том, что результат команды getsizeof не включает в себя размер хранимых элементов, только размер самого списка. А массив под списком не хранит элементы. Вместо этого он хранит указатели на эти элементы.

Размер указателя — фиксированный, 8 байт (для 64-битной системы). Этот размер можно вычислить из зависимости занимаемой памяти (getsizeof) и allocated. Или просто вызвав функцию из ctypes:

pointer_size = ctypes.sizeof(ctypes.c_void_p)

Проиллюстрируем процесс извлечения элементов с помощью той же самой структуры PyListObject. В этот раз возьмём список из элементов разных типов, чтобы проиллюстрировать работу питона с ними.

import ctypes


class PyListObject(ctypes.Structure):
   _fields_ = [
       ("ob_refcnt", ctypes.c_ssize_t), # количество ссылок на объект
       ("ob_type", ctypes.c_void_p), # тип объекта
       ("ob_size", ctypes.c_ssize_t), # количество элементов в списке
       ("ob_item", ctypes.c_void_p), # указатель на массив указателей на элементы списка
       ("allocated", ctypes.c_ssize_t), # количество выделенной памяти для элементов списка
   ]

# Создаём список
my_list = [1, True, [1, 2, 3]]
address_my_list = id(my_list)
py_list = PyListObject.from_address(address_my_list)

# Размер указателя
pointer_size = ctypes.sizeof(ctypes.c_void_p)

# Где начинается массив указателей на элементы списка
array_address = py_list.ob_item

# Цикл по всем элементам списка
for i in range(py_list.ob_size):
   # адрес ячейки, где хранится указатель (адрес самого pointer)
   pointer_address = array_address + i * pointer_size

   # значение этого указателя (адрес элемента)
   pointer = ctypes.c_void_p.from_address(pointer_address).value

   # что лежит по этому адресу
   element = ctypes.cast(pointer, ctypes.py_object).value

   print(f"[{i}]")
   print(f"  адрес ячейки указателя : {hex(pointer_address)}")
   print(f"  указатель на элемент   : {hex(pointer)}")
   print(f"  значение элемента      : {element}")

Таким образом, массив под списком хранит указатели фиксированного размера (что позволяет применить формулу из первого раздела), а сами указатели могут указывать на объекты любого размера. В сочетании с использованием динамического массива получается максимально гибкий контейнер, который вмещает в себя буквально всё что угодно.

Сложность операций со списком

Под конец приведу шпаргалку с алгоритмической сложностью (по времени) операций со списком:

list[i]       O(1)
append        O(1) (амортизированная)
pop()         O(1) (амортизированная)
pop(i)        O(n)
del list[i]   O(n)
insert        O(n)
extend        O(m), где m - длина второго списка

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

Как считается амортизированная сложность

Как считается амортизированная сложность? Оценивается суммарное время , которое займет операций, и делится на . Посчитаем количество операций, затраченное на append‑ов. Вставок будет , а сколько будет копирований? Для простоты примем коэффициент расширения за . Тогда переаллокация будет происходить при добавлении 1-го, 2-го, 4-го, 8-го и так далее элемента. При каждой переаллокации копируются все существующие элементы, и суммарное количество операций копирования составит:

Это геометрическая прогрессия, где последний элемент , следовательно, по сумме геометрической прогрессии:

$1 + 2 + 4 + ... + 2^k = 2^{k+1} − 1 = 2*2^k - 1 <= 2N - 1$

Складываем число копирований и вставок:

Итого амортизированное время одной операции:

Заключение

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