从Python中廉价的列表前面删除一个元素？

Question

我正在编写一个程序,它在数据列表的前面或后面做了很多删除,而不是中间的.

我明白删除最后一个元素很便宜,但删除第一个元素怎么样？例如,假设列表A的地址为4000,所以元素0是at 4000,元素1是at 4001.

那么在删除元素0则只是让编译器把名单A在的地址4001,或将它的换挡元件1在4001该位置处4000,并转移所有其他元素下来1？

Answer 1

不,它不便宜.从列表的前面删除元素(list.pop(0)例如,使用)是一种O(N)操作,应该避免.类似地,在开头(使用list.insert(0, <value>))插入元素同样效率低.

这是因为,在调整列表大小后,必须移动它的元素.对于CPython的,在l.pop(0)情况下,这是用做memmove而l.insert(0, <value>),该移位是通过经由存储的商品的循环实现.

列表是专为快速随机访问,并O(1)在他们的行动结束.

既然你经常这样操作,但是,你应该考虑使用deque从collections模块(如@ayhan在评论所说).文档deque还强调list对象不适合这些操作:

虽然列表对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并且会导致O(n)内存移动成本pop(0)和insert(0, v)操作,从而改变底层数据表示的大小和位置.

^{(强调我的)}

的deque数据结构提供O(1)对双方(开始和结束)与复杂性appendleft/ popleft和append/ pop用于分别开始和结束的方法.

当然,对于小尺寸,这会产生一些额外的空间要求(由于其结构deque),这通常应该是无关紧要的(并且正如@juanpa在评论中指出的那样,并不总是保持不变)随着列表的大小增长.最后,正如@ ShadowRanger富有洞察力的评论所指出的那样,由于序列尺寸非常小,从正面弹出或插入的问题被轻视到它真正无关紧要的程度.

因此,简而言之,对于包含许多项目的列表,deque如果您需要来自双方的快速追加/弹出,请使用,否则,如果您随机访问并追加到最后,请使用lists.

Answer 2

从Python的列表前面删除元素是O(n),而从collections.deque的末尾删除元素只是O(1).因此,deque对于您的目的来说是很好的,但应该注意的是,从双端队列中间访问或添加/删除比列表更昂贵.

删除的O(n)成本是因为CPython中的列表只是作为一个指针数组实现,因此您对每个元素的转移成本的直觉是正确的.

这可以在Wiki上的Python TimeComplexity页面中看到.