Удаляет ли элемент из списка списка в Python?

Я пишу программу, которая делает много удалений либо на передней, либо на обратной стороне списка данных, а не на середине.

Я понимаю, что удаление последнего элемента дешево, но как насчет удаления первого элемента? Например, пусть скажем, адрес A находится в 4000, поэтому элемент 0 находится в 4000, а элемент 1 - 4001.

Удалив элемент 0, тогда просто сделайте компилятор, поместите список A в 4001, или переместите элемент 1 в 4001 в местоположение в 4000 и переместите все остальные элементы вниз на 1?

Ответ 1

Нет, это не дешево. Удаление элемента с передней части списка (например, с помощью list.pop(0)) - это операция O(N), и ее следует избегать. Точно так же вставка элементов в начале (с использованием list.insert(0, <value>)) одинаково неэффективна.

Это происходит потому, что после изменения размера списка его элементы должны быть сдвинуты. Для CPython в случае l.pop(0) это выполняется с помощью memmove, а для l.insert(0, <value>), сдвиг выполняется с помощью цикла через сохраненные элементы.

Списки создаются для быстрого оперативного доступа и O(1) операций на их конце.

Поскольку вы обычно выполняете эту операцию, вам следует рассмотреть возможность использования deque из модуля collections (as @ayhan предложил в комментарии). Документы на deque также показывают, как объекты list не подходят для этих операций:

Хотя объекты списка поддерживают подобные операции, они оптимизированы для операций с быстрой фиксированной длиной и несут затраты на перемещение памяти O(N) для операций pop(0) и insert(0, v), которые изменяют размер и положение базового представления данных.

^{(Акцент мой)}

Структура данных deque предлагает O(1) сложность для обеих сторон (начало и конец) с помощью методов appendleft/popleft и append/pop для начала и конца соответственно.

Конечно, с небольшими размерами это требует некоторых дополнительных требований к пространству (из-за структуры deque), которая обычно не должна беспокоить (и, как отмечает @juanpa в комментарии, не всегда выполняется), поскольку размеры списков растут. Наконец, как замечательные примечания к комментариям @ShadowRanger, с очень маленькими размерами последовательностей проблема сбрасывания или вставки с фронта тривиально до такой степени, что на самом деле это не имеет никакого отношения.

Итак, вкратце, для списков со многими элементами используйте deque, если вам нужны быстрые добавления/всплывающие окна с обеих сторон, иначе, если вы случайно получаете доступ и добавляете в конец, используйте list s.

Ответ 2

Удаление элементов из передней части списка в Python равно O (n), при удалении элементов из концов collections.deque является только O (1). В результате результат будет отличным для вашей цели, однако следует отметить, что доступ или добавление/удаление из середины дека более дорогостоящий, чем для списка.

Стоимость удаления O (n) заключается в том, что список в CPython просто реализуется как массив указателей, поэтому ваша интуиция относительно стоимости переключения для каждого элемента верна.

Это можно увидеть на странице странице Python TimeComplexity на Wiki.