Expand description
BitVec implemented with portable-simd.
BitVec represents numbers by the position of bits. For example, for the set ${1,3,5}$, we
can represent it by a just a byte 010101000 – the most left (high) bit represent if 0
exits in this set or not, the second bit represent 1 …
BitVec is usually used in the algorithm which requires many set intersection/union operations,
such like graph mining, formal concept analysis. Set operations in bitvec can be implemented
with simple and/or/xor operations so it is much faster than “normal” version of HashSet.
Furthermore, as SIMD introduces the ability for handling multiple data with a single instruction, set operations can be even faster with SIMD enabled.
However, implementation with SIMD in Rust is not really an easy task – now only low-level API
is provided through core::arch. It requires
many cfg(target_arch)s (i.e. different implement on different arch) and
assembly-like unsafe function calls.
The Rust standard library’s portable SIMD API provided a much better API for users. You can just treat SIMD operations as an operation on slices. Portable SIMD wraps all the low-level details for you – no arch-specified code, no unsafe, just do what you’ve done on normal integer/floats.
This crate uses Portable SIMD to implement a basic bitvec.
Usage
use bitsvec::BitVec;
let mut bitvec = BitVec::ones(1_000); //create a set containing 0 ..= 999
bitvec.set(1_999, true); // add 1999 to the set, bitvec will be automatically expanded
bitvec.set(500, false); // delete 500 from the set
// now the set contains: 0 ..=499, 501..=1999
assert_eq!(bitvec.get(500), Some(false));
assert_eq!(bitvec.get(5_000), None);
// When try to get number larger than current bitvec, it will return `None`.
// of course if you don't care, you can just do:
assert_eq!(bitvec.get(5_000).unwrap_or(false), false);
let bitvec2 = BitVec::zeros(2000); // create a set containing 0 ..=1999
let bitvec3 = bitvec.and_cloned(&bitvec2);
// and/or/xor/not operation is provided.
// these APIs usually have 2 version:
// `.and` consume the inputs and `.and_clone()` accepts reference and will do clone on inputs.
let bitvec4 = bitvec & bitvec2;
// ofcourse you can just use bit-and operator on bitvecs, it will also consumes the inputs.
assert_eq!(bitvec3, bitvec4);
// A bitvec can also be constructed from a collection of bool, or a colluction of integer:
let bitvec: BitVec = (0 .. 10).map(|x| x%2 == 0).into();
let bitvec2: BitVec = (0 .. 10).map(|x| x%3 == 0).into();
let bitvec3 = BitVec::from_bool_iterator((0..10).map(|x| x%6 == 0));
assert_eq!(bitvec & bitvec2, bitvec3)Performance
run cargo bench to see the benchmarks on your device.
Structs
Representation of a BitVec