Skip to content

Instantly share code, notes, and snippets.

@fstab
Created February 2, 2022 16:40
Show Gist options
  • Save fstab/f1f90633ffc3659f99372a1df06e58c1 to your computer and use it in GitHub Desktop.
Save fstab/f1f90633ffc3659f99372a1df06e58c1 to your computer and use it in GitHub Desktop.
Source Code for the CKMS Blog Post

The space requirements for CKMS quantiles were evaluated by adding the following test to CKMSQuantilesTest in client_java.

@Test
public void testBlog() {
    Random random = new Random(0);
    Quantile q05 = new Quantile(0.5, 0.01);
    Quantile q95 = new Quantile(0.95, 0.005);
    Quantile q99 = new Quantile(0.99, 0.001);
    dump(random, 1000, q95);
    dump(random, 10*1000, q95);
    dump(random, 100*1000, q95);
    dump(random, 1000*1000, q95);
    dump(random, 10*1000*1000, q95);
    dump(random, 100*1000*1000, q95);
    dump(random, 1000, q95, q99);
    dump(random, 10*1000, q95, q99);
    dump(random, 100*1000, q95, q99);
    dump(random, 1000*1000, q95, q99);
    dump(random, 10*1000*1000, q95, q99);
    dump(random, 100*1000*1000, q95, q99);
    dump(random, 1000, q05, q95, q99);
    dump(random, 10*1000, q05, q95, q99);
    dump(random, 100*1000, q05, q95, q99);
    dump(random, 1000*1000, q05, q95, q99);
    dump(random, 10*1000*1000, q05, q95, q99);
    dump(random, 100*1000*1000, q05, q95, q99);
}   

private void dump(Random random, int n, Quantile... qs) {
    System.out.print("dump");
    for (Quantile q : qs) {
        System.out.print(" " + q.quantile);
    }   
    System.out.print(" " + n + ": "); 
    CKMSQuantiles ckms = new CKMSQuantiles(qs);
    List<Double> input = shuffledValues(n, random);
    for (double value : input) {
        ckms.insert(value);
    }   
    validateResults(ckms);
    System.out.println(ckms.samples.size() + " of " + ckms.n);
}

Note that as of today the implementation is still in the ckms branch but it will be merged soon.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment