ruby - ruby 数组中 shift/unshift 的运行时间是多少

Question

有人知道 ruby​​ 数组中的 shift 和 unshift 有多高效吗？

从数组的开头删除并且必须移动内存中的每个元素会变得非常低效。我假设 ruby​​ 以其他方式做到这一点。

以下任何信息都会有所帮助:
- 算法运行时
- 实现
- 一般效率
- shift/unshift 是否可以用于队列(在 C++ 之类的东西中这不会)

谢谢!

Answer 1

在旧版本的 Ruby 中(~2012 之前)，unshift 是一个 O(n) 操作。但是，在 this commit 中添加了优化和 released in Ruby 2.0.0这使得 unshift 摊销 O(1)，这意味着它保证平均为 O(1)，但单个操作可能为 O(n) .这与 shift 的运行时间相同。

This CS Stack Exchange post很好地解释了这是如何工作的，以及如何以 O(1) 分摊运行时间结束(这是关于 C++ 的 vector::push_back，但它的工作方式相同)。