Как устроен list() в Python?

Question

[Sazoks]

У меня возник спор с преподавателем. Он говорит, что list в Python - это список.

Я говорю, что это не так хотя бы потому, что есть функция взятия элемента по индексу. Он сказал, что оператор [] можно перегрузить (он сам в этом не уверен). Действительно, можно. Тогда я сказал ему, что элементы list() хранятся в памяти последовательно (за счет чего и есть доступ по индексу), но на это он послал меня разбираться в устройстве памяти Python, аргументировав это тем, что будь это массив, все элементы были бы однотипны (вполне логично).

В коде Python я нашел следующую структуру.

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

Как видно из кода, ob_item - динамический массив указателей на хранимые объекты, аllocated - кол-во выделенной памяти.

Правильно ли я понимаю, что list в памяти представляется именно этой структурой?
Могу ли я на основании представления данной структуры утверждать что элементы list лежат в памяти последовательно?
Могу ли я сделать вывод, что list все же обычный динамический массив, объекты которого имеют тип PyObject, а в полях PyObject уже определяется тип конкретного хранимого объекта?

Comments

[Евгений Шатунов]

Sazoks , сейчас все тобой описанное представляет из себя рассказ.
Но Q&A - это сервис вопросов и ответов. Тебе нужно прояснить свой вопрос. Что тебя интересует?

Помимо этого считаю необходимым напомнить о П3.4 регламента работы сервиса.

Тебе стоит привести свой вопрос в соответствие правилам.

[Sazoks]

Евгений Шатунов, понял, спасибо за поправку.

[Алексей Черемисин]

Евгений Шатунов, почему? Мне кажется, очень хороший вопрос, и вполне конкретный - как устроены списки в питоне. Да, вводную часть можно и урезать. Но как минимум радует пытливость ума!

[zed]

аllocated - кол-во выделенной памяти

Да, но эта память выделена под указатели, а не под сами объекты. Сами же объекты элементов списка хранятся "кто-где", а не в непрерывной области памяти.

Answer 1

[15432]

https://docs.python.org/2/faq/design.html#how-are-...

How are lists implemented in CPython?¶
CPython’s lists are really variable-length arrays, not Lisp-style linked lists. The implementation uses a contiguous array of references to other objects, and keeps a pointer to this array and the array’s length in a list head structure.

This makes indexing a list a[i] an operation whose cost is independent of the size of the list or the value of the index.

When items are appended or inserted, the array of references is resized. Some cleverness is applied to improve the performance of appending items repeatedly; when the array must be grown, some extra space is allocated so the next few times don’t require an actual resize.

Короче динамический массив. Непрерывный массив указателей на объекты

Comments

[Алексей Черемисин]

Я бы еще добавил, что это классический динамический список, описанный у Кнута.

Answer 2

[res2001]

Когда вы программируете на питоне не важно как реализован список внутри, главное, чтобы он выполнял то, что от него требуется.
Он вполне мог бы быть реализован и как связный списк. Такая реализация не отменяет операцию взятия элемента по индексу.
Взятие элемента по индексу в питоне, это совсем не взятие элемента по индексу в массиве Си.
Все операции в питоне (в т.ч. и взятие элемента по индексу) просто вызывают соответствующие функции обработчики. В функциях может быть какая угодно логика от Сишного взятия элемента по индексу, до прохождения списка до нужного элемента и т.п.
Реализация каждого типа в питоне заполняет структуру указателей на функции, реализующих питоновские операции для этого типа. Вы выйдите на эту структуру, если дальше продолжите раскопки PyObject_VAR_HEAD.

PS: Ваши выводы, основанные на структуре питоновского списка, верны.
Для студента 1 курса очень не плохо!