Предлагаю вашему вниманию статью, основанную на публикации Laurent Luce о реализации работы со списками в CPython. Она может быть полезна начинающим программистам на Python, либо готовящимся к собеседованию. Функции C показаны в сокращенном варианте и с моими комментариями. Полный текст функций можно найти в исходниках CPython 2.7.
Эта статья описывает реализацию объекта списка в CPython, наиболее популярной реализации Python. Списки в Python — это мощный инструмент, и интересно узнать, как они устроены внутри. Взгляните на простой скрипт, который добавляет несколько целых значений в список и выводит их:
Как вы можете видеть, список является итерируемым объектом.
Объект списка в CPython представлен нижеследующей структурой в C. ob_item — это список указателей на элементы списка, allocated — количество выделенной памяти.
Давайте посмотрим, что происходит при создании пустого списка, к примеру l = []. Вызывается функция PyList_New(0):
Важно понимать разницу между выделенной памятью и размером списка. Размер списка — это тоже самое, что и len(l). allocated — это количество выделенной памяти, которое зачастую может быть больше размера списка. Это делается для предотвращения вызовов realloc при каждом добавлении элементов. Мы разберемся в этом подробнее чуть позже.
Мы добавляем целое число в список: l.append(1). Что в этот момент происходит? Вызывается функция C PyList_Append(), которая, в свою очередь, вызывает функцию app1():
Давайте посмотрим на функцию list_resize(). Она выделяет больше памяти, чем нужно для предотвращения частых вызовов list_resize. Выделение памяти задается следующей последовательностью: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
4 ячейки сейчас выделено для элементов списка и первый из них — это целое число 1. На изображении вы можете увидеть, что l[0] указывает на целое число, которое мы добавили в список. Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память.
Операция добавления элемента в список имеет сложность O(1).
Добавим еще один элемент в список: l.append(2). list_resize вызывается с n+1 = 2, но, так как размер выделенной памяти 4, нет необходимости выделять дополнительную память. То же самое происходить при добавлении еще двух целых чисел: l.append(3), l.append(4). На картинке показано, что мы имеем в итоге:
Вставим новое целое число в позицию 1: l.insert(1,5) и посмотрим, что будет происходить на низком уровне. Вызывается функция ins1():
Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память. Итак, 8 ячеек выделено, но размер списка у нас сейчас 5.
Сложность операции вставки O(n).
Когда вы выталкиваете элемент из списка, l.pop(), вызывается listpop(). list_resize вызывается внутри listpop() и в случае, если новый размер меньше половины выделенной памяти — то список сжимается.
Сложность операции O(1).
Вы можете наблюдать, что 4 ячейка все еще указывает на целое, но важно понимать, что размер списка у нас 4.
Вытолкнем еще один элемент. В list_resize(), size-1 = 4-1 = 3 меньше чем половина выделенных ячеек, поэтому список сжимается до 6 ячеек и новый размер списка становится 3.
Вы можете наблюдать, что 3 и 4 ячейка все еще указывают на целое, но важно понимать, что размер списка у нас 3.
В Python объект списка имеет метод для удаления элемента с заданным значением: l.remove(5). Вызывается listremove().
Сложность операции удаления — O(n).
Эта статья описывает реализацию объекта списка в CPython, наиболее популярной реализации Python. Списки в Python — это мощный инструмент, и интересно узнать, как они устроены внутри. Взгляните на простой скрипт, который добавляет несколько целых значений в список и выводит их:
>>> l = [] >>> l.append(1) >>> l.append(2) >>> l.append(3) >>> l [1, 2, 3] >>> for e in l: ... print e ... 1 2 3
Как вы можете видеть, список является итерируемым объектом.
C-структура объекта списка
Объект списка в CPython представлен нижеследующей структурой в C. ob_item — это список указателей на элементы списка, allocated — количество выделенной памяти.
typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject;
Инициализация списка
Давайте посмотрим, что происходит при создании пустого списка, к примеру l = []. Вызывается функция PyList_New(0):
/* size - размер списка */ PyList_New(Py_ssize_t size) { // Вычисляется реальный размер необходимой памяти nbytes = size * sizeof(PyObject *); // Инициализируется ob_item if (size <= 0) op->ob_item = NULL; else { op->ob_item = (PyObject **) PyMem_MALLOC(nbytes); memset(op->ob_item, 0, nbytes); } // Сохраняется количество выделенных ячеек op->allocated = size; return (PyObject *) op; }
Важно понимать разницу между выделенной памятью и размером списка. Размер списка — это тоже самое, что и len(l). allocated — это количество выделенной памяти, которое зачастую может быть больше размера списка. Это делается для предотвращения вызовов realloc при каждом добавлении элементов. Мы разберемся в этом подробнее чуть позже.
Добавление элементов
Мы добавляем целое число в список: l.append(1). Что в этот момент происходит? Вызывается функция C PyList_Append(), которая, в свою очередь, вызывает функцию app1():
/* self - указатель на объект списка v - указатель на добавляемое значение */ app1(PyListObject *self, PyObject *v) { // Если не удалось изменить размер списка, возвращаем ошибку - значение (-1) if (list_resize(self, n+1) == -1) return -1; // После изменения размера списка, устанавливаем значение элемента n в v PyList_SET_ITEM(self, n, v); // При успешном выполнении возвращаем 0 return 0; }
Давайте посмотрим на функцию list_resize(). Она выделяет больше памяти, чем нужно для предотвращения частых вызовов list_resize. Выделение памяти задается следующей последовательностью: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
/* self - указатель на объект списка newsize - новый размер списка */ list_resize(PyListObject *self, Py_ssize_t newsize) { // Если выделенной ранее памяти достаточно для заданного размера - дополнительной памяти не выделяем if (allocated >= newsize && newsize >= (allocated >> 1)) { assert(self->ob_item != NULL || newsize == 0); Py_SIZE(self) = newsize; return 0; } /* В противном случае выделяем необходимую память, а также резервируем * дополнительную для следующих увеличений списка */ new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); /* Проверяем на переполнение */ if (new_allocated > PY_SIZE_MAX - newsize) { PyErr_NoMemory(); return -1; } else { new_allocated += newsize; } // Выделяем память if (new_allocated <= (PY_SIZE_MAX / sizeof(PyObject *))) PyMem_RESIZE(items, PyObject *, new_allocated); return 0; }
4 ячейки сейчас выделено для элементов списка и первый из них — это целое число 1. На изображении вы можете увидеть, что l[0] указывает на целое число, которое мы добавили в список. Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память.
Операция добавления элемента в список имеет сложность O(1).
Добавим еще один элемент в список: l.append(2). list_resize вызывается с n+1 = 2, но, так как размер выделенной памяти 4, нет необходимости выделять дополнительную память. То же самое происходить при добавлении еще двух целых чисел: l.append(3), l.append(4). На картинке показано, что мы имеем в итоге:
Вставка
Вставим новое целое число в позицию 1: l.insert(1,5) и посмотрим, что будет происходить на низком уровне. Вызывается функция ins1():
/* self - указатель на объект списка where - позиция, в которую вставляется новый элемент v - указатель на вставляемое значение */ ins1(PyListObject *self, Py_ssize_t where, PyObject *v) { n = Py_SIZE(self); // Изменяем размер списка и возвращаем ошибку в случае неудачи if (list_resize(self, n+1) == -1) return -1; // Если позиция отрицательна, то считаем с конца списка if (where < 0) { where += n; if (where < 0) where = 0; } // Если позиция больше длины списка, то вставляем в конец if (where > n) where = n; // Сдвигаем значения списка от конца до вставляемого элемента items = self->ob_item; for (i = n; --i >= where; ) items[i+1] = items[i]; // Вставляем новый элемент items[where] = v; return 0; }
Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память. Итак, 8 ячеек выделено, но размер списка у нас сейчас 5.
Сложность операции вставки O(n).
Выталкивание
Когда вы выталкиваете элемент из списка, l.pop(), вызывается listpop(). list_resize вызывается внутри listpop() и в случае, если новый размер меньше половины выделенной памяти — то список сжимается.
/* self - указатель на объект списка args - параметры, указывающие на выталкиваемый элемент */ listpop(PyListObject *self, PyObject *args) { // По умолчанию выталкиваем последний элемент Py_ssize_t i = -1; // Если список пуст - возвращаем NULL if (Py_SIZE(self) == 0) { return NULL; } // Если индекс отрицательный - считаем с конца if (i < 0) i += Py_SIZE(self); v = self->ob_item[i]; // Если выталкивается последний элемент - вызывает list_resize и возвращаем вытолкнутое значение if (i == Py_SIZE(self) - 1) { status = list_resize(self, Py_SIZE(self) - 1); return v; } // Если выталкивается элемент из внутренности списка, вызываем специальную функцию для изменения списка status = list_ass_slice(self, i, i+1, (PyObject *)NULL); return v; }
Сложность операции O(1).
Вы можете наблюдать, что 4 ячейка все еще указывает на целое, но важно понимать, что размер списка у нас 4.
Вытолкнем еще один элемент. В list_resize(), size-1 = 4-1 = 3 меньше чем половина выделенных ячеек, поэтому список сжимается до 6 ячеек и новый размер списка становится 3.
Вы можете наблюдать, что 3 и 4 ячейка все еще указывают на целое, но важно понимать, что размер списка у нас 3.
Удаление
В Python объект списка имеет метод для удаления элемента с заданным значением: l.remove(5). Вызывается listremove().
/* self - указатель на объект списка v - указатель на удаляемое значение */ listremove(PyListObject *self, PyObject *v) { Py_ssize_t i; // Пробегаемся по списку for (i = 0; i < Py_SIZE(self); i++) { int cmp = PyObject_RichCompareBool(self->ob_item[i], v, Py_EQ); // Если нашли подходящее значение - удаляем его и возвращаем Python None if (cmp > 0) { if (list_ass_slice(self, i, i+1, (PyObject *)NULL) == 0) Py_RETURN_NONE; return NULL; } else if (cmp < 0) return NULL; } // Если не нашли элемент - возвращаем NULL return NULL; }
Сложность операции удаления — O(n).
