Lib.rs

偏斜列表

sbral::SkewList 提供了一种偏斜 N-ary 随机访问列表，这是一种不可变的数据结构，结合了列表和树的性能特征，具有 O(log index) 的索引和更新操作，以及 O(1) 的推送和弹出。它们最初由 Chris Okasaki 在 1995 年的论文“Purely Functional Random-Access Lists”中描述，并且经过时间的考验。

如果您需要一个性能优秀且持久化的列表，且不需要插入、删除、分割或连接（这些操作都是 O(N)）的功能，您应该考虑使用它们。

默认情况下，SkewList 使用 Rc 内部，不能在多个线程之间共享。您可以通过添加 threadsafe 功能标志来选择线程安全。

详细信息

sbral 在将元素插入到底层数组之前，将它们分组到 16 个元素的块中。因此，在调用 .clone() 或 .get_mut() 时，最多可能克隆 16 个元素。如果您的元素克隆成本高昂或不可能，您需要根据需要将它们包裹在 Rc 或 Arc 中。

分配和跟踪指针是耗时的操作，因此大多数类似于树的数据结构，如 sbral，会将值组合到数组中，以分摊分配成本，减少内存开销和整体树深度。在 sbral 的情况下，这些数组长度为 16，因此当您克隆一个 SkewList 时，最多可能克隆 16 个元素（那些等待插入为新块的部分）并在更新值时，所有 16 个相邻元素可能都会被克隆（如果它们有其他引用）。如果克隆成本高昂或不可能，您需要将您的元素包裹在 Rc 或 Arc 中。

sbral 还通过具有更高的分支因子来寻求提高性能，这再次减少了树深度——这就是它成为偏斜 n-ary 列表而不是偏斜二叉列表的原因。

性能

以下基准测试显示了 sbral 支持的基本集合操作的性能。我选择了一些不同的库来进行比较，它们提供了与 SkewList 相同的功能——推送、弹出、索引和索引突变。（事实证明，它们都是向量。）它们是 im_rc::Vector、dogged::DVec 和 rpds::Vector。此外，我还包括了标准库中的 std::vec::Vec，以提供基准线。每个都作为 usizes 集合进行测试。

与任何微基准测试一样，这些测试相当人为化，并不总是反映数据结构在实际生活中的使用方式。请带着怀疑的态度看待它们，并在决定使用其中一个而不是另一个之前，使用自己的数据进行测试！

构建

这衡量了创建一个新集合并向其中添加N个元素所需的时间（实质上，(0..N).collect()）。

追加

这衡量了向一个包含N个元素的现有集合中添加1000个元素所需的时间。不会计算克隆集合所需的时间。这是为了测试比从头开始构建更实用的较大尺寸。

Vec由于过长的延迟，在测试中途退出。虽然克隆所需的时间不包括在测量中，但它仍然发生，并且在约100万个条目时变得难以承受。

查找第一个

这衡量了随机顺序检索并求和前1000个元素（或列表中的所有元素）所需的时间。虽然对偏斜列表进行索引在最坏情况下是O(log N)，但预期情况是O(log索引)。

选择要相加的元素数量是困难的：属于部分块值的值始终可以通过O(1)访问，并且较小的范围会将测量结果偏向它。当访问最近添加的值时，缓冲区是有益的，基准测试应该反映这一点，但它也应该试图衡量底层集合的性能。

查找最后一个

这是上述最坏情况：访问最后一个（最不最近添加的）值需要O(log N)。

查找分散

这将集合的大小分成1000个相等的范围，在每个范围内选择一个随机索引，然后对这些索引进行洗牌，检索它们并求和它们的值。这是为了测量查找不可预测的值，同时确保它们不会偏向集合的开始或结束。

更新第一个

类似于查找第一个，它以随机顺序访问前1000个元素，并将每个元素加1。所有测试的不可变数据结构仅在必要时克隆值：如果您从未克隆集合，它们将就地修改它。在这种情况下，集合在开始时克隆一次（未测量），然后修改1000次。与追加一样，Vec由于过长的设置时间而提前退出。

更新最后一个

这里没有太多可说的。这与查找最后一个类似。

更新分散

类似于查找分散。

克隆

这衡量了克隆给定大小集合所需的时间。在一个像Rust那样仔细控制变异的语言中，快速且内存高效地克隆是持久数据结构相对于可变数据结构提供的唯一功能，因此这应该尽可能快。

丢弃

这衡量了丢弃给定大小集合全部所需的时间。这可能是罕见的情况，但它可能提供了丢弃其部分所需时间的指示。

进一步阅读

• 原始论文和论文介绍了偏斜列表的工作原理以及它们为什么具有这些性能特征。
• 维基百科上关于偏斜二进制数的文章也不错。
• 单边柔性数组引导 探讨了类似的数据结构，以及在不同查找时间和更新时间之间进行权衡的不同方法。
• fral 是 Rust 中斜二进制列表的一个更直接实现。
• Haskell 的 nested-sequence 库是另一个使用 n-ary 列表的实现。