Ruby数组是真正的数组吗？

Question

我知道 Ruby 数组既是动态分配的，也是动态调整大小的；然而，我似乎找不到任何明确的信息来确定它们是否是真正的数组。也就是说，它们在内存中是连续的（更具体地说，它们所持有的引用在内存中是连续的）。

我的假设是，增加 Ruby 数组的大小涉及将整个数组重新分配到需要更大的连续内存块。

这样理解正确吗？或者在这种情况下，“数组”是一个错误的称呼？

- Ant P

---

阅读array.c源代码或许可以帮助理解。 - maerics

数组所保存的关于其元素的信息仅为它们的对象ID。 - sawa

请访问 http://ruby-hacking-guide.github.io/object.html 并转到“struct RArray”部分。虽然这是关于旧版Ruby的，但如果您要阅读源代码，这可能会对您有所帮助。 - Darek Nędza

请参阅 Pat Shaughnessy 的付费书籍《Ruby Under a Microscope》。 - Wayne Conrad

Answer 1

经过查看 Darek 在评论中提到的源代码和文章，我可以确认 Ruby 的数组确实是真正的数组，由连续的内存块组成，在常数时间 O(1) 内可以访问给定索引处的元素。

似乎 Ruby 为了提高 push 等操作的效率而过度分配数组长度；然而，当数组容量超出时，数组会自动扩展到更大的尺寸。

这是一个相当重要的区别，但却被大多数人忽视了，希望这些信息对于其他正在寻找类似启示的人有所帮助。

- Ant P

---

过度分配内存，特别是指指数级的过度分配，是实现动态数组并获得O(1)摊销最坏情况步骤复杂度所必需的。这是实现动态数组的常见方式。而不进行指数级调整大小是一种常见错误，会导致性能不佳。 - Jörg W Mittag

Answer 2

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

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

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

- Array#[]的最坏情况步骤复杂度应为O（切片项数） - Array#<<的最坏情况步骤复杂度应为O(n)，摊销最坏情况步骤复杂度应为O(1) - 等等

基本上，您会从动态数组中期望到的典型性能保证。

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

- Jörg W Mittag

---

非常准确地回答了我想要的问题。谢谢。 - Ant P

“Ruby语言规范” - 这很有趣。我从未听说过这个。我读过Ruby没有规范的说法。如果我错了（或者我的信息已经过时），你能提供规范的链接吗？ - Darek Nędza

@DarekNędza：http://ISO.Org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=59579 - Jörg W Mittag