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

У меня возник спор с преподавателем. Он говорит, что 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 уже определяется тип конкретного хранимого объекта?
  • Вопрос задан
  • 420 просмотров
Решения вопроса 1
15432
@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.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ICL Services Казань
от 80 000 ₽
Eltex Новосибирск
от 80 000 ₽
Recruitment Boutique S.M.Art Москва
от 180 000 до 300 000 ₽
29 окт. 2020, в 03:40
4000 руб./за проект
29 окт. 2020, в 03:23
400 руб./в час
29 окт. 2020, в 02:05
3000 руб./за проект