python-3.x - 队列 O(1) 没有在 python 中快速追加或弹出

Question

我使用节点制作了一个队列 O(1)，其中队列类包含“头和尾”，节点包含“下一个和后退”，但是当我通过“timeit”将“入队和出队”与“追加和弹出”进行比较时，我发现“追加和弹出”比我做的“入队和出队”要快得多。我是否在 Node 或 Queue 上做错了什么，或者我的 O(1) 不会像 append 或 pop 一样快？

Answer 1

“arraylist”（这是 Python 列表背后的数据结构）也有O(1)的摊销成本，所以就大哦而言，两者是等价的。实际上，列表有O(n)来附加最坏的情况，但这并不经常发生。通常，列表具有初始容量，当列表已满时，容量会翻倍。这意味着如果我们想创建一个包含n 个元素的列表，并且n非常大，那么列表将被调整为容量：

1, 2, 4, 8, 16, …, n

每次在更大的数组中复制一个原始列表的长度，这意味着复制的总花费是这些数字的总和，即2×n-1，并且这个O(n )，因此这意味着n追加，总共需要O(n)，时间，因此列表中追加的摊销成本为O(1)。

但是还有其他原因会导致您的链表效率降低。每次构建一个新节点时，它都会寻找一个内存槽，通常分配内存需要一些时间。此外，Python 的列表通常在解释器中实现，例如对于CPython [GitHub]，可能是您正在使用的解释器，它与PyListObject[GitHub]一起使用，这通常比在 Python 本身中实现某些东西更有效，因为它是被解释的。