Expand description
A primitive integer BitSet for high-performance combinatorics involving small numbers.
§Scope
This crate offers
- zero-cost abstraction over bitwise operations without allocation or block management and
- a rich interface for mathematics/combinatorics involving integer sets.
pibs is best suited when the bitset should abstract a mathematical set, the performance of set
operations is your primary concern, and the elements naturally lie in the representable range
(0..128 for Set128). See Alternatives if this is not the case.
The ambition of pibs is that you can’t write faster code for any of its operations. If you can, please open an issue!
§Examples
All examples assume the following import, which gives access to Set = BitSet<usize> and
set!.
use pibs::prelude::*;§Subset sum problem
The subset sum problem asks: does a given set of integers have a subset with a particular sum?
§By bruteforce
The following solves the problem by bruteforce. This is not efficient, but showcases the
subsets iterator.
fn subset_with_sum(set: Set, sum: usize) -> Option<Set> {
set.subsets().find(|subset| subset.sum() == sum)
}
let set = set![4, 7, 10, 13, 18, 22, 27];
let solution = subset_with_sum(set, 30).unwrap();
assert_eq!(solution, set![7, 10, 13]);§Fast check for small sums
For deciding the problem without recovering the subset, a faster implementation uses
truncating_subset_sums, which produces the set of
representable sums of all subsets of a set.
fn has_subset_with_sum(set: Set, sum: usize) -> bool {
if sum > Set::MAX {
unimplemented!("the target sum must be representable");
}
set.truncating_subset_sums().contains(sum)
}
let set = set![4, 7, 10, 13, 18, 22, 27];
assert_eq!(has_subset_with_sum(set, 30), true);
assert_eq!(has_subset_with_sum(set, 15), false);§Testing Sidon sets
A set is a Sidon set if every unordered pair of
elements (repetition allowed) has a unique sum. One can use the sumset
operator (also known as Minkowski sum) to check this property given that every pair sum is
representable.
use pibs::Error;
fn is_sidon(set: Set) -> Result<bool, Error> {
let n = set.len();
Ok(set.sumset(set)?.len() == n * (n + 1) / 2)
}
assert_eq!(is_sidon(set![1, 2, 3]), Ok(false)); // 2 + 2 = 1 + 3
assert_eq!(is_sidon(set![1, 2, 4, 8, 16]), Ok(true));
assert_eq!(is_sidon(set![1, 2, 4, 8, 16] + Set::MAX), Err(Error::Irrepresentable));§Minimum generating set
The following computes by brute force a minimum-cardinality set of positive integers that
generate (by taking any subset of the numbers and summing them) all elements of a target set.
This is done using the iter_combinations(n, k) generator, which
yields all subsets of 0..n of size k, and the
truncating_map_add operation (<<), to shift these subsets to
1..=n.
fn min_generating_set(set: Set) -> Set {
let max: usize = set.max().unwrap_or(0);
let bit_length = (usize::BITS - max.leading_zeros()) as usize; // ⌈log₂(max + 1)⌉
// Test all subsets of 1..=max, grouped by increasing cardinality.
for size in 0..bit_length {
for generator in Set::iter_combinations(max, size).map(|g| g << 1) {
if set.is_subset(generator.truncating_subset_sums()) {
return generator;
}
}
}
// If no small generator was found, fall back to powers of two.
Set::from_unchecked((0..bit_length).map(|b| 1 << b))
}
// To generate {0, ..., 9}, we need a generating set of size four.
assert_eq!(min_generating_set(set![0..=9]), set![1, 2, 4, 8]);
// But if we don't need to generate 2 and 7, three numbers suffice.
assert_eq!(min_generating_set(set![0..=9] - set![2, 7]), set![1, 3, 5]);§Usage
§Cheat Sheet
M denotes the largest representable element BitSet::MAX.
§Creation
For using u128/W instead of usize, replace Set with Set128/BitSet<W> and
set! with set128!/bitset![W; ...].
| set | short form | long form | checked variant |
|---|---|---|---|
| ∅ | set![] | Set::new() | |
| {0} | set![0] | Set::singleton(0) | |
| {a, b, c} | set![a, b, c] | Set::from_unchecked([a, b, c]) | Set::try_from([a, b, c]) |
from iter | Set::from_unchecked(iter) | Set::try_from_iter(iter) | |
| {m, …, n} | set![m..=n] | Set::interval(m, n) | |
| {0, …, n - 1} | set![0..n] | Set::range(n) | |
| {0, …, M} | Set::full() |
§Queries
| set | short form | long form | unchecked variant | note |
|---|---|---|---|---|
| |A| | a.len() | |||
| min A, max A | a.min(), a.max() | |||
| ∑(x : x ∈ A) | a.sum() | |||
| A = ∅ | a.is_empty() | |||
| A ⊆ B | a <= b | a.is_subset(b) | ||
| A ⊇ B | a >= b | a.is_superset(b) | ||
| A ⊂ B | a < b | a.is_strict_subset(b) | ||
| A ⊃ B | a > b | a.is_strict_superset(b) | ||
| A ∩ B ≠ ∅ | a.intersects(b) | |||
| A ∩ B = ∅ | a.is_disjoint(b) | |||
| x ∈ A | a.contains(x) | |||
| A = {m, …, n} | a.is_interval() | |||
| pos(x) | a.position(x) | a.position_unchecked(x) | indexed from zero | |
| rank(x) | a.rank(x) | a.rank_unchecked(x) | indexed from one |
§Set operations
| operation | short form | long form | mutating | mutating long form |
|---|---|---|---|---|
| A ∪ B | a | b | a.union(b) | a |= b | a.union_update(b) |
| A ∩ B | a & b | a.intersection(b) | a &= b | a.intersection_update(b) |
| A ∖ B | a - b | a.difference(b) | a -= b | a.difference_update(b) |
| A ∆ B | a ^ b | a.symmetric_difference(b) | a ^= b | a.symmetric_difference_update(b) |
| A ∪ {x} | a + x | a.with(x) | a += x | a.insert(x) |
| A ∖ {x} | a - x | a.without(x) | a -= x | a.remove(x) |
| A ← A ∆ {x} | a.toggle(x) | |||
| A ← ∅ | a.clear() |
§Arithmetic operations
Checked variants return Err(Irrepresentable) if an output element
cannot be represented; truncating variants instead drop any values < 0 or > M. The short
forms are truncating.
| operation | definition | short form | mutating | checked variant | truncating variant |
|---|---|---|---|---|---|
| A + B | {a + b | a ∈ A ∧ b ∈ B} | a + b | a += b | a.sumset(b) | a.truncating_sumset(b) |
| A + {x} | {a + x | a ∈ A} | a << x | a <<= x | a.map_add(x) | a.truncating_map_add(x) |
| A - {x} | {a - x | a ∈ A} | a >> x | a >>= x | a.map_sub(x) | a.truncating_map_sub(x) |
| A ± {x} | {a ± x | a ∈ A} | a.translate(x) | a.truncating_translate(x) | ||
| {∑(x : x ∈ X) | X ⊆ A} | a.subset_sums() | a.truncating_subset_sums() |
§Generation
Generation ordered “by size” (cardinality grows slowly) is slower by a factor of about 10.
| example | iterator yields |
|---|---|
Set::iter_all() | ∅, {0}, {1}, {0, 1}, {2}, {0, 2}, {1, 2}, {0, 1, 2}, {3}, … |
Set::iter_all_by_size() | ∅, {0}, {1}, {2}, …, {M}, {0, 1}, {0, 2}, {1, 2}, …, {M, M - 1}, {0, 1, 2}, … |
Set::iter_all_below(3) | ∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2} |
Set::iter_combinations(4, 2) | {0, 1}, {0, 2}, {1, 2}, {0, 3}, {1, 3}, {2, 3} |
set![2, 4, 6].subsets() | ∅, {2}, {4}, {2, 4}, {6}, {2, 6}, {4, 6}, {2, 4, 6} |
set![2, 4, 6].subsets_by_size() | ∅, {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6} |
set![2, 4, 6].subsets_of_size(2) | {2, 4}, {2, 6}, {4, 6} |
§Installation
Via one of the following cargo commands:
cargo add pibs # with default features
cargo add pibs --no-default-features # without default features
cargo add pibs -F serde # with 'serde' featureOr by adding one of the following lines to Cargo.toml (replace 0.1 with the latest version):
[dependencies]
pibs = "0.1" # with default features
pibs = { version = "0.1", default-features = false } # without default features
pibs = { version = "0.1", features = ["serde"] } # with 'serde' feature§Features and dependencies
pibs is no_std-compatible and its
only non-optional dependency is num_traits.
§Discussion
§Pitfalls
§Two overloads for the plus operator
The + operator has two different meanings: for sets a and b and an element x, a + b
denotes the sumset (Minkowski sum) of a and b, whereas a + x denotes the union of a with
the singleton set containing x:
let a = set![1, 2, 3];
let b = set![4];
let x = 4;
assert_eq!(a + b, set![5, 6, 7]); // sumset
assert_eq!(a + x, set![1, 2, 3, 4]); // singleton union§Bit-length precondition for non-builtin word types
Currently, num_traits provides no trait that exposes the logical bit length of a Word
W at compile time. For this reason, pibs infers the logical bit length from the physical
one. This results in a precondition to using BitSet<W> that:
assert_eq!(size_of::<W>() * 8, W::zero().count_zeros() as usize);§Support for non-builtin word types
The storage word trait Word has a blanket implementation and allows BitSet<W> to be used
with some non-builtin types W, say
bnum::types::U256. This is partially
supported, with the following limitations:
- There is a precondition on the word type
W; see above. - The
Wordtrait may change in the future as new features are added. subsets_of_sizehas a hard limit of 128 on the subset size, regardless ofWordtype.subsets_by_sizewould, in theory, stop after generating all subsets of size 128.From<BitSet<W>>is only implemented forVec<T>whenWis a builtin type.- Testing of non-builtin word types is very limited; benchmarking is non-existent.
§Performance
§Impact of word size
Benchmarking suggests that on a 64 bit system, BitSet operations are often equally fast for
the primitives u32 and u64, while using u8, u16, or u128 for storage can
make them slower by a factor of about two. It is thus recommended to use Set128 only when
needed for capacity, and BitSet<u8> to <u32> only when memory use is a
concern or the platform has registers of the corresponding size. The default Set uses a
usize for best performance.
§Checks and preconditions
As pibs aims for zero-cost abstraction, it prefers preconditions over runtime checks. In a debug build, violating a stated precondition always panics. In a release build, no guarantees with respect to the method’s behavior are made: it may panic or produce unexpected results. Runtime checks are only performed
- if a foreign trait dictates it, or
- if a precondition on a method’s arguments alone is not sufficient to ensure correct operation.
An example of the first condition is try_from, which needs to ensure that
every number obtained from the source collection is at most BitSet::MAX. The second rule
applies to translate: testing whether the outcome is representable
requires knowledge of the set’s extremal elements in addition to the number being added, so the
method takes care of this check and returns a Result. On the other hand, a successful
insert only requires the argument to be within bounds, which is imposed by
a precondition.
Whenever such runtime checks would occur in a release build, pibs offers alternative methods
that omit them. For example, from_unchecked has the precondition
that the source collection only contains representable elements, while
truncating_translate discards irrepresentable sums as a
zero-cost side effect of the shift used to compute the result.
Creation macros such as set! bounds-check relevant arguments at compile time. This
introduces no runtime cost but requires those arguments to be constant expressions.
§Alternatives
The obvious limitation of pibs is that its BitSet can only store numbers less than the bit
length of the underlying primitive. If your numbers can be larger than this but you know a
bound, consider using fixedbitset (SIMD-optimized set
abstraction) or bittle (low-level bit manipulation) instead. If you
don’t know your largest number ahead of time, then bit-set (based on
bit-vec) or roaring (compressed
representation) may suit you.
Modules§
Macros§
- bitset
- Create a
BitSetusing the given primitive type to store the arguments. - set
- Create a
Setcontaining the arguments. - set128
- Create a
Set128containing the arguments.
Structs§
- BitSet
- A high-performance generic bitset that wraps a single primitive integer for storage.
- BitSet
Iter - Iterator returned by
BitSet::iterandBitSet::into_iter. - Subsets
OfSize Iter - Iterator returned by
BitSet::subsets_of_size.
Enums§
Traits§
Type Aliases§
- Element
- Alias for
usize, the default input and output type for the numbers stored in aBitSet. - Set
- Alias for
BitSet<usize>; the set offering the best performance. - Set128
- Alias for
BitSet<u128>; the set with the highest capacity among builtin word types.