Как реализуется список Python?

Ответ 1

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

Ответ 5

В соответствии с документация,

Списки Pythons представляют собой массивы переменной длины, а не Lisp -строчные связанные списки.

Ответ 6

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

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

Объект списка в CPython представлен следующей структурой C. 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) и посмотреть, что происходит внутри.

...

Поп

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

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

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

...

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

Ответ 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) амортизированное время). Кроме того, следует отметить, что если таблица позволяет удалять, сокращение таблицы должно выполняться с другим фактором (например, 3 раза)

Ответ 8

Список в 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, но наш основной список изменился. Этот средний список не был назначен как список копирования, назначенный в качестве его ссылки.