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

Question

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

Answer 1

Код 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 .

Answer 2

Это динамический массив .Практическое доказательство: индексирование занимает (конечно, с очень небольшими различиями (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 использовали связанные списки - они разрушили быпроизводительность многих широко используемых библиотек, построенных на предположении, что списки являются динамическими массивами.

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

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

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

typedef struct {

PyObject_VAR_HEAD

PyObject ** ob_item;

Py_ssize_t выделено;

} 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) и посмотрим, что происходит внутри.

...

Pop

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

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

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

...

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

Answer 7

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

Чтобы понять, почему метод 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) </p>