Будет ли del a[0] в Python копировать весь список?

Я пытаюсь использовать простой список с del a[0], чтобы имитировать deque.popleft(). Просто хочу понять, как работает del в Python. Например:

a = [0,1,2,3,4,5]

a находится в непрерывном пространстве памяти. После того, как я вызову del a[0], Python выделит новое пространство и скопирует туда 1,2,3,4,5, или он просто даст a новый адрес (который совпадает с a = a[1:]).

Если он выделяет новое пространство, означает ли это, что del a[0] является _O (len (a) _ операцией?

Если del a[0] совпадает с a = a[1:], восстановит ли Python пространство памяти, которое было удалено из массива?


python list del deque
person Xing Shi    schedule 08.01.2015    source источник
comment
a находится в непрерывном пространстве памяти. - не имеет большого смысла в терминах Python.   -  person Niklas R    schedule 08.01.2015
comment
@NiklasR: Ну, на самом деле в CPython вы заглядываете под капот и обнаруживаете, что старые добрые указатели и mallocs бегают как никогда счастливо...   -  person zehnpaard    schedule 08.01.2015

Ответы (1)


arrow_upward
5
arrow_downward

См. этот ответ: Как реализован список Python?

Списки Python — это, по сути, массивы указателей. Таким образом, хотя удаление с начала перетасовывает все элементы всего списка в новую позицию в том же пространстве памяти, весь список намного меньше, чем можно было бы ожидать, если бы каждый элемент действительно сохранялся в списке, и поэтому перетасовка намного быстрее, с точки зрения постоянных затрат времени.

Но наверняка del a[0] — это операция O(len(a)), поэтому существует deque.

Интересно, что с точки зрения перераспределения памяти удаление элемента не обязательно означает немедленное освобождение пространства памяти элемента. Списки будут увеличиваться/уменьшаться в размере при определенных пороговых значениях, чтобы сделать запросы на выделение памяти более эффективными, а также оптимизировать фрагментацию памяти.

Изменить: В этом сообщении блога дается более подробная информация

Пояснение: ранее в сообщении не объяснялось, что расположение памяти всего списка было одинаковым, но каждый элемент был перемешан и возможно часть памяти освобождена.

person zehnpaard    schedule 08.01.2015
comment
Отличный ответ и отличные посты (особенно второй пост). Спасибо! - person Xing Shi; 08.01.2015