cmsketch

Rust 中的计数最小草图实现。

灵感来自 Facebook/CacheLib 和 Caffeine。

使用方法

use cmsketch::CMSketchU32;

const ERROR: f64 = 0.01;
const CONFIDENCE: f64 = 0.95;

fn main() {
    let mut cms = CMSketchU32::new(ERROR, CONFIDENCE);
    for i in 0..10 {
        for _ in 0..i {
            cms.inc(i);
        }
    }
    
    for i in 0..10 {
        assert!(cms.estimate(i) >= i as u32);
    }
    
    cms.halve();
    
    for i in 0..10 {
        assert!(cms.estimate(i) >= (i as f64 * 0.5) as u32);
    }
}

路线图

• simd halve
• 基准测试

lib.rs:

一种概率计数数据结构，在达到计数器容量之前，永远不会对项目进行低估。它是一种表格结构，深度是哈希数，宽度是唯一项目的数量。当插入一个键时，每一行的哈希函数用于生成该行的索引。然后在该索引处增加该元素的计数。结果，插入一个键将增加每一行中的不同索引。查询计数返回这些元素的最小值，因为某些哈希可能会冲突。

用户应同步对数据结构的并发访问。

例如。插入(1) hash1(1) = 2 -> 增加行 1，索引 2 hash2(1) = 5 -> 增加行 2，索引 5 hash3(1) = 3 -> 增加行 3，索引 3 等。

使用方法

use cmsketch::CMSketchU32;

const ERROR: f64 = 0.01;
const CONFIDENCE: f64 = 0.95;

fn main() {
    let mut cms = CMSketchU32::new(ERROR, CONFIDENCE);
    for i in 0..10 {
        for _ in 0..i {
            cms.inc(i);
        }
    }
    
    for i in 0..10 {
        assert!(cms.estimate(i) >= i as u32);
    }
    
    cms.halve();
    
    for i in 0..10 {
        assert!(cms.estimate(i) >= (i as f64 * 0.5) as u32);
    }
}