我相信在Ruby以外的其他语言中,数组查找为O(1),因为您知道数据从哪里开始,然后将索引乘以数组所保存的数据大小,然后访问该内存位置。
但是,在Ruby中,数组可以具有来自不同类的对象,那么它如何管理O(1)复杂度呢?
@Neil Slater所说的,还有更多细节……
基本上有两种可行的方法来存储大小不同的异构对象的数组:
将对象存储为单链接列表或双链接列表,每个对象的存储空间前面都有指向前一个和/或后一个对象的指针。这种结构的优点是可以很容易地在任意点插入新对象而无需在数组的其余部分移动,但是巨大的缺点是,按位置查找对象通常是O(N)
,因为您必须从一端开始列表并逐个跳转,直到到达第n个。
存储指向各个对象的大小恒定的表或数组。由于此查找表以连续的有序布局包含大小固定的项目,因此查找单个对象的地址O(1)
;该表只是一个C样式的数组,即使在RISC CPU体系结构上,查找也只需要很少的一对多机器指令。
(用于存储单个对象的分配策略也很有趣且复杂,但与您的问题并不直接相关。)
诸如Perl / Python / Ruby之类的动态语言几乎都选择了#2作为通用列表/数组类型。换句话说,与在列表中的随机位置插入对象相比,它们使查找更为有效,这对于许多应用程序来说是更好的选择。
我不熟悉Ruby的实现细节,但它们可能与Pythonlist
类型的实现细节非常相似,在effbot.org上详细介绍了其性能和设计。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句