moon-collections
High-performance collection data structures for MoonBit, including ordered maps and sets, bitsets, deques, caches, heaps, and AVL trees.
moon add Hhsqoo/moon-collections@0.4.1
Download zipAuthor
Version
0.4.1
License
Apache-2.0
Repository
Last updated
yesterday
Downloads
26
README#Moon Collections
面向 MoonBit 生态的高性能扩展数据结构与算法库，提供有序映射、有序集合、位图、缓存、堆、图算法、并查集和 AVL 有序容器。项目使用纯 MoonBit 实现，不依赖 C/Wasm 外部绑定。
#项目状态
- 当前模块版本：0.4.0
- 兼容工具链：MoonBit 0.10.3+16975d007（CI 基线）及当前 0.10.7；CI 仍固定在比赛要求的 0.10.3
- CI 验证后端：wasm、wasm-gc、js、native；LLVM 是实验性后端，不包含在 --target all 中
- 当前测试规模：105 个测试用例，覆盖集合、图遍历、连通性、空集合、重复插入、边界索引、淘汰顺序、堆耗尽、AVL 删除和双端队列扩容等场景
- 开源协议：Apache-2.0
#包含模块
| 包 | 作用 | 典型复杂度 |
|---|---|---|
| src/indexmap | 保持插入顺序的哈希映射 | 查询/更新平均 O(1)；shift_remove 为 O(n)；swap_remove 平均 O(1) |
| src/indexset | 保持插入顺序的集合 | 插入/查询平均 O(1) |
| src/bitset | 基于 Array[Int] 的动态位图 | 单点操作 O(1)；集合运算按机器字长度批量处理 |
| src/lru_cache | 双向链表 + 哈希表的 LRU 缓存 | get/set/remove 平均 O(1) |
| src/priority_queue | 支持自定义比较器的二叉堆 | peek 为 O(1)；push/pop 为 O(log n) |
| src/sorted_map | AVL 树有序映射 | 查询/插入/删除为 O(log n) |
| src/sorted_set | 基于 SortedMap[T, Unit] 的 AVL 有序集合 | 查询/插入/删除为 O(log n) |
| src/deque | 基于循环缓冲区的双端队列 | 两端插入/删除均摊 O(1) |
| src/graph | 确定性邻接表图与图算法 | 遍历 O(V+E)；拓扑排序 O(V+E) |
| src/disjoint_set | 路径压缩并查集 | 合并/查询近似 O(α(n)) |
#安装与使用
发布到 Mooncakes 后，在你的 MoonBit 模块中执行：
moon add Hhsqoo/moon-collections在目标包的 moon.pkg 中导入需要的包：
import {
"Hhsqoo/moon-collections/src/indexmap" @indexmap,
"Hhsqoo/moon-collections/src/bitset" @bitset,
"Hhsqoo/moon-collections/src/graph" @graph,
"Hhsqoo/moon-collections/src/disjoint_set" @disjoint_set,
}示例：
let map : @indexmap.IndexMap[String, Int] = @indexmap.IndexMap::new()
let _ = map.set("moon", 1)
let _ = map.set("bit", 2)
println("keys: \{map.keys().to_array()}")
let bits = @bitset.BitSet::new()
bits.set(31)
bits.set(32)
println("set bits: \{bits.iter().to_array()}")
let dependencies : @graph.Graph[String] = @graph.Graph::new(true)
let _ = dependencies.add_edge("parse", "typecheck")
let _ = dependencies.add_edge("typecheck", "codegen")
println("build order: \{dependencies.topological_sort()}")
let connectivity = @disjoint_set.DisjointSet::new(4)
let _ = connectivity.union(0, 1)
println("connected: \{connectivity.connected(0, 1)}")完整可运行示例位于 src/examples：
moon run src/examples图算法和并查集的 API、复杂度与应用场景见
docs/graph-and-connectivity.md。
#开发与验证
moon update
moon fmt
moon check --fmt --deny-warn
moon check --target all --deny-warn
moon build --target all
moon test --target all --deny-warn
moon info
git diff --exit-codemoon fmt --deny-warn 和 moon info --deny-warn 不是当前 CLI 的有效参数：格式检查使用 moon fmt --check 或 moon check --fmt --deny-warn；接口检查使用 moon info 后检查生成的 pkg.generated.mbti 是否产生 diff。项目已兼容 0.10.7 的 pkgtype(kind: "executable") 清单语法和 Default::default() API；CI 对 0.10.3 基线执行上述步骤。
Windows 原生目标需要 C 编译器。CI 使用 MSYS2 UCRT64 + MinGW GCC；本地可以将 C:\msys64\ucrt64\bin 加入 PATH 后执行 --target native 或 --target all。
#可复现基准
基准入口是 src/benchmarks，固定执行 100,000 次映射写入/查询，以及每 3 个位置设置一次位图再遍历：
moon run src/benchmarks --target native在 Windows 11、MSYS2 UCRT64、MoonBit 0.10.4 本地运行 5 次的中位数如下。该数据用于复现实验方法，不是跨机器性能承诺：
| 工作负载 | 中位耗时 | 校验和 |
|---|---|---|
| IndexMap 100,000 次写入 + 查询 | 28 ms | 1409965408 |
| BitSet 100,000 次设置 + 遍历 | 28 ms | 1666683333 |
如需比较不同机器或后端，请保留工具链版本、目标后端和工作负载，并重复运行至少 5 次。
#项目结构
moon.mod # 模块元数据和版本
src/indexmap # 有序哈希映射
src/indexset # 有序集合
src/bitset # 动态位图
src/lru_cache # LRU 缓存
src/priority_queue # 二叉堆优先队列
src/sorted_map # AVL 有序映射
src/sorted_set # AVL 有序集合
src/deque # 循环缓冲双端队列
src/examples # 可直接运行的示例
src/benchmarks # 可复现 native 基准入口
docs/graph-and-connectivity.md # 图算法与并查集使用说明
docs/architecture.md # 数据结构和不变量
docs/performance.md # 基准方法与数据
pkg.generated.mbti # moon info 生成的公共接口摘要公共接口文件由 moon info 生成并纳入版本控制，修改公共 API 时请同时检查接口 diff。测试文件采用 *_test.mbt，文档中的代码示例应保持可复制运行。
#贡献
请先阅读 CONTRIBUTING.md。新功能应同时提供边界测试、README/API 示例和必要的复杂度说明；提交前至少运行格式、全目标检查、测试和接口漂移检查。
#许可证与镜像
本项目采用 Apache License 2.0。默认开发分支为 main；master 仅为历史镜像分支。
High-performance collection data structures for MoonBit, including ordered maps and sets, bitsets, deques, caches, heaps, and AVL trees.
0.4.1
Apache-2.0
Updated yesterday
26 downloads