Struct quantiles::ckms::CKMS

pub struct CKMS<T: Copy> { /* fields omitted */ }

A structure to provide approximate quantiles queries in bounded memory and with bounded error.

Methods

impl<T: Copy + PartialOrd + Debug + Add<Output=T>> CKMS<T>

fn new(error: f64) -> CKMS<T>

Create a new CKMS

A CKMS is meant to answer quantile queries with a known error bound. If the error passed here is ε and there have been n items inserted into CKMS then for any quantile query Φ the deviance from the true quantile will be +/- εΦn.

For an error ε this structure will require T*(floor(1/(2*ε)) + O(1/ε log εn)) + f64 + usize + usize words of storage.

Examples

use quantiles::ckms::CKMS;

let mut ckms = CKMS::<u64>::new(0.001);
for i in 1..1001 {
    ckms.insert(i as u64);
}
assert_eq!(ckms.query(0.0), Some((1, 1)));
assert_eq!(ckms.query(0.998), Some((998, 998)));
assert_eq!(ckms.query(0.999), Some((999, 999)));
assert_eq!(ckms.query(1.0), Some((1000, 1000)));

error must but a value between 0 and 1, exclusive of both extremes. If you input an error <= 0.0 CKMS will assign an error of 0.00000001. Likewise, if your error is >= 1.0 CKMS will assign an error of 0.99.

fn last(&self) -> Option<T>

Return the last element added to the CKMS

Example

use quantiles::ckms::CKMS;

let mut ckms = CKMS::new(0.1);
ckms.insert(1.0);
ckms.insert(2.0);
ckms.insert(3.0);
assert_eq!(Some(3.0), ckms.last());

fn sum(&self) -> Option<T>

Return the sum of the elements added to the CKMS

Example

use quantiles::ckms::CKMS;

let mut ckms = CKMS::new(0.1);
ckms.insert(1.0);
ckms.insert(2.0);
ckms.insert(3.0);
assert_eq!(Some(6.0), ckms.sum());

fn insert(&mut self, v: T)

Insert a T into the CKMS

Insertion will gradulally shift the approximate quantiles. This implementation is biased toward fast writes and slower queries. Storage may grow gradually, as defined in the module-level documentation, but will remain bounded.

fn query(&self, q: f64) -> Option<(usize, T)>

Query CKMS for a ε-approximate quantile

This function returns an approximation to the true quantile-- +/- εΦn --for the points inserted. Argument q is valid 0. <= q <= 1.0. The minimum and maximum quantile, corresponding to 0.0 and 1.0 respectively, are always known precisely.

Return

Examples

use quantiles::ckms::CKMS;

let mut ckms = CKMS::<u32>::new(0.001);
for i in 0..1000 {
    ckms.insert(i as u32);
}

assert_eq!(ckms.query(0.0), Some((1, 0)));
assert_eq!(ckms.query(0.998), Some((998, 997)));
assert_eq!(ckms.query(1.0), Some((1000, 999)));

fn count(&self) -> usize

Query CKMS for the count of its points

This function returns the total number of points seen over the lifetime of the datastructure, not the number of points currently stored in the structure.

Examples

use quantiles::ckms::CKMS;

let mut ckms = CKMS::<u32>::new(0.001);
for i in 0..1000 {
    ckms.insert(i as u32);
}

assert_eq!(ckms.count(), 1000);

fn into_vec(self) -> Vec<T>

Retrieve a representative vector of points

This function returns a represenative sample of points from the CKMS. Doing so consumes the CKMS.

Examples

use quantiles::ckms::CKMS;

let mut ckms = CKMS::<u32>::new(0.1);
for i in 0..10 {
    ckms.insert(i as u32);
}

assert_eq!(ckms.into_vec(), vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);

Trait Implementations

impl<T: Debug + Copy> Debug for CKMS<T>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: PartialEq + Copy> PartialEq for CKMS<T>

fn eq(&self, __arg_0: &CKMS<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, __arg_0: &CKMS<T>) -> bool

This method tests for !=.

impl<T: Clone + Copy> Clone for CKMS<T>

fn clone(&self) -> CKMS<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> AddAssign for CKMS<T> where T: Copy + Add<Output=T> + PartialOrd + Debug

fn add_assign(&mut self, rhs: CKMS<T>)

The method for the += operator