在本地测试中，每点的插入时间约为4微秒，方差为7%。这意味着每秒可以插入250k个点。

Misra Gries - ε近似频率计数

Misra-Gries计算一个ε近似频率计数，用于N个元素的流。输出是k个最频繁的元素。

1. 近似计数f'[e]小于元素e的真实频率f[e]，但最多为εN，即(f[e] - εN) ≤ f'[e] ≤ f[e]
2. 任何频率f[e] ≥ εN的元素e都会出现在结果集中

误差界限ε = 1/(k+1)，其中k是算法中使用的计数器数量。当k = 1时，即单个计数器，该算法等同于Boyer-Moore多数算法。

如果您想检查至少出现εN次的元素，您将需要进行第二次遍历来计算结果集中值的精确频率，这可以在常数空间中完成。

use quantiles::misra_gries::*;

let k: usize = 3;
let numbers: Vec<u32> = vec![1,3,2,1,3,4,3,1,2,1];
let counts = misra_gries(numbers.iter(), k);
let bound = numbers.len() / (k+1);
let in_range = |f_expected: usize, f_approx: usize| {
  f_approx <= f_expected &&
  (bound >= f_expected || f_approx >= (f_expected - bound))
};
assert!(in_range(4usize, *counts.get(&1).unwrap()));
assert!(in_range(2usize, *counts.get(&2).unwrap()));
assert!(in_range(3usize, *counts.get(&3).unwrap()));

Greenwald Khanna - ε近似分位数

Greenwald Khanna计算ε近似分位数。如果所需的分位数是φ，则ε近似分位数是介于⌊(φ-ε)N⌋和⌊(φ+ε)N⌋之间的任何元素

流摘要数据结构可以处理最多max[usize]个观察结果。

开始和结束分位数分别被限制在观察到的最小和最大元素。

此页解释了理论： http://www.mathcs.emory.edu/~cheung/Courses/584-StreamDB/Syllabus/08-Quantile/Greenwald.html

use quantiles::greenwald_khanna::*;

let epsilon = 0.01;

let mut stream = Stream::new(epsilon);

let n = 1001;
for i in 1..n {
    stream.insert(i);
}
let in_range = |phi: f64, value: u32| {
  let lower = ((phi - epsilon) * (n as f64)) as u32;
  let upper = ((phi + epsilon) * (n as f64)) as u32;
  (epsilon > phi || lower <= value) && value <= upper
};
assert!(in_range(0f64, *stream.quantile(0f64)));
assert!(in_range(0.1f64, *stream.quantile(0.1f64)));
assert!(in_range(0.2f64, *stream.quantile(0.2f64)));
assert!(in_range(0.3f64, *stream.quantile(0.3f64)));
assert!(in_range(0.4f64, *stream.quantile(0.4f64)));
assert!(in_range(1f64, *stream.quantile(1f64)));

升级

0.2 -> 0.3

本版本引入了两个新算法：“Greenwald Khanna”和“Misra Gries”。现有的CKMS已从根目录移动到自己的子模块。您需要更新您的导入，从

use quantiles::CMKS;

到

use quantiles::ckms::CKMS;