ruby - Arrays Sets 和 SortedSets 在 Ruby 中是如何实现的

Question

通常，数组被实现为内存块，集合被实现为 HashMap ，有序集合被实现为跳跃列表。在 Ruby 中也是如此吗？

我正在尝试从性能和内存占用方面评估 Ruby 中不同容器的使用情况

Answer 1

数组是 Ruby 核心库的一部分。每个 Ruby 实现都有自己的数组实现。 Ruby 语言规范只规定了 Ruby 数组的行为，并没有规定任何特定的实现策略。它甚至没有指定任何会强制或至少建议特定实现策略的性能约束。

然而，大多数 Rubyist 对数组的性能特征有一些期望，这会迫使不符合它们的实现变得默默无闻，因为实际上没有人会使用它:

• 插入、前置或追加以及删除元素的最坏情况步骤复杂度为 O(n)，分摊的最坏情况步骤复杂度为 O(1)
• 访问元素的最坏情况下的步骤复杂度为 O(1)
• 迭代所有元素的最坏情况步骤复杂度为 O(n)

这意味着数组需要实现为具有指数调整大小的动态数组，否则无法满足这些性能保证。您可能得到一棵又宽又浅的树，但 AFAIK 没有 Ruby 实现可以做到这一点。

这是 Rubinius's array implementation ，我个人认为这是所有 Ruby 实现中最容易阅读的。 (注意:只有基本要素是用 C++ 实现的，大多数数组方法是用 Ruby 实现的，例如 kernel/common/array.rb )。

Set 和 SortedSet 是 stdlib 中 set 库的一部分。 stdlib 在 Ruby 实现之间基本保持不变(至少实际上是用 Ruby 编写的部分，显然不能共享用其他语言编写的部分)，并且由于 Set 是用 Ruby 编写的，您可以期望它在所有 Ruby 实现上都是一样的。

Set 实现为 Hash，其中只使用键，值总是true:参见Set#add in lib/set.rb .

SortedSet 由未在 Ruby 中实现的红黑树提供支持。