ruby – 为什么在数组O(1)中查找？
发布时间：2020-12-16 23:03:17 所属栏目：百科 来源：网络整理
导读：我相信在除 Ruby之外的某些语言中,Array查找是O(1)因为您知道数据的起始位置,并且您将索引乘以数组所持有的数据的大小,然后访问该内存位置. 但是,在Ruby中,Array可以包含来自不同类的对象,那么它如何设法查找O(1)复杂度？ 解决方法 什么@尼尔斯莱特说,更详细
|
我相信在除
Ruby之外的某些语言中,Array查找是O(1)因为您知道数据的起始位置,并且您将索引乘以数组所持有的数据的大小,然后访问该内存位置.
但是,在Ruby中,Array可以包含来自不同类的对象,那么它如何设法查找O(1)复杂度？ 解决方法
什么@尼尔斯莱特说,更详细一点……
基本上有两种合理的方法来存储不同大小的异构对象数组： >将对象存储为单个或双重-linked list,每个单独对象的存储空间前面都有指向前一个和/或后一个对象的指针.这种结构的优点是可以很容易地在任意点插入新对象而不会移动阵列的其余部分,但是巨大的缺点是通过其位置查找对象通常是O(N),因为你必须从列表的一端开始,逐节点地跳过它,直到到达第n个节点. (用于存储单个对象的分配策略也很有趣且复杂,但与您的问题无关.) 像Perl / Python / Ruby这样的动态语言几乎都选择#2作为通用列表/数组类型.换句话说,它们使查找比在列表中的随机位置插入对象更有效,这对于许多应用程序来说是更好的选择. 我不熟悉Ruby的实现细节,但它们可能与Python的列表类型非常相似,其性能和设计在effbot.org详细解释. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |