Предлагаю вашему вниманию перевод публикации Laurent Luce о реализации работы со списками в CPython. Она может быть полезна начинающим программистам на Python, либо готовящимся к собеседованию.
Эта статья описывает реализацию объекта списка в 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 = []:
arguments: size of the list = 0
returns: list object = []
PyListNew:
nbytes = size * size of global Python object = 0
allocate new list object
allocate list of pointers (ob_item) of size nbytes = 0
clear ob_item
set list's allocated var to 0 = 0 slots
return list object
Важно понимать разницу между выделенной памятью и размером списка. Размер списка — это тоже самое, что и len(l). allocated — это количество выделенной памяти, которое зачастую может быть больше размера списка. Это делается для предотвращения вызовов realloc при каждом добавлении элементов. Мы разберемся в этом подробнее чуть позже.
Добавление элементов
Мы добавляем целое число в список: l.append(1). Что в этот момент происходит? Вызывается внутренняя функция C app1():
arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
n = size of list
call list_resize() to resize the list to size n+1 = 0 + 1 = 1
list[n] = list[0] = new element
return 0
Давайте посмотрим на функцию list_resize(). Она выделяет больше памяти, чем нужно для предотвращения частых вызовов list_resize. Выделение памяти задается следующей последовательностью: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
new_allocated += newsize = 3 + 1 = 4
resize ob_item (list of pointers) to size 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():
arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
resize list to size n+1 = 5 -> 4 more slots will be allocated
starting at the last element up to the offset where, right shift each element
set new element at offset where
return 0
Квадраты, помеченные прерывистой линией, обозначают выделенную, но еще не использованную память. Итак, 8 ячеек выделено, но размер списка у нас сейчас 5.
Сложность операции вставки O(n).
Выталкивание
Когда вы выталкиваете элемент из списка, l.pop(), вызывается listpop(). list_resize вызывается внутри listpop() и в случае, если новый размер меньше половины выделенной памяти — то список сжимается.
arguments: list object
returns: element popped
listpop:
if list empty:
return null
resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
set list object size to 4
return last element
Трудоемкость операции O(1).
Вы можете наблюдать, что 4 ячейка все еще указывает на целое, но важно понимать, что размер списка у нас 4.
Вытолкнем еще один элемент. В list_resize(), size-1 = 4-1 = 3 меньше чем половина выделенных ячеек, поэтому список сжимается до 6 ячеек и новый размер списка становится 3.
Вы можете наблюдать, что 3 и 4 ячейка все еще указывают на целое, но важно понимать, что размер списка у нас 3.
Удаление
В Python объект списка имеет метод для удаления элемента с заданным значением: l.remove(5). Вызывается listremove().
arguments: list object, element to remove
returns none if OK, null if not
listremove:
loop through each list element:
if correct element:
slice list between element's slot and element's slot + 1
return none
return null
Для среза списка и удаления элемента вызывается list_ass_slice() и интересно то, как она работает. В нашем случае нижний индекс для среза 1 и верхний индекс 2, если мы удаляем элемент со значением 5 в позиции 1.
arguments: list object, low offset, high offset
returns: 0 if OK
list_ass_slice:
copy integer 5 to recycle list to dereference it
shift elements from slot 2 to slot 1
resize list to 5 slots
return 0
Сложность операции удаления — O(n).
Автор: medvedGrizli
