索引位向量

此库为位向量提供索引系统，希望允许快速排名和选择操作。

此库基于 Zhou、Andersen 和 Kaminsky 在 Space–Efficient, High–Performance Rank & Select Structures on Uncompressed Bit Sequences 中提出的设计。

性能

性能测试已进行

• 使用 criterion 进行性能测试
• 针对 1GB 向量（实际上略大）
• 以发布模式编译
• 使用 LTO，代码生成单元 1，非增量构建
• 使用 RUSTFLAGS='-C target-cpu=native'
• CPU: Intel® Core™ i7-7700K CPU @ 4.20GHz

使用 target-cpu 可能会对操作速度产生重大影响，因为它允许 llvm & rust 使用可能可用的矢量化 & popcount 指令，因此请考虑如何为要在其上运行程序的特定 CPU 编译。

由于 criterion 对其进行了许多迭代以计时，因此没有将构建索引的时间保留在代码中，这使基准测试运行需要 15 分钟。

另请参阅

我认为在 Haskell 紧凑向量库 中有相同方法的实现。

Zhou, Andersen 和 Kaminsky. Space–Efficient, High–Performance Rank & Select Structures on Uncompressed Bit Sequences