collections.deque()是Python中常长列表的最佳实现吗？

Question

我想限制python中列表的长度，当

len(list) > limit

时，第一项会被删除，

collections.deque()

可以实现，但是会比：

慢吗

list_A = [2,4,6,8,11]
length_limit = 5
while True:
    # do something to the list, for example, list_A.append(2)
    if len(list_A) > length_limit:
        list_A = list_A[1:]

还有其他方法可以比

collections.deque()

更易读且更高效吗？

Answer 1

你需要知道的一个事实是list和deque在底层是不同的实现。在Cpython中，前者是一个动态数组，后者是一个双向链表。数组擅长通过索引访问元素，但不擅长从内部插入或删除元素。相反，链表擅长从任何地方插入或删除元素（但要先确定节点），但不擅长通过索引访问元素。

至于您到目前为止所描述的，如果您不需要您的列表来进行高效的随机访问，那么双端队列确实是最合适的选择。当你对列表使用切片时，python会根据切片指定的范围复制列表中的引用，并将它们存储在一个新列表中。在您的情况下，这是一个

O(n)

操作（也就是说，所需的时间与列表的长度成正比）。对于deque来说，当长度超过指定的maxlen时，只需要简单的丢弃头节点即可（Cpython也用maxlen限制来优化deque）。这是一个

O(1)

操作，显然比列表效率更高。