Disjoint Set 结构实现，也称为 Union-Find。

文档

示例

使用此实现的原因

• 使用单个内存分配来存储所有树和所有层级。
• 独特功能：并行线程中的并操作。
• 独特功能：在初始并操作之后，可以并行查询根。
• 从所有标签都是底层缓冲区有效索引的知识中进行优化。其他实现使用带有边界检查的安全索引，这没有被优化掉。
  • 该软件包使用 Miri 进行了大量测试，因此使用它是安全的。
• 具有 3 种适合您特定需求的版本
  • 推荐的默认版本 DisjointSet 适用于在事先知道节点数量的情况下的用例，
  • DisjointSetArrayU8/DisjointSetArrayU16/DisjointSetArrayU32/DisjointSetArrayU64，适用于在首选将所有数据结构内联存储而不进行额外的堆分配的情况。
  • DisjointSetDynamic 如果事先不知道确切的节点数量。
• DisjointSet 和 DisjointSetDynamic 使用更小的节点标签类型以减少内存使用。这在例如 DisjointSet 中具有 u16::MAX 节点的使用中尤为重要，它占用 256 KByte 内存，非常适合 L2 缓存，而 u16::MAX+1 将使用大约 512 KBytes，这很难适应。这种优化对用户是透明的，因此不需要考虑。
• 良好的文档。
• 良好的测试覆盖率。

基准测试结果

我在 Core i5 6300HQ 上对 crates.io 上大多数具有并查集实现的流行 crate 进行了基准测试： union-find 和 ena。

Labyrinth/aph-disjoint-set serial   time:   [230.91 µs 231.54 µs 232.21 µs]
Labyrinth/aph-disjoint-set parallel time:   [84.909 µs 85.978 µs 87.173 µs]
Labyrinth/Crate Union-Find          time:   [254.05 µs 254.21 µs 254.37 µs]
Labyrinth/Crate eno                 time:   [444.44 µs 444.77 µs 445.11 µs]
Islands/aph-disjoint-set serial     time:   [177.12 µs 183.31 µs 190.54 µs]
Islands/aph-disjoint-set parallel   time:   [132.87 µs 134.11 µs 135.66 µs]
Islands/Crate Union-Find            time:   [167.80 µs 172.37 µs 177.84 µs]
Islands/Crate eno                   time:   [399.41 µs 400.37 µs 401.52 µs]

基准测试代码可通过 链接 获取。

贡献

该 crate 由 Apache 2.0 或 MIT 许可证授权，因此通过对其贡献，您同意以这两种许可证授权您的代码。