Python中的deques如何实现，什么时候比列表更糟？

我最近开始研究如何在Python中实现各种数据结构，以使我的代码更高效。 在调查list和deques是如何工作的时候，我发现当我想移位和不移位时，我可以从列表中的O（n）到O（1）deques（列表被实现为固定长度数组每次在前面插入东西时都要完全复制，等等）。 我似乎无法find的是如何执行deque的具体细节，以及其缺点vs列表的具体细节。 有人能就这两个问题给我启发吗？

Answer 1

https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

一个dequeobject由一个双向链表的block节点组成。

所以是的，一个deque是一个（双重）链表，如另一个答案所示。

详细说明：这意味着Python列表对于随机访问和固定长度的操作（包括分片）来说要好得多，而deques对于推送和popup结尾更有用，而索引（而不是切片，有趣的是）可能但比列表慢。

Answer 2

查看collections.deque 。 从文档：

Deques支持线程安全的，高效的内存追加，并且在双向任意一侧都有大致相同的O（1）性能。

虽然列表对象支持类似的操作，但是它们针对快速固定长度操作进行了优化，并且对pop（0）和insert（0，v）操作产生O（n）内存移动成本，这些操作改变了底层数据表示的大小和位置。

正如它所说的，使用pop（0）或insert（0，v）会对列表对象产生较大的惩罚。 你不能在deque上使用slice / index操作，但是你可以使用popleft / appendleft ，这是deque被优化的操作。 这是一个简单的基准来certificate这一点：

 import time from collections import deque num = 100000 def append(c): for i in range(num): c.append(i) def appendleft(c): if isinstance(c, deque): for i in range(num): c.appendleft(i) else: for i in range(num): c.insert(0, i) def pop(c): for i in range(num): c.pop() def popleft(c): if isinstance(c, deque): for i in range(num): c.popleft() else: for i in range(num): c.pop(0) for container in [deque, list]: for operation in [append, appendleft, pop, popleft]: c = container(range(num)) start = time.time() operation(c) elapsed = time.time() - start print "Completed %s/%s in %.2f seconds: %.1f ops/sec" % (container.__name__, operation.__name__, elapsed, num / elapsed) 

在我的机器上的结果：

 Completed deque/append in 0.02 seconds: 5582877.2 ops/sec Completed deque/appendleft in 0.02 seconds: 6406549.7 ops/sec Completed deque/pop in 0.01 seconds: 7146417.7 ops/sec Completed deque/popleft in 0.01 seconds: 7271174.0 ops/sec Completed list/append in 0.01 seconds: 6761407.6 ops/sec Completed list/appendleft in 16.55 seconds: 6042.7 ops/sec Completed list/pop in 0.02 seconds: 4394057.9 ops/sec Completed list/popleft in 3.23 seconds: 30983.3 ops/sec 

Answer 3

我怀疑， deque对象的文档条目说明了大部分你需要知道的东西。 着名的报价：

Deques支持线程安全的，高效的内存追加，并且在双向任意一侧都有大致相同的O（1）性能。

但…

索引访问两端是O（1），但在中间减慢到O（n）。 对于快速随机访问，请使用列表。

我不得不看看源代码来判断实现是链表还是别的东西，但是听起来好像一个deque和双链表具有大致相同的特性。

Answer 4

除了所有其他有用的答案之外， 这里还有一些比较Python列表，deques，sets和dictionaries上各种操作的时间复杂度（Big-Oh）的更多信息。 这应该有助于为特定问题select正确的数据结构。

Answer 5

虽然我不确定Python是如何实现它的，但是在这里我只写了一个使用数组的实现。 它和Python的队列一样复杂。

 class ArrayQueue: """ Implements a queue data structure """ def __init__(self, capacity): """ Initialize the queue """ self.data = [None] * capacity self.size = 0 self.front = 0 def __len__(self): """ return the length of the queue """ return self.size def isEmpty(self): """ return True if the queue is Empty """ return self.data == 0 def printQueue(self): """ Prints the queue """ print self.data def first(self): """ Return the first element of the queue """ if self.isEmpty(): raise Empty("Queue is empty") else: return self.data[0] def enqueue(self, e): """ Enqueues the element e in the queue """ if self.size == len(self.data): self.resize(2 * len(self.data)) avail = (self.front + self.size) % len(self.data) self.data[avail] = e self.size += 1 def resize(self, num): """ Resize the queue """ old = self.data self.data = [None] * num walk = self.front for k in range(self.size): self.data[k] = old[walk] walk = (1+walk)%len(old) self.front = 0 def dequeue(self): """ Removes and returns an element from the queue """ if self.isEmpty(): raise Empty("Queue is empty") answer = self.data[self.front] self.data[self.front] = None self.front = (self.front + 1) % len(self.data) self.size -= 1 return answer class Empty(Exception): """ Implements a new exception to be used when stacks are empty """ pass 

在这里你可以用一些代码来testing它：

 def main(): """ Tests the queue """ Q = ArrayQueue(5) for i in range(10): Q.enqueue(i) Q.printQueue() for i in range(10): Q.dequeue() Q.printQueue() if __name__ == '__main__': main() 

它不会像C实现一样快，但它使用相同的逻辑。