使用Python列表作为队列的效率 [英] Efficiency of using a Python list as a queue

问题描述

一个同事最近写了一个程序，其中他使用Python列表作为队列.换句话说，他在需要插入项目时使用.append(x)，在需要删除项目时使用.pop(0).

A coworker recently wrote a program in which he used a Python list as a queue. In other words, he used .append(x) when needing to insert items and .pop(0) when needing to remove items.

我知道Python具有 collections.deque ，试图弄清楚是否要花费我的(有限的)时间来重写此代码以使用它.假设我们执行了数以百万计的追加和弹出操作，但条目数从未超过数千，那么他的列表使用情况会成问题吗?

I know that Python has collections.deque and I'm trying to figure out whether to spend my (limited) time to rewrite this code to use it. Assuming that we perform millions of appends and pops but never have more than a few thousand entries, will his list usage be a problem?

尤其是，即使列表只有一千个东西，Python列表实现所使用的基础数组是否会无限期地继续增长以拥有数百万个点，或者Python最终会做一个realloc并释放一些内存?

In particular, will the underlying array used by the Python list implementation continue to grow indefinitely have millions of spots even though the list only has a thousand things, or will Python eventually do a realloc and free up some of that memory?

推荐答案

使用list实现不会耗尽内存，但是性能会很差.来自文档:

You won't run out of memory using the list implementation, but performance will be poor. From the docs:

尽管list对象支持类似的功能 操作，它们针对 快速定长运算并招致 O(n)的内存移动成本为 pop(0)和insert(0, v)操作 这会改变大小和 基础数据的位置 表示形式.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

因此使用deque会更快.

这篇关于使用Python列表作为队列的效率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！