Ruby数组是真正的数组吗？

Question

我知道Ruby数组都是动态分配和动态调整大小的; 但是,我似乎无法找到关于它们是否是真正数组的任何明确信息; 即它们在内存中是连续的(更具体地说,它们所持有的引用在内存中是连续的).

我的假设是增加Ruby数组的大小需要将整个数组重新分配到更大的连续内存块(如果需要).

这是正确的,还是"阵列"在这种情况下用词不当？

Answer 1

在评论中回顾了Darek引用的源代码和文章之后,我可以确认Ruby的数组确实是真正的数组,并且由连续的内存块组成,其中给定索引处的元素可以在O(1)时间内被访问.

似乎Ruby过度分配数组以提高效率push和类似操作; 但是,当超出阵列容量时,阵列会自动realloc以更大的尺寸运行.

这是一个相当重要的区别,似乎在很大程度上被忽视了,所以希望这些信息对于寻求类似启蒙的其他人有用.

Answer 2

Ruby 语言规范没有规定Array对象（或实际上任何对象）的任何特定内存表示。这对于实施者来说限制太大。事实上，它甚至没有规定对象必须存在于内存中，这使得像 MagLev 这样的实现成为可能，其中对象内存是分布式磁盘上的 OO 数据库而不是 RAM。

\n\n

Ruby 语言规范也没有为该类的任何方法规定任何特定的性能特征Array。

\n\n

然而，Ruby 程序员已经开始期望某些Array方法能够提供某些性能保证（任何不满足这些保证的实现都将被社区忽略），例如

\n\n

\n
• Array#[]最坏情况的步骤复杂度应为 O(切片的项目数)
\n
• Array#<<最坏情况步骤复杂度应为 O(n)，摊销最坏情况步骤复杂度为 O(1)
\n
• \xe2\x80\xa6 等等。
\n

\n\n

基本上，典型的性能保证了您对动态阵列的期望。

\n\n

这或多或少意味着满足这些性能保证的唯一方法是实现必须使用连续存储和指数调整大小。

\n