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

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

5 Solutions collect form web for “Python中的deques如何实现,什么时候比列表更糟?”

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

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

所以是的,一个deque是一个(双重)链表,如另一个答案所示。

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

查看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 

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

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

但…

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

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

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

虽然我不确定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实现一样快,但它使用相同的逻辑。

  • 如何用SqlAlchemy做一个upsert?
  • 如何从python代码调用shell脚本?
  • 从Python项目创build一个可执行文件
  • 在Python中获取列表的最后一个元素
  • Django信号与重载保存方法
  • unit testing是否有可能声明一个方法调用sys.exit()
  • 最好的python XMPP / Jabber客户端库?
  • 使用Python在Google App Engine数据存储中复制实体,而不必在“编译”时知道属性名称
  • 导入matplotlib.pyplot挂起
  • 如何迭代Python,几天,几个小时,几周,几个月后的时间跨度?
  • 更新不同深度的嵌套字典的值