有谁知道ruby阵列中的移位和非移位效率如何？
从数组的开头删除并且必须移动内存中的每个元素可能变得非常低效.我认为ruby会以其他方式做到这一点.
以下任何信息都会有所帮助：
– 算法运行时
– 实施
– 一般效率
– 移位/取消移位是否可以接受用于队列(在C之类的情况下这不会)
谢谢！
解决方法
在早期版本的
Ruby中(在~2012之前),unshift是一个O(n)操作.但是,在
this commit中添加了一个优化,使得非移位摊销O(1),这意味着它平均保证为O(1),但单个操作可能是O(n).这与班次的运行时间相同.
This CS Stack Exchange post有一个很好的解释,它是如何工作的,以及你如何最终得到一个O(1)摊销的运行时间(它是关于C的vector :: push_back,但它的工作方式相同).