Это связанный список, массив? Я искал вокруг и обнаружил, что люди только гадают. Мои знания C недостаточно хороши, чтобы заглянуть в исходный код.
Переведено автоматически
Ответ 1
Код на C на самом деле довольно прост. Расширяя один макрос и удаляя некоторые нерелевантные комментарии, базовая структура находится в listobject.h, который определяет список как:
typedefstruct { 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. На самом деле массив не удваивается, а увеличивается за счет выделения
каждый раз по емкости, где newsize - запрошенный размер (не обязательно, allocated + 1 потому что вы можете extend использовать произвольное количество элементов вместо appendдобавления их по одному).
Это динамический массив. Практическое доказательство: индексация занимает (конечно, с чрезвычайно малыми различиями (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 использовали связанные списки - они бы испортили производительность многих широко используемых библиотек, построенных на предположении, что списки являются динамическими массивами.
Ответ 3
Я бы посоветовал статью Лорана Люса "Реализация списка в Python". Она была действительно полезна для меня, потому что автор объясняет, как список реализован в CPython, и использует отличные диаграммы для этой цели.
Структура объекта списка C
Объект list в CPython представлен следующей структурой C. ob_item - это список указателей на элементы списка. allocated - это количество слотов, выделенных в памяти.
Важно заметить разницу между выделенными слотами и размером списка. Размер списка такой же, как len(l). Количество выделенных слотов - это то, что было выделено в памяти. Часто вы увидите, что выделенный размер может быть больше размера. Это сделано для того, чтобы избежать необходимости вызова realloc каждый раз, когда в список добавляются новые элементы.
...
Добавить
Мы добавляем целое число к списку: 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.
...
Удалить объект списка в Python имеет метод для удаления определенного элемента: l.remove(5).
Ответ 4
Это зависит от реализации, но IIRC:
CPython использует массив указателей
Jython использует ArrayList
IronPython, по-видимому, также использует массив. Вы можете просмотреть исходный код, чтобы узнать.
Таким образом, все они имеют O (1) произвольный доступ.