The Utote crate provides statically allocated multisets of unsigned
integers. A nightly only
simd feature can also be used to greatly improve
A multiset, also known as a “bag”, is an extension to the concept of set
where elements can occur multiple times. Utote calls the number of times an
element occurs its
count, though the term
multiplicity is more often
used in mathematical descriptions of multisets. All the common operations
on sets have implementations on multisets, so you can
union multisets, along with everything else you would expect to be able
If you have a known number of things that you want to count and do set-like operations on, then this crate will likely be useful to you.
Multiset can only keep track of uint counters, but if you have a fixed
number of non-uint items then pairing a
HashMap with a
provide significant performance benefits.
use std::collections::HashMap; use utote::Multiset; let mut item_map: HashMap<&str, usize> = HashMap::new(); item_map.insert("foo", 0); item_map.insert("bar", 1); let multiset: Multiset<u16, 2> = Multiset::empty(); // do a whole load of stuff to the multiset... let bar_count: &u16 = multiset.get(*item_map.get("bar").unwrap()).unwrap();
SIMD and Generics
Due to remaining rough edges in the const generic feature there is an extra
constraint required when using
Multiset generically. The const values for
the number of lanes for the simd types of a counter type need to be
constrained. The constraint:
where [(); T::L128 * T::L256 * T::LF]: Sized
is the most simple to add.
- simd: Requires nightly rust toolchain. Enables simd implementations using the packed_simd crate crate and unsatble features: const_generics and const_evaluatable_checked.
- rand: Enables
choose_randommethods for multiset structs using the rand crate.
The largest factor in multiset performance is the size of the multiset, the larger the slower it is. The simplest way to improve performance is to keep them as small as possible.
The most simple way to improve performance is to use the simd
implementations by turning on the
simd feature of Utote. If you can use
the nightly toolchain then this should be utilised.
A stack allocated multiset of unsigned integers.
The Counter trait simplifies the use of Multiset with generics. This trait is sealed and not implementable outside of this crate.