cmsketch/lib.rs
1// Copyright 2023 MrCroxx
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! A probabilistic counting data structure that never undercounts items before
16//! it hits counter's capacity. It is a table structure with the depth being the
17//! number of hashes and the width being the number of unique items. When a key
18//! is inserted, each row's hash function is used to generate the index for that
19//! row. Then the element's count at that index is incremented. As a result, one
20//! key being inserted will increment different indices in each row. Querying the
21//! count returns the minimum values of these elements since some hashes might collide.
22//!
23//!
24//! Users are supposed to synchronize concurrent accesses to the data structure.
25//!
26//! E.g. insert(1)
27//! hash1(1) = 2 -> increment row 1, index 2
28//! hash2(1) = 5 -> increment row 2, index 5
29//! hash3(1) = 3 -> increment row 3, index 3
30//! etc.
31//!
32//! # Usage
33//!
34//! ```
35//! use cmsketch::CMSketchU32;
36//!
37//! const ERROR: f64 = 0.01;
38//! const CONFIDENCE: f64 = 0.95;
39//!
40//! fn main() {
41//! let mut cms = CMSketchU32::new(ERROR, CONFIDENCE);
42//! for i in 0..10 {
43//! for _ in 0..i {
44//! cms.inc(i);
45//! }
46//! }
47//!
48//! for i in 0..10 {
49//! assert!(cms.estimate(i) >= i as u32);
50//! }
51//!
52//! cms.halve();
53//!
54//! for i in 0..10 {
55//! assert!(cms.estimate(i) >= (i as f64 * 0.5) as u32);
56//! }
57//! }
58//! ```
59
60mod base;
61pub use base::*;
62
63mod atomic;
64pub use atomic::*;