vecbool

基于 Vec<u8> 的位向量简单实现。

vecbool::VecBool 实现旨在替换 Vec<bool>，同时保持相似的性能并减少内存使用 - 因为一个 u8 可以打包 8 个 bool，而一个 Vec<bool> 使用一个字节来存储一个 bool。

注意：这是一个主要用于学习目的的玩具项目。如果您需要更健壮的替代品，请查看 crate bitvec。如果您发现可以改进的地方，请随时在 github 上创建问题。任何反馈都将非常受欢迎！

示例

use vecbool::vecbool::VecBool;

let mut vecbool = VecBool::new();

assert_eq!(vecbool.get(0), None);

vecbool.push(true);
vecbool.push(false);
assert_eq!(vecbool.get(0), Some(true));
assert_eq!(vecbool.get(1), Some(false));

let vec: Vec<_> = vecbool.iter().collect();
assert_eq!(vec, vec![true, false]);

assert_eq!(vecbool.pop(), Some(false));
assert_eq!(vecbool.pop(), Some(true));
assert_eq!(vecbool.pop(), None);

基准测试

基准测试比较了 BoolVec、Vec<bool> 和 BitVec。基准测试使用 rust 的默认基准测试工具（可在 nightly 版本中找到），我没有使用过，因此结果可能容易出错。无论如何，获得的结果如下

迭代包含 n 个元素的向量中的元素 - 对于 1_000_000 个元素，VecBool 的性能更好，可能是因为某种自动向量化的小花招

test bitvec::iter_10_elements         ... bench:          10 ns/iter (+/- 0)
test vec::iter_10_elements            ... bench:           2 ns/iter (+/- 0)
test vecbool::iter_10_elements        ... bench:           6 ns/iter (+/- 0)

test bitvec::iter_1000_elements       ... bench:         739 ns/iter (+/- 753)
test vec::iter_1000_elements          ... bench:         267 ns/iter (+/- 6)
test vecbool::iter_1000_elements      ... bench:         274 ns/iter (+/- 313)

test bitvec::iter_1_000_000_elements  ... bench:     660,920 ns/iter (+/- 11,827)
test vec::iter_1_000_000_elements     ... bench:     306,850 ns/iter (+/- 405,266)
test vecbool::iter_1_000_000_elements ... bench:     186,838 ns/iter (+/- 1,389)

在包含 n 个元素的向量中访问 n 个随机索引 - 性能相当

test bitvec::get_10_elements          ... bench:           3 ns/iter (+/- 0)
test vec::get_10_elements             ... bench:           4 ns/iter (+/- 1)
test vecbool::get_10_elements         ... bench:           7 ns/iter (+/- 2)

test bitvec::get_1000_elements        ... bench:         295 ns/iter (+/- 242)
test vec::get_1000_elements           ... bench:         391 ns/iter (+/- 3)
test vecbool::get_1000_elements       ... bench:         750 ns/iter (+/- 859)

test bitvec::get_1_000_000_elements   ... bench:     603,804 ns/iter (+/- 26,881)
test vec::get_1_000_000_elements      ... bench:     613,401 ns/iter (+/- 471,768)
test vecbool::get_1_000_000_elements  ... bench:     663,668 ns/iter (+/- 209,096)

将 n 个元素推送到空向量中 - 性能相当

test bitvec::push_10_elements         ... bench:          95 ns/iter (+/- 0)
test vec::push_10_elements            ... bench:         165 ns/iter (+/- 6)
test vecbool::push_10_elements        ... bench:          94 ns/iter (+/- 88)

test bitvec::push_1000_elements       ... bench:       5,520 ns/iter (+/- 6,270)
test vec::push_1000_elements          ... bench:       3,014 ns/iter (+/- 3,864)
test vecbool::push_1000_elements      ... bench:       2,985 ns/iter (+/- 5,452)

test bitvec::push_1_000_000_elements  ... bench:   3,276,390 ns/iter (+/- 5,365,655)
test vec::push_1_000_000_elements     ... bench:   2,661,370 ns/iter (+/- 4,383,416)
test vecbool::push_1_000_000_elements ... bench:   2,486,280 ns/iter (+/- 1,126,453)

基准测试代码可在 此处 找到。