Как получилось, что поиск элементов списка - это O (1) в Python?

Question

Сегодня в классе мы узнали, что извлечение элемента из списка - это O(1) в Python.Почему это так?Предположим, у меня есть список из четырех элементов, например:

li = ["perry", 1, 23.5, "s"]

Эти элементы имеют разные размеры в памяти.И поэтому невозможно взять ячейку памяти li[0] и добавить три раза размер каждого элемента, чтобы получить ячейку памяти li[3].Так как же интерпретатору узнать, где находится li[3], не просматривая список для извлечения элемента?

Answer 1

Когда вы говорите a = [...], a фактически является указателем на PyObject, содержащий массив указателей на PyObject с.

Когда вы запрашиваете a[2], интерпретатор сначаласледует за указателем на список PyObject, затем добавляет 2 к адресу массива внутри него, затем возвращает этот указатель.То же самое происходит, если вы запрашиваете a[0] или a[9999].

По сути, все объекты Python доступны по ссылке, а не по значению, даже целочисленные литералы, такие как 2.В системе указателей есть только некоторые хитрости, чтобы сделать все это эффективным.А указатели имеют известный размер, поэтому их удобно хранить в массивах в стиле C.

Answer 2

Краткий ответ: списки Python являются массивами.

Длинный ответ: термин списка информатики обычно означает либо односвязный список (используемый в функциональном программировании), либо двояко-связанный список (используемый в процедурном программировании).Эти структуры данных поддерживают вставку O (1) либо в начало списка (функционально), либо в любую позицию, которую не нужно искать (процедурно).`` Список '' Python не имеет ни одной из этих характеристик.Вместо этого он поддерживает (амортизированный) O (1), добавляя в конец списка (например, C ++ std :: vector или Java ArrayList).Списки Python - это действительно изменяемые массивы в терминах CS.

Следующий комментарий из документации Python объясняет некоторые характеристики производительности `` lists '' Python:

Можно также использовать список в качестве очереди, где первый добавленный элемент является первым извлеченным элементом («первым вошел, первым вышел»);однако списки не эффективны для этой цели.В то время как добавления и вставки в конце списка выполняются быстро, вставки или вставки в начале списка выполняются медленно (поскольку все остальные элементы должны быть сдвинуты на единицу).

Answer 3

Список в Python реализован в виде массива указателей ¹ .Итак, что действительно происходит при создании списка:

["perry", 1, 23.5, "s"]

заключается в том, что вы на самом деле создаете массив указателей, например:

[0xa3d25342, 0x635423fa, 0xff243546, 0x2545fade]

Каждый указатель "указывает" на соответствующийобъекты в памяти, так что строка "perry" будет храниться по адресу 0xa3d25342, а число 1 будет храниться по 0x635423fa и т. д.

Поскольку все указатели имеют одинаковый размер,интерпретатор может фактически добавить 3-кратный размер элемента к адресу li[0], чтобы получить указатель, хранящийся в li[3].

---

¹ Более подробную информацию можно получить у: рта лошади (исходный код CPython на GitHub) .