Внутреннее устройство Python list

Предлагаю вашему вниманию перевод публикации 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

Источник