Как реализован список Python?

Это связанный список, массив? Я искал вокруг и нашел только людей, догадывающихся. Мои знания C не достаточно хороши, чтобы смотреть на исходный код.

Это динамический массив . Практическое доказательство: индексирование занимает (конечно, с очень небольшими различиями (0,0013 мкс!)) Одно и то же время независимо от индекса:

...>python -m timeit --setup="x = [None]*1000" "x[500]"
10000000 loops, best of 3: 0.0579 usec per loop

...>python -m timeit --setup="x = [None]*1000" "x[0]"
10000000 loops, best of 3: 0.0566 usec per loop

Я был бы поражен, если бы IronPython или Jython использовали связанные списки - они бы испортили производительность многих широко используемых библиотек, построенных на предположении, что списки являются динамическими массивами.

Код C довольно прост, на самом деле. Раскрывая один макрос и удаляя несколько ненужных комментариев, основная структура находится в том listobject.h, что список определяется как:

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* 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
     */
    Py_ssize_t allocated;
} PyListObject;

PyObject_HEADсодержит счетчик ссылок и идентификатор типа. Итак, это вектор / массив, который перераспределяется. Код для изменения размера такого массива, когда он заполнен, находится в listobject.c. На самом деле массив не удваивается, а растет за счет

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

до емкости каждый раз, где newsizeзапрашиваемый размер (не обязательно, allocated + 1потому что вы можете extendиспользовать произвольное количество элементов вместо того, чтобы использовать appendих один за другим).

Смотрите также FAQ по Python .

В CPython списки являются массивами указателей. Другие реализации Python могут хранить их различными способами.

Это зависит от реализации, но IIRC:

• CPython использует массив указателей
• Jython использует ArrayList
• IronPython, очевидно, также использует массив. Вы можете просмотреть исходный код, чтобы узнать.

Таким образом, все они имеют O (1) произвольный доступ.

Я бы предложил статью Лорана Люса "Реализация списка Python" . Было действительно полезно для меня, потому что автор объясняет, как список реализован в CPython и использует отличные диаграммы для этой цели.

Структура объекта списка C

Объект списка в CPython представлен следующей структурой Си. ob_itemсписок указателей на элементы списка выделено количество слотов, выделенных в памяти.

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

Важно заметить разницу между выделенными слотами и размером списка. Размер списка такой же, как len(l). Количество выделенных слотов - это то, что было выделено в памяти. Часто вы увидите, что выделенное может быть больше, чем размер. Это сделано для того, чтобы избежать необходимости вызова reallocкаждый раз, когда новые элементы добавляются в список.

...

Append

Мы добавить целое число в списке: l.append(1). Что случается?

Мы по- прежнему, добавив еще один элемент: l.append(2). list_resizeвызывается с n + 1 = 2, но поскольку выделенный размер равен 4, нет необходимости выделять больше памяти. То же самое происходит, когда мы добавляем еще 2 целых числа: l.append(3), l.append(4). Следующая диаграмма показывает, что мы имеем до сих пор.

...

Вставить

Давайте вставим новое целое число (5) в позицию 1: l.insert(1,5)и посмотрим, что происходит внутри.

...

Поп

Когда появляется последний элемент: l.pop(), listpop()называется. list_resizeвызывается изнутри, listpop()и если новый размер меньше половины выделенного размера, список сокращается.

Вы можете заметить, что слот 4 по-прежнему указывает на целое число, но важен размер списка, который теперь равен 4. Давайте добавим еще один элемент. В list_resize()size - 1 = 4 - 1 = 3 меньше половины выделенных слотов, поэтому список сокращен до 6 слотов, и новый размер списка теперь равен 3.

Вы можете заметить, что слоты 3 и 4 по-прежнему указывают на некоторые целые числа, но важная вещь - это размер списка, который теперь равен 3.

...

Удалить Python список объектов имеет метод для удаления определенного элемента: l.remove(5).

Согласно документации ,

Списки Python - это действительно массивы переменной длины, а не связанные списки в стиле Lisp.

Как уже указывалось выше, списки (когда они заметно велики) реализуются путем выделения фиксированного объема пространства и, если это пространство должно заполняться, выделения большего объема пространства и копирования элементов.

Чтобы понять, почему метод амортизируется O (1), без потери общности, предположим, что мы вставили a = 2 ^ n элементов, и теперь мы должны удвоить нашу таблицу до размера 2 ^ (n + 1). Это означает, что в настоящее время мы делаем 2 ^ (n + 1) операций. Последняя копия, мы сделали 2 ^ n операций. До этого мы сделали 2 ^ (n-1) ... вплоть до 8,4,2,1. Теперь, если мы сложим их, мы получим 1 + 2 + 4 + 8 + ... + 2 ^ (n + 1) = 2 ^ (n + 2) - 1 <4 * 2 ^ n = O (2 ^ n) = O (a) общее количество вставок (т.е. O (1) амортизированное время). Кроме того, следует отметить, что если таблица допускает удаление, сжатие таблицы должно выполняться с другим фактором (например, 3x)

Список в Python - это что-то вроде массива, в котором вы можете хранить несколько значений. Список изменчив, что означает, что вы можете изменить его. Более важная вещь, которую вы должны знать, когда мы создаем список, Python автоматически создает reference_id для этой переменной списка. Если вы измените его, назначив другие переменные, основной список будет изменен. Давайте попробуем с примером:

list_one = [1,2,3,4]

my_list = list_one

#my_list: [1,2,3,4]

my_list.append("new")

#my_list: [1,2,3,4,'new']
#list_one: [1,2,3,4,'new']

Мы добавляем, my_listно наш основной список изменился. Список того среднего значения не был назначен как список копий, назначенный в качестве его ссылки.

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