Struct CpcSketch 

pub struct CpcSketch { /* private fields */ }

A CPC (Compressed Probabilistic Counting) sketch: estimates the number of distinct items added via update_*. Unlike Theta’s ThetaSketch, there is no separate compact/wrapped variant — this single type is both the mutable/update type and the serializable type, since CPC’s serialized form is always compressed by construction. Build one with CpcSketchBuilder.

Implementations

impl CpcSketch

pub fn deserialize(bytes: &[u8]) -> Result<Self, SketchError>

Reconstructs a sketch from bytes produced by Self::serialize.

Examples found in repository

examples/bench_cpc_update.rs (line 280)

fn bench_serde(items: u64, reps: usize) {
    let mut sketch = build();
    for key in 0..items {
        sketch.update_u64(key);
    }
    let reference = sketch.serialize();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize = || CpcSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/cpc.rs (line 59)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

pub fn update_u64(&mut self, value: u64)

Adds a u64 value to the sketch.

Examples found in repository

examples/bench_cpc_update.rs (line 204)

fn bench_distinct(items: u64, reps: usize) {
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for key in 0..items {
            sketch.update_u64(key);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("distinct", items, &passes);
}

fn bench_hot(items: u64, reps: usize) {
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for i in 0..items {
            sketch.update_u64(i % HOT_KEY_SPACE);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("hot", items, &passes);
}

fn bench_str(items: u64, reps: usize) {
    let keys = string_keys();
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for i in 0..items {
            sketch.update_str(&keys[(i % STR_KEY_SPACE) as usize]);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("str", items, &passes);
}

/// Serialization, measured per call rather than per item: its cost tracks the
/// serialized size, which at `lg_k = 12` is the same at every ladder rung.
///
/// The sketch is built once and shared by both directions and every rep.
/// Serializing does not mutate it, so unlike the update scenarios there is no
/// state that a second rep would find already dirtied -- and rebuilding at the
/// 100M rung would cost more than the measurement itself.
fn bench_serde(items: u64, reps: usize) {
    let mut sketch = build();
    for key in 0..items {
        sketch.update_u64(key);
    }
    let reference = sketch.serialize();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize = || CpcSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/cpc.rs (line 18)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

pub fn update_i64(&mut self, value: i64)

Adds an i64 value to the sketch.

pub fn update_u32(&mut self, value: u32)

Adds a u32 value to the sketch.

pub fn update_i32(&mut self, value: i32)

Adds an i32 value to the sketch.

pub fn update_u16(&mut self, value: u16)

Adds a u16 value to the sketch.

pub fn update_i16(&mut self, value: i16)

Adds an i16 value to the sketch.

pub fn update_u8(&mut self, value: u8)

Adds a u8 value to the sketch.

pub fn update_i8(&mut self, value: i8)

Adds an i8 value to the sketch.

pub fn update_f64(&mut self, value: f64)

Adds an f64 value to the sketch.

pub fn update_f32(&mut self, value: f32)

Adds an f32 value to the sketch.

pub fn update_str(&mut self, value: &str)

Adds a string value to the sketch.

Examples found in repository

examples/bench_cpc_update.rs (line 239)

fn bench_str(items: u64, reps: usize) {
    let keys = string_keys();
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for i in 0..items {
            sketch.update_str(&keys[(i % STR_KEY_SPACE) as usize]);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("str", items, &passes);
}

pub fn update_bytes(&mut self, value: &[u8])

Adds an arbitrary byte slice to the sketch.

pub fn is_empty(&self) -> bool

Returns true if no items have been added to this sketch.

pub fn get_estimate(&self) -> f64

Returns the current estimate of the number of distinct items added.

Examples found in repository

examples/bench_cpc_update.rs (line 209)

fn bench_distinct(items: u64, reps: usize) {
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for key in 0..items {
            sketch.update_u64(key);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("distinct", items, &passes);
}

fn bench_hot(items: u64, reps: usize) {
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for i in 0..items {
            sketch.update_u64(i % HOT_KEY_SPACE);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("hot", items, &passes);
}

fn bench_str(items: u64, reps: usize) {
    let keys = string_keys();
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let mut sketch = build();
        let start = Instant::now();
        for i in 0..items {
            sketch.update_str(&keys[(i % STR_KEY_SPACE) as usize]);
        }
        let elapsed = start.elapsed();
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report("str", items, &passes);
}

/// Serialization, measured per call rather than per item: its cost tracks the
/// serialized size, which at `lg_k = 12` is the same at every ladder rung.
///
/// The sketch is built once and shared by both directions and every rep.
/// Serializing does not mutate it, so unlike the update scenarios there is no
/// state that a second rep would find already dirtied -- and rebuilding at the
/// 100M rung would cost more than the measurement itself.
fn bench_serde(items: u64, reps: usize) {
    let mut sketch = build();
    for key in 0..items {
        sketch.update_u64(key);
    }
    let reference = sketch.serialize();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize = || CpcSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/cpc.rs (line 31)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

pub fn get_lower_bound(&self, num_std_dev: u8) -> Result<f64, SketchError>

Returns the lower bound of the confidence interval around Self::get_estimate, for the given number of standard deviations (1, 2, or 3, corresponding to roughly 67%, 95%, and 99% confidence — upstream calls this parameter kappa). Returns SketchError::InvalidConfig for any other value.

Examples found in repository

examples/cpc.rs (line 39)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

pub fn get_upper_bound(&self, num_std_dev: u8) -> Result<f64, SketchError>

Returns the upper bound of the confidence interval around Self::get_estimate. See Self::get_lower_bound for the meaning of num_std_dev.

Examples found in repository

examples/cpc.rs (line 40)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

pub fn get_lg_k(&self) -> u8

Returns the lg_k this sketch was built with.

pub fn to_string_summary(&self) -> String

Returns a human-readable, multi-line summary of this sketch’s internal state — useful for debugging, not for parsing.

pub fn serialize(&self) -> Vec<u8>

Serializes this sketch to bytes. CPC’s on-wire format is always compressed, so there is only this one serialization method (unlike Theta’s separate compressed/uncompressed formats).

Examples found in repository

examples/bench_cpc_update.rs (line 262)

fn bench_serde(items: u64, reps: usize) {
    let mut sketch = build();
    for key in 0..items {
        sketch.update_u64(key);
    }
    let reference = sketch.serialize();

    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0usize;
        for _ in 0..SER_CALLS {
            total += black_box(sketch.serialize()).len();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: sketch.get_estimate(),
        });
    }
    report_bytes("ser", items, SER_CALLS, &passes, reference.len());

    let deserialize = || CpcSketch::deserialize(&reference).expect("the bytes came from serialize");
    let mut passes = Vec::with_capacity(reps);
    for _ in 0..reps {
        let start = Instant::now();
        let mut total = 0.0;
        for _ in 0..DESER_CALLS {
            total += deserialize().get_estimate();
        }
        let elapsed = start.elapsed();
        black_box(total);
        passes.push(Pass {
            elapsed,
            estimate: deserialize().get_estimate(),
        });
    }
    report_bytes("deser", items, DESER_CALLS, &passes, reference.len());
}

examples/cpc.rs (line 58)

fn main() {
    // A sketch estimates the number of distinct items seen, using bounded
    // memory regardless of how many items are added. `lg_k` (4..=26)
    // trades memory for accuracy: higher values are more accurate but use
    // more space.
    let mut visitors_day1 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 0..10_000u64 {
        visitors_day1.update_u64(id);
    }

    let mut visitors_day2 = CpcSketchBuilder::new()
        .lg_k(11)
        .build()
        .expect("valid lg_k");
    for id in 5_000..15_000u64 {
        visitors_day2.update_u64(id);
    }

    println!(
        "Day 1 unique visitors (estimate): {:.0}",
        visitors_day1.get_estimate()
    );
    println!(
        "Day 2 unique visitors (estimate): {:.0}",
        visitors_day2.get_estimate()
    );
    println!(
        "Day 1, 95% confidence interval: [{:.0}, {:.0}]",
        visitors_day1.get_lower_bound(2).unwrap(),
        visitors_day1.get_upper_bound(2).unwrap()
    );

    // CpcUnion merges multiple sketches into one, e.g. combining per-day
    // counts into a total distinct count across both days.
    let mut union = CpcUnionBuilder::new().lg_k(11).build().expect("valid lg_k");
    union.update(&visitors_day1);
    union.update(&visitors_day2);
    let total_unique = union.get_result();
    println!(
        "Total unique visitors across both days (true count = 15000): {:.0}",
        total_unique.get_estimate()
    );

    // Sketches can be serialized to bytes (e.g. to store or send over the
    // network) and reconstructed later. CPC's serialized form is always
    // compressed, so there's a single serialize()/deserialize() pair
    // (unlike Theta, which has separate compressed/uncompressed formats).
    let bytes = visitors_day1.serialize();
    let restored = CpcSketch::deserialize(&bytes).expect("valid sketch bytes");
    println!(
        "serialized day-1 sketch to {} bytes and restored successfully (estimate {:.0})",
        bytes.len(),
        restored.get_estimate()
    );
}

Trait Implementations

impl Send for CpcSketch