zw-fast-quantile

Zhang Wang快速近似分位数算法在Rust中的实现：[参考链接](http://web.cs.ucla.edu/~weiwang/paper/SSDBM07_2.pdf)。这是原始算法，它启发了Tensorflow Boosted Trees中的技术：Tensorflow Boosted Trees

安装

将以下内容添加到您的 Cargo.toml

[dependencies]
zw-fast-quantile = "0.2"

然后就可以使用了。如果您使用的是Rust 2015，您还需要在crate根目录中将 extern crate zw-fast-quantile 添加到您的crate中。

示例

该库中有两种实现：FixedSizeEpsilonSummary 是在已知流大小的条件下使用的，而 UnboundEpsilonSummary 是用于未知大小的流。您可以调整自己的错误率 epsilon 以在空间和准确性之间进行权衡。

let epsilon = 0.1;
let n = 10;
let mut s = FixedSizeEpsilonSummary::new(n, epsilon);
for i in 1..=n {
    s.update(i);
}

let ans = s.query(0.0);
let expected = 1;
assert!(expected == ans);

let epsilon = 0.1;
let n = 10;
let mut s = UnboundEpsilonSummary::new(epsilon);
for i in 1..=n {
    s.update(i);
}

let ans = s.query(0.0);
let expected = 1;
assert!(expected == ans);

基准测试

我们对GK01在quantiles中的实现进行了基准测试。为了测试UPDATE，我们以0.01的错误率按顺序插入5000个值。GK01比ZW慢约2.6倍。

zw unbound quantile update
                        time:   [60.780 us 60.855 us 60.936 us]
                        change: [-1.4032% -0.9510% -0.5005%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
  2 (2.00%) high mild
  6 (6.00%) high severe

gk quantile update      time:   [156.84 us 157.02 us 157.24 us]
                        change: [-0.1907% -0.0503% +0.0969%] (p = 0.50 > 0.05)
                        No change in performance detected.
Found 11 outliers among 100 measurements (11.00%)
  6 (6.00%) high mild
  5 (5.00%) high severe

至于查询时间，我们查询了从0.0到1.0的11个分位数。GK01比ZW慢约1.5倍。

zw unbound quantile query
                        time:   [229.62 ns 230.16 ns 230.77 ns]
                        change: [+1.3422% +1.8105% +2.2504%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 11 outliers among 100 measurements (11.00%)
  3 (3.00%) high mild
  8 (8.00%) high severe

gk quantile query       time:   [350.21 ns 350.48 ns 350.76 ns]
                        change: [-0.4638% -0.3109% -0.1670%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 8 outliers among 100 measurements (8.00%)
  1 (1.00%) low severe
  2 (2.00%) high mild
  5 (5.00%) high severe