0

我的代码有问题吗？deque当使用collections模块而不是常规列表来计时一个简单的函数时，我的速度提高了 100 倍。

>>> from collections import deque as dl
>>> import cProfile
>>> 
>>> def l(i):
...     l = ['0','1','2','3','4','5','6']
...     while i:
...         l.insert(0,'9')
...         i -= 1
... 
>>> def d(i):
...     l = dl('0123456')
...     while i:
...         l.appendleft('9')
...         i -= 1
... 
>>> cProfile.run('l(100000)')
         100004 function calls in 4.480 seconds

[...]

>>> cProfile.run('d(100000)')
         100004 function calls in 0.031 seconds

如果我的代码没问题，那么使用列表有什么意义呢？为什么不完全切换到deque?

4

1 回答 1

2

来自 Python 文档：

双端队列是堆栈和队列的概括（名称发音为“deck”，是“双端队列”的缩写）。双端队列支持线程安全、内存高效的从双端队列的任一侧追加和弹出，在任一方向上具有大致相同的 O(1) 性能。

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

双端队列支持迭代、酸洗、len(d)、reversed(d)、copy.copy(d)、copy.deepcopy(d)、使用 in 运算符的成员资格测试以及 d[-1] 等下标引用。索引访问在两端都是 O(1)，但在中间慢到 O(n)。对于快速随机访问，请改用列表。

...

现在不同的是，list 是用固定大小的内存块（数组）实现的，而 deque 是用双链表实现的。

这意味着列表必须根据插入新项目的位置重新分配内存并制作数据副本，追加时除外。

但是随机访问（索引）对他们来说非常快。

双端队列没有这样的问题，因为在插入时，只需更正指针以在给定位置插入新节点。

但是查找数据（插入或随机访问的位置 - 索引）需要对双端队列进行迭代。

双端队列也是线程安全的，但除非您必须处理端点，即队列列表的使用属性仍然是您最好的朋友。

双端队列每个项目使用更多的内存，因为它们与每个项目存储至少两个以上的整数（指针）。

还有切片双端队列的问题。可以通过使用旋转方法切换双端队列的端点来手动完成。获取 N 个项目，然后旋转回来。

从 Python 文档中查看 del 如何仅针对一项实现：

rotate() 方法提供了一种实现双端队列切片和删除的方法。例如，del d[n] 的纯 Python 实现依赖于 rotate() 方法来定位要弹出的元素：

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

我认为这对你来说已经足够了。顺便说一句，您的 Q 几乎与以下内容重复：

Python 中的双端队列是如何实现的，它们何时比列表更糟糕？

于 2015-10-21T14:16:20.053 回答