ruby数组中shift / unshift的运行时间是多少？
发布时间：2020-12-16 19:13:10 所属栏目：百科 来源：网络整理
导读：有谁知道ruby阵列中的移位和非移位效率如何？ 从数组的开头删除并且必须移动内存中的每个元素可能变得非常低效.我认为ruby会以其他方式做到这一点. 以下任何信息都会有所帮助： – 算法运行时 – 实施 – 一般效率 – 移位/取消移位是否可以接受用于队列(在C
|
有谁知道ruby阵列中的移位和非移位效率如何？
从数组的开头删除并且必须移动内存中的每个元素可能变得非常低效.我认为ruby会以其他方式做到这一点. 以下任何信息都会有所帮助： 谢谢！ 解决方法
在早期版本的
Ruby中(在~2012之前),unshift是一个O(n)操作.但是,在
this commit中添加了一个优化,使得非移位摊销O(1),这意味着它平均保证为O(1),但单个操作可能是O(n).这与班次的运行时间相同.
This CS Stack Exchange post有一个很好的解释,它是如何工作的,以及你如何最终得到一个O(1)摊销的运行时间(它是关于C的vector :: push_back,但它的工作方式相同). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |