elias_fano_rust

Rust语言的Sebastiano Vigna的Elias Fano实现。

我们的目标不是实现最佳压缩，而是寻求速度和内存之间的良好平衡。

我们的实现与论文中的实现不同，因为我们没有使用具有跳转量子的高比特位bitvector，而目前我们使用的是完全可索引字典。这似乎是一个合理的想法，因为在SUX实现Elias Fano（SUX是Vigna的一个项目）中，他使用简单的选择来存储高比特位。目前我们只需要select_0和select_1，因此在未来可能会探索更好的结构来支持高比特位上的选择。因此，下一步之一是实现Vigna在《Rank/Select查询的Broadword实现》中展示的simple_select。

Rank和Select性能

我们将我们的库与所有支持rank和select的数据结构进行了基准测试。

基准测试在一个排序的包含0到2_000_000之间1_000_000个值的向量上执行。对于每次运行，选择/排名重复1_000次，输入随机。以下是在我的Ryzen 9 3900x 4Ghz 12c 24t上的结果。

test bio::rank                ... bench:      17,488 ns/iter (+/- 526)
test bio::select              ... bench:     151,620 ns/iter (+/- 6,668)
test ef::rank                 ... bench:      81,228 ns/iter (+/- 3,542)
test ef::select               ... bench:      49,509 ns/iter (+/- 1,761)
test fid::rank                ... bench:      35,865 ns/iter (+/- 1,213)
test fid::select              ... bench:     143,085 ns/iter (+/- 4,942)
test hashmap::select          ... bench:      78,803 ns/iter (+/- 6,984)
test indexed_bitvec::rank     ... bench:      52,563 ns/iter (+/- 1,369)
test indexed_bitvec::select   ... bench:     116,231 ns/iter (+/- 3,741)
test rsdict::rank             ... bench:      21,915 ns/iter (+/- 623)
test rsdict::select           ... bench:      45,674 ns/iter (+/- 317)
test succint::jacobson_rank   ... bench:      17,966 ns/iter (+/- 223)
test succint::jacobson_select ... bench:     509,892 ns/iter (+/- 6,706)
test succint::rank9_rank      ... bench:       9,068 ns/iter (+/- 245)
test succint::rank9_select    ... bench:     324,839 ns/iter (+/- 1,784)
test vec::rank                ... bench:     123,351 ns/iter (+/- 760)
test vec::select              ... bench:       3,880 ns/iter (+/- 61)

内存性能

待办事项！