7 个版本
| 0.0.8 | 2024年4月16日 |
|---|---|
| 0.0.7 | 2023年8月16日 |
| 0.0.6 | 2022年11月21日 |
| 0.0.5 | 2020年10月6日 |
| 0.0.2 | 2020年5月17日 |
#186 in 数据结构
每月47 次下载
用于 elias_fano_rust
59KB
1K SLoC
RsDict：快速位图 rank/select
Rank 和 select 是在位图上执行的有用操作，用于构建更复杂的数据结构。首先，给定索引 i 的 rank 计算左侧的设置位数量。例如，稀疏数组可以用一个密集数组表示现有值，并使用一个位图来指示哪些索引存在。然后，rank 提供了一个从稀疏数组索引到密集数组索引的函数。
Select 是 rank 的逆操作，其中 select(B, k) 返回第 k 个设置位的索引。为了使这两个逆操作，我们为 select 使用零索引（因此 select(B, 0) 返回 B 中第一个设置位的索引）并且 rank 只计算 i 左侧的索引。从我们之前的例子中，select 允许从密集数组索引到原始稀疏数组的转换。
此数据结构在只追加位图之上高效实现这两个操作。它是 Navarro 和 Providel, "Fast, Small, Simple Rank/Select On Bitmaps" 的实现，受到一个 Go 实现 的极大启发。基础位图以压缩形式存储，因此长序列的零和一不会占用太多空间。rank 和 select 的索引比未压缩位图增加了大约 28% 的开销。
有关如何使用 rank 和 select 构建紧凑数据结构的更多示例，请参阅 Navarro 关于 紧凑数据结构 的概述。
实现说明
此库主要是 Go 实现的移植，附带一些额外的优化。
rank 的 SSE 加速
通过仅在夜间使用的 simd 功能和支持 SSSE3 的 CPU，排名的最后一步在几个步骤中完成，没有任何循环。启用此功能可以将我的计算机上的 rsdict::rank 基准测试提高约 40%。有关更多详细信息，请参阅 rank_acceleration.rs。
针对 u64 中的排名和选择的优化例程
支持 popcnt 的 CPU，在 64 位小块中计算排名将使用此指令来高效地计算设置位的数量。选择使用 Daniel Lemire 的博客中的一种算法的修改版本来快速跳过尾随零的运行，该算法使用 tzcnt 来快速跳过尾随零。
紧凑的二项式系数查找表
编码和解码压缩位图的块需要计算二项式系数 B(n, k)，其中 0 <= k <= n <= 64。实时计算此值过于昂贵，因此我们存储了一个预先计算的系数查找表。然而，我们利用 B 在 k 中的对称性，只存储一半的值。有关更多详细信息，请参阅 build.rs。
性能
以下是在我的 2018 年 MacBook Pro 上运行基准测试的结果，使用 -C target-cpu=native。
rsdict::rank time: [10.330 us 10.488 us 10.678 us]
Found 4 outliers among 100 measurements (4.00%)
4 (4.00%) high mild
jacobson::rank time: [17.958 us 18.335 us 18.740 us]
Found 6 outliers among 100 measurements (6.00%)
1 (1.00%) high mild
5 (5.00%) high severe
rank9::rank time: [6.8907 us 7.0768 us 7.2940 us]
Found 1 outliers among 100 measurements (1.00%)
1 (1.00%) high severe
rsdict::select0 time: [37.124 us 37.505 us 37.991 us]
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high severe
rsdict::select1 time: [29.782 us 29.918 us 30.067 us]
Found 7 outliers among 100 measurements (7.00%)
5 (5.00%) high mild
2 (2.00%) high severe
rank9::binsearch::select0
time: [229.64 us 231.54 us 233.87 us]
Found 5 outliers among 100 measurements (5.00%)
2 (2.00%) high mild
3 (3.00%) high severe
rank9::binsearch::select1
time: [253.69 us 255.84 us 258.19 us]
Found 9 outliers among 100 measurements (9.00%)
4 (4.00%) high mild
5 (5.00%) high severe
因此，对于排名查询，此实现比 succinct-rs 的 Jacobson 快，但比其 Rank9 稍慢。然而，对于选择查询，它比在这些排名结构上执行二分搜索要快得多，因此如果您算法中需要选择操作，请考虑使用此库。
测试
我们使用 QuickCheck 测试数据结构的守恒性。此外，还有基本的 AFL 模糊集成，用于使用程序覆盖率找到有趣的测试案例。安装 cargo-afl 并使用设置 fuzz 的功能运行 rsdict_fuzz 二进制文件。
$ cargo install afl
$ cargo afl build --release --test rsdict_fuzz --features fuzz
# Create some starting bitsets within target/fuzz/in and create an empty directory target/fuzz/out.
$ cargo afl fuzz -i target/fuzz/in -o target/fuzz/out target/release/rsdict_fuzz
依赖项
~0–1.4MB