RoaringBitmap（位图数据结构）招募

发布人:仓颉技术交流平台官方

分类:算法与数据结构 / 位图与高性能集合

为丰富仓颉语言的生态系统，填补其在高性能计算与大数据处理领域基础数据结构的空白，现招募开发者，运用仓颉语言设计与实现一个媲美 Roaring Bitmaps 的高性能压缩位图索引库。 Roaring Bitmaps是一种高效的压缩位图数据结构，广泛应用于数据库、搜索引擎、OLAP分析等系统，以实现快速的集合运算（如交集、并集、差集）与成员查询。本项目目标在于，充分挖掘仓颉语言在系统编程与并发控制方面的潜能，构建一个设计精良、性能卓越、接口清晰且完全兼容仓颉语言特性的基础组件。

等待接取

2025-11-20

悬赏内容

招募内容

1. 项目背景与目标

为构建仓颉语言在大数据、数据库及搜索引擎等高性能计算场景下的核心竞争力，我们启动一项公益性开源项目，旨在原生实现一个与Roaring Bitmaps技术标准看齐的压缩位图库。

Roaring Bitmaps是一种将位图与多种压缩技术相结合的优雅数据结构，通过智能选择最优的容器类型，在稀疏和稠密数据集上均能实现极致的查询性能与空间效率。本项目不仅要求功能完备，更追求达到工业级的性能、健壮性和可维护性，使其成为仓颉语言生态中一个标杆性的基础组件。

2. 项目详细规格与技术要求

2.1 核心数据结构规范

项目需实现Roaring Bitmaps的核心三态容器机制，其逻辑如下：

容器类型	适用数据特征	内部实现简述	优势
数组容器	稀疏数据（容量 ≤ 4096）	使用有序数组存储设置的位索引	内存占用小，二分查找速度快
位图容器	稠密数据（容量 > 4096）	使用长度为2^16位的经典位图（8KB）	位运算速度快，适合密集操作
运行容器	连续数据（长行程）	使用行程长度编码（RLE）存储连续区间	对连续值压缩率极高，解码快

容器转换策略：必须实现高效的动态转换逻辑。例如，当向数组容器插入数据使其容量超过阈值（如8192）时，应自动转换为位图容器；反之，当位图容器的基数（设置位的数量）下降至阈值以下时，应转换回数组容器。转换逻辑需保证线程安全与数据一致性。

2.2 关键算法实现要求

（1）集合运算（以交集为例）

所有集合运算（AND, OR, XOR, ANDNOT）都需要针对不同容器组合进行优化。以下伪代码展示了核心的交集运算逻辑，要求实现同等水平的算法优化。

// 伪代码示例：两个RoaringBitmap的交集操作
function intersect(bitmap1, bitmap2) -> RoaringBitmap {
    result = new RoaringBitmap()
    iterator1 = bitmap1.getContainerIterator()
    iterator2 = bitmap2.getContainerIterator()

    while iterator1.hasNext() and iterator2.hasNext() {
        container1 = iterator1.next()
        container2 = iterator2.next()

        if container1.key < container2.key {
            // 容器键不匹配，跳过
            continue
        } else if container1.key > container2.key {
            // 容器键不匹配，跳过
            continue
        } else {
            // 相同键的容器进行交集
            key = container1.key
            new_container = container1.and(container2)
            if not new_container.isEmpty() {
                result.addContainer(key, new_container)
            }
        }
    }
    return result
}

// 容器级别的交集运算，需根据类型分派最优算法
function arrayContainer.and(bitmapContainer) -> Container {
    // 优化：遍历数组，检查位图对应位置是否为1
    result_array = new ArrayContainer()
    for value in this.array {
        if bitmapContainer.bitmap[value] == 1 {
            result_array.add(value)
        }
    }
    return result_array
}

（2）序列化与持久化

必须严格遵循 Roaring Bitmaps官方格式规范实现序列化功能。序列化后的数据应具备平台无关性，可被其他语言实现的库正确读取。

序列化头部概览（示例）：

字段	大小（字节）	描述
Cookie	4	标识符（例如 `0x3A71F0A3`）
描述符	4	版本及标志位
容器数量	4	序列化中包含的容器数量
...	...	...

3. 项目交付物与质量认证标准

3.1 代码交付物

核心库源码：完整、模块化的仓颉语言源代码。
API文档：基于仓颉语言文档工具生成的API参考，每个公开函数和类型均有详尽说明。
架构设计文档：阐述关键设计决策、容器选择策略、内存管理模型和并发处理方案。

3.2 质量认证基准

为确保项目成果达到生产级质量，必须通过以下量化标准的验证：

测试类别	具体标准与指标
功能正确性	1. 单元测试覆盖率 ≥ 98%：覆盖所有容器类型、集合运算、序列化/反序列化、边界条件。 2. 模糊测试：通过随机输入验证程序的健壮性，确保无崩溃或未定义行为。
性能基准	1. 性能对比测试：提供与Java/C++版Roaring Bitmaps的横向对比报告。关键指标包括： - 吞吐量：操作数/秒（如交集运算）。 - 延迟：单次操作耗时（P99分位）。 - 内存占用：处理特定数据集时的内存消耗。 2. 可扩展性测试：展示在数据量从1万到1亿级增长时，性能的平滑变化。
代码质量	1. 静态分析：代码通过仓颉语言编译器或相关Lint工具的最严格检查，无警告。 2. 代码审查：所有代码需经过项目维护者的严格审查，确保符合编码规范与最佳实践。

质量认证要求

交付件

NO	交付件描述	备注
1	三方库源代码	源代码
2	三方库测试方案和用例	测试用例和文档
3	用户手册，API文档，设计文档，license文档	资料和文档

验收标准

1.功能

三方库必须有明确的功能；
如果参考对标库移值开发，功能与参考三方库保持一致。

2.资料

Readme：包含简介，软件架构，目录结构，下载安装（编译构建），接口说明，使用示例，约束限制，开源协议，参与贡献等内容；
Changelog，三方库版本需包含基本的修改说明。

3.标准遵从性（可选），三方库实现需满足对应协议或行业标准，举例

appquth：支持对OAuth 的PKCE扩展；
icu4j：支持unicode标准库，通用字符集ISO/IEC 10646。

4.性能目标

性能敏感三方库接口运行性能持平对标三方库

5.开源协议遵从，必须包含License文件

放置合适的开源License协议，建议Apache License Version 2.0；
引用或参考开源三方库，需遵从开源协议。

6.网络安全要求

满足基础的网络安全红线及隐私要求，符合安全编码规范。

过程质量要求

指标分类	指标名称	指标要求	度量工具	牵引 OR Must
代码度量	平均文件代码行	≤300 LOC	CMetricsPlus，CJMetric	Must
	总文件重复率	C/C++≤4%；相比开源不劣化	CMetricsPlus，CJMetric	Must
	源文件重复率	C/C++≤4%；相比开源不劣化	CMetricsPlus，CJMetric	Must
	平均函数或方法代码行*	≤30 LOC	CMetricsPlus，CJMetric	Must
	总代码重复率	C/C++≤10%；相比开源不劣化	CMetricsPlus，CJMetric	Must
	源文件代码重复率	C/C++≤10%；相比开源不劣化	CMetricsPlus，CJMetric	Must
	平均圈复杂度	≤5；相比开源不劣化	CMetricsPlus，CJMetric	Must
	冗余代码	“0” 【2】；	CMetricsPlus，CJMetric	Must
	不安全函数	NA	CMetricsPlus，CJMetric	Must
静态检查	编译告警	“0” 【2】	Compile工具	牵引
静态检查	通用静态告警	“0” 【2】	Pclint plus，CJLINT	Must
开发者测试	DT用例密度(个/KLOC)	> 40	手工	牵引
	DT代码语句覆盖率	>=85%	Gcov，cjcov	牵引
	DT代码分支覆盖率	>=50%	Gcov，cjcov	牵引
	未做DT文件数	0	手工	牵引
问题解决率	遗留问题DI	整体<10	Issue	牵引
	遗留致命缺陷数(0)	0	Issue	Must
	累计缺陷解决率	85%	Issue	牵引
软件开发	每日构建成功率	100%	CI	牵引
测试评估	测试缺陷密度（/KLOC）	5-9	人工	牵引
	测试用例密度（个/KLOC）	20-40	人工	牵引
	初验用例自动化率	100%	CIDA	牵引
	HLT自动化用例比率	【85%，95%】	CIDA	牵引
开源第三方（含构建工具）	开源片段引用	0（除例外备案类）	FOSSBOT+人工	Must
可信构建	二进制一致性	0（含可澄清）	人工	Mus