在 O(1) 中合并两个双端队列
Merge two deques in O(1)
有没有办法在O(1)中合并两个Pythondeques？
Double linked lists can be merged in O(1), and deque is the implementation of a double linked list. However, from the documentation I do not see a way to do efficiently merge two deques. The a.extend(b) and a += b mentioned in 实际上遍历了b的所有元素，所以时间复杂度是O(len(b))而不是O(1).
没有。 deques 不是普通的双向链表。它们是多个值块的链接列表（在 CPython 参考解释器上，每个块最多可以包含 64 个值），其中只有开始和结束块可能不完整； none 个块可能是稀疏的。所以它必须填充左侧的末尾块，这意味着下一个块由两个块的混合填充，依此类推。
除此之外，由于Python中没有破坏性迭代（无论如何都不支持任何语言），即使左边的结束块和开始右侧的块已满。复制必须发生，块所有权不能转移。
我将此作为单独的答案发布，而不是继续在 下的评论中进行交流。 :)
ShadowRanger 正确地指出，deque 的不变量之一是列表中间的块总是 100% 满。因此，如果你有两个双端队列
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (8 9 A B) (C D E .) [2 blocks, 7 elements]
实际上没有办法在 O(1) 时间内将它们连接起来同时保持顺序，因为 deque 的不变量不允许您将结果表示为
X+Y = (. . . 1) (2 3 4 5) (6 7 . .) (8 9 A B) (C D E .) [invalid]
你会调整一个或另一个双端队列中所有元素的位置，就像这样：
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [adjusted elements 8 thru E]
或者像这样：
X+Y = (. 1 2 3) (4 5 6 7) (8 9 A B) (C D E .) [adjusted elements 1 thru 7]
这些是简单的指针交换，所以速度很快；但仍然有 O(n) 个。
但是，假设您传入两个对齐恰好重合的双端队列？
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (. . 8 9) (A B C D) (E . . .) [3 blocks, 7 elements]
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [can be done in O(1)]
在这里，在我们手动追加项目 8 和 9 之后，它确实变得物理上 可能 窃取右侧双端队列的整个尾部在 O(1) 中。而deque可以在O(1)中检测到这种可能性；并手动附加前几项需要 O(block size) = O(1)。所以是的，在并不总是成立的特殊情况下，在 O(1) 时间内实现连接两个双端队列在物理上是 可能。
但是，您必须将该操作称为 x += y 或 x.extend(y) 以外的其他名称。 这两个操作已指定 not修改他们的右手操作数。 collections 中的标准 deque 不提供任何类似的 "destructive" 操作。 （但是，如果它存在，我希望它被命名为 splice。）
您可以看到 deque 的 += 运算符的实现（在 CPython 中实现）here.
有没有办法在O(1)中合并两个Pythondeques？
Double linked lists can be merged in O(1), and deque is the implementation of a double linked list. However, from the documentation I do not see a way to do efficiently merge two deques. The a.extend(b) and a += b mentioned in b的所有元素，所以时间复杂度是O(len(b))而不是O(1).
没有。 deques 不是普通的双向链表。它们是多个值块的链接列表（在 CPython 参考解释器上，每个块最多可以包含 64 个值），其中只有开始和结束块可能不完整； none 个块可能是稀疏的。所以它必须填充左侧的末尾块，这意味着下一个块由两个块的混合填充，依此类推。
除此之外，由于Python中没有破坏性迭代（无论如何都不支持任何语言），即使左边的结束块和开始右侧的块已满。复制必须发生，块所有权不能转移。
我将此作为单独的答案发布，而不是继续在
ShadowRanger 正确地指出，deque 的不变量之一是列表中间的块总是 100% 满。因此，如果你有两个双端队列
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (8 9 A B) (C D E .) [2 blocks, 7 elements]
实际上没有办法在 O(1) 时间内将它们连接起来同时保持顺序，因为 deque 的不变量不允许您将结果表示为
X+Y = (. . . 1) (2 3 4 5) (6 7 . .) (8 9 A B) (C D E .) [invalid]
你会调整一个或另一个双端队列中所有元素的位置，就像这样：
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [adjusted elements 8 thru E]
或者像这样：
X+Y = (. 1 2 3) (4 5 6 7) (8 9 A B) (C D E .) [adjusted elements 1 thru 7]
这些是简单的指针交换，所以速度很快；但仍然有 O(n) 个。
但是，假设您传入两个对齐恰好重合的双端队列？
X = (. . . 1) (2 3 4 5) (6 7 . .) [3 blocks, 7 elements]
Y = (. . 8 9) (A B C D) (E . . .) [3 blocks, 7 elements]
X+Y = (. . . 1) (2 3 4 5) (6 7 8 9) (A B C D) (E . . .) [can be done in O(1)]
在这里，在我们手动追加项目 8 和 9 之后，它确实变得物理上 可能 窃取右侧双端队列的整个尾部在 O(1) 中。而deque可以在O(1)中检测到这种可能性；并手动附加前几项需要 O(block size) = O(1)。所以是的，在并不总是成立的特殊情况下，在 O(1) 时间内实现连接两个双端队列在物理上是 可能。
但是，您必须将该操作称为 x += y 或 x.extend(y) 以外的其他名称。 这两个操作已指定 not修改他们的右手操作数。 collections 中的标准 deque 不提供任何类似的 "destructive" 操作。 （但是，如果它存在，我希望它被命名为 splice。）
您可以看到 deque 的 += 运算符的实现（在 CPython 中实现）here.