我相信在除
Ruby之外的某些语言中,Array查找是O(1)因为您知道数据的起始位置,并且您将索引乘以数组所持有的数据的大小,然后访问该内存位置.
但是,在Ruby中,Array可以包含来自不同类的对象,那么它如何设法查找O(1)复杂度？
解决方法
什么@尼尔斯莱特说,更详细一点……
基本上有两种合理的方法来存储不同大小的异构对象数组：
>将对象存储为单个或双重-linked list,每个单独对象的存储空间前面都有指向前一个和/或后一个对象的指针.这种结构的优点是可以很容易地在任意点插入新对象而不会移动阵列的其余部分,但是巨大的缺点是通过其位置查找对象通常是O(N),因为你必须从列表的一端开始,逐节点地跳过它,直到到达第n个节点.
>将一个常量大小的指针表或数组存储到各个对象中.由于此查找表包含连续有序布局中的常量项,因此查找单个对象的地址O(1);该表只是一个C风格的数组,其中查询只需要1到1的机器指令,即使在RISC cpu架构上也是如此.
(用于存储单个对象的分配策略也很有趣且复杂,但与您的问题无关.)
像Perl / Python / Ruby这样的动态语言几乎都选择#2作为通用列表/数组类型.换句话说,它们使查找比在列表中的随机位置插入对象更有效,这对于许多应用程序来说是更好的选择.
我不熟悉Ruby的实现细节,但它们可能与Python的列表类型非常相似,其性能和设计在effbot.org详细解释.