Skip to main content

Crate pibs

Crate pibs 

Source
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; ...].

setshort formlong formchecked 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 iterSet::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

setshort formlong formunchecked variantnote
|A|a.len()
min A, max Aa.min(), a.max()
∑(x : x ∈ A)a.sum()
A = ∅a.is_empty()
A ⊆ Ba <= ba.is_subset(b)
A ⊇ Ba >= ba.is_superset(b)
A ⊂ Ba < ba.is_strict_subset(b)
A ⊃ Ba > ba.is_strict_superset(b)
A ∩ B ≠ ∅a.intersects(b)
A ∩ B = ∅a.is_disjoint(b)
x ∈ Aa.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

operationshort formlong formmutatingmutating long form
A ∪ Ba | ba.union(b)a |= ba.union_update(b)
A ∩ Ba & ba.intersection(b)a &= ba.intersection_update(b)
A ∖ Ba - ba.difference(b)a -= ba.difference_update(b)
A ∆ Ba ^ ba.symmetric_difference(b)a ^= ba.symmetric_difference_update(b)
A ∪ {x}a + xa.with(x)a += xa.insert(x)
A ∖ {x}a - xa.without(x)a -= xa.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.

operationdefinitionshort formmutatingchecked varianttruncating variant
A + B{a + b | a ∈ A ∧ b ∈ B}a + ba += ba.sumset(b)a.truncating_sumset(b)
A + {x}{a + x | a ∈ A}a << xa <<= xa.map_add(x)a.truncating_map_add(x)
A - {x}{a - x | a ∈ A}a >> xa >>= xa.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.

exampleiterator 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' feature

Or 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

featuredefaultimplements
allocyesconversion to and from Vec
serdeno(de)serialization via serde

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 Word trait may change in the future as new features are added.
  • subsets_of_size has a hard limit of 128 on the subset size, regardless of Word type.
  • subsets_by_size would, in theory, stop after generating all subsets of size 128.
  • From<BitSet<W>> is only implemented for Vec<T> when W is 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

  1. if a foreign trait dictates it, or
  2. 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§

prelude
Re-exports BitSet, Set, Set128, and their creation macros.

Macros§

bitset
Create a BitSet using the given primitive type to store the arguments.
set
Create a Set containing the arguments.
set128
Create a Set128 containing the arguments.

Structs§

BitSet
A high-performance generic bitset that wraps a single primitive integer for storage.
BitSetIter
Iterator returned by BitSet::iter and BitSet::into_iter.
SubsetsOfSizeIter
Iterator returned by BitSet::subsets_of_size.

Enums§

Error
Errors returned for BitSet operations.

Traits§

Word
A primitive unsigned integer that BitSet can use for storage.

Type Aliases§

Element
Alias for usize, the default input and output type for the numbers stored in a BitSet.
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.