This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 8ba1022 feat(tdigest): Add batch quantile queries (#275)
8ba1022 is described below
commit 8ba102243a189d3281463ee1544fe0b682e73ca4
Author: Ryu <[email protected]>
AuthorDate: Sat Oct 3 18:16:15 2026 +0200
feat(tdigest): Add batch quantile queries (#275)
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 2 +
benchmarks/tdigest/query.rs | 40 +++-
datasketches/src/lib.rs | 1 +
datasketches/src/tdigest/sketch.rs | 224 +++++++++++++++++------
tests-integration/tests/tdigest_test/property.rs | 48 ++++-
tests-integration/tests/tdigest_test/sketch.rs | 178 ++++++++++++++++++
6 files changed, 432 insertions(+), 61 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index ff73f71..524755e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -13,6 +13,7 @@ All significant changes to this project will be documented in
this file.
### New features
* `KllSketch` is now available behind the `kll` feature, with rank, quantile,
PMF, and CDF queries, merging, serialization, custom ordered item types, and a
`KllFloat` adapter for non-NaN floating-point values.
+* Add `TDigestMut::quantiles` and `TDigest::quantiles` for querying several
ranks in one centroid scan while preserving input order.
### Improvements
@@ -43,6 +44,7 @@ All significant changes to this project will be documented in
this file.
* `ReqSketch::cdf` and its sorted view now preserve the rank at each split
point and end at exactly `1.0`, avoiding extra rounding from accumulating PMF
values.
* `TDigestMut` updates and merges now panic without changing the digest if the
total weight would exceed `u64::MAX`, including in release builds.
* `TDigestMut::merge` now preserves the true minimum and maximum from both
inputs, including compressed digests.
+* `TDigest` and `TDigestMut` quantile queries no longer extrapolate above the
stored maximum when large total weights cause rounding near rank `1.0`.
* `TDigest` and `TDigestMut` deserialization now returns `InvalidData` for
invalid flags or extrema, out-of-range values, unsorted centroids, or non-empty
images with no stored values.
## v0.5.0 (2026-09-04)
diff --git a/benchmarks/tdigest/query.rs b/benchmarks/tdigest/query.rs
index 0981657..ae36977 100644
--- a/benchmarks/tdigest/query.rs
+++ b/benchmarks/tdigest/query.rs
@@ -18,6 +18,9 @@
use divan::Bencher;
use divan::black_box;
use divan::counter::ItemsCount;
+use rand::SeedableRng;
+use rand::rngs::StdRng;
+use rand::seq::SliceRandom;
use super::support::prepared_digest;
@@ -45,14 +48,37 @@ fn cdf_100(bencher: Bencher) {
.bench_local(|| black_box(&digest).cdf(black_box(&split_points)));
}
-#[divan::bench]
-fn quantiles_2_sequential(bencher: Bencher) {
+#[divan::bench(consts = [true, false], args = [2, 6, 100])]
+fn quantiles_sequential<const SORTED: bool>(bencher: Bencher, num_ranks:
usize) {
let digest = prepared_digest();
+ let ranks = query_ranks(num_ranks, SORTED);
- bencher.bench_local(|| {
- [
- black_box(&digest).quantile(black_box(0.5)),
- black_box(&digest).quantile(black_box(0.95)),
- ]
+ bencher.counter(ItemsCount::new(num_ranks)).bench_local(|| {
+ for &rank in black_box(&ranks) {
+ black_box(black_box(&digest).quantile(black_box(rank)));
+ }
});
}
+
+#[divan::bench(consts = [true, false], args = [2, 6, 100])]
+fn quantiles_batch<const SORTED: bool>(bencher: Bencher, num_ranks: usize) {
+ let digest = prepared_digest();
+ let ranks = query_ranks(num_ranks, SORTED);
+
+ bencher
+ .counter(ItemsCount::new(num_ranks))
+ .bench_local(|| black_box(&digest).quantiles(black_box(&ranks)));
+}
+
+fn query_ranks(num_ranks: usize, sorted: bool) -> Vec<f64> {
+ let mut ranks = (1..=num_ranks)
+ .map(|rank| rank as f64 / (num_ranks + 1) as f64)
+ .collect::<Vec<_>>();
+ if !sorted {
+ ranks.shuffle(&mut StdRng::seed_from_u64(42));
+ if ranks.is_sorted() {
+ ranks.reverse();
+ }
+ }
+ ranks
+}
diff --git a/datasketches/src/lib.rs b/datasketches/src/lib.rs
index b4ff016..6c0f539 100644
--- a/datasketches/src/lib.rs
+++ b/datasketches/src/lib.rs
@@ -63,6 +63,7 @@
#![cfg_attr(docsrs, feature(doc_cfg))]
#![deny(missing_docs)]
+extern crate core;
// See https://github.com/apache/datasketches-rust/issues/28 for more
information.
#[cfg(target_endian = "big")]
diff --git a/datasketches/src/tdigest/sketch.rs
b/datasketches/src/tdigest/sketch.rs
index e0d5953..317e61a 100644
--- a/datasketches/src/tdigest/sketch.rs
+++ b/datasketches/src/tdigest/sketch.rs
@@ -514,7 +514,10 @@ impl TDigestMut {
/// assert!((1.0..=3.0).contains(&median));
/// ```
pub fn quantile(&mut self, rank: f64) -> Option<f64> {
- assert!((0.0..=1.0).contains(&rank), "rank must be in [0.0, 1.0]");
+ assert!(
+ (0.0..=1.0).contains(&rank),
+ "rank must be in [0.0, 1.0]; got {rank}"
+ );
if self.is_empty() {
return None;
@@ -523,6 +526,21 @@ impl TDigestMut {
self.view().quantile(rank)
}
+ /// Returns the quantiles described by [`TDigest::quantiles`].
+ ///
+ /// # Panics
+ ///
+ /// Panics if any rank is outside `[0.0, 1.0]`.
+ pub fn quantiles(&mut self, ranks: &[f64]) -> Option<Vec<f64>> {
+ check_ranks(ranks);
+
+ if self.is_empty() {
+ return None;
+ }
+
+ self.view().quantiles(ranks)
+ }
+
/// Serializes this mutable t-digest to bytes.
///
/// # Examples
@@ -1274,6 +1292,35 @@ impl TDigest {
self.view().quantile(rank)
}
+ /// Computes approximate quantiles for the given normalized ranks.
+ ///
+ /// Ranks in nondecreasing order are answered with one centroid scan.
Ranks in any other order
+ /// are accepted and results are returned in the same order as the input.
+ ///
+ /// Returns `None` if this t-digest is empty.
+ ///
+ /// # Panics
+ ///
+ /// Panics if any rank is outside `[0.0, 1.0]`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// use datasketches::tdigest::TDigestMut;
+ ///
+ /// let mut sketch = TDigestMut::new(100).unwrap();
+ /// for value in [1.0, 2.0, 3.0] {
+ /// sketch.update(value);
+ /// }
+ /// let digest = sketch.freeze();
+ /// let quantiles = digest.quantiles(&[0.25, 0.5, 0.75]).unwrap();
+ /// assert_eq!(quantiles.len(), 3);
+ /// ```
+ pub fn quantiles(&self, ranks: &[f64]) -> Option<Vec<f64>> {
+ check_ranks(ranks);
+ self.view().quantiles(ranks)
+ }
+
/// Converts this immutable t-digest into a mutable one.
///
/// # Examples
@@ -1441,57 +1488,132 @@ impl TDigestView<'_> {
return None;
}
+ let mut quantile = [0.];
+ self.fill_quantiles(std::iter::once((0, rank)), &mut quantile);
+ Some(quantile[0])
+ }
+
+ fn quantiles(&self, ranks: &[f64]) -> Option<Vec<f64>> {
+ debug_assert!(
+ ranks.iter().all(|rank| (0.0..=1.0).contains(rank)),
+ "ranks must be in [0.0, 1.0]"
+ );
+
+ if self.centroids.is_empty() {
+ return None;
+ }
+
+ let mut quantiles = vec![0.; ranks.len()];
+ if ranks.is_sorted() {
+ self.fill_quantiles(ranks.iter().copied().enumerate(), &mut
quantiles);
+ return Some(quantiles);
+ }
+
+ // The scan only moves forward. Sort indices so queries become
monotonic without changing
+ // the caller's output order.
+ let mut rank_order = (0..ranks.len()).collect::<Vec<_>>();
+ rank_order.sort_unstable_by(|&left, &right| {
+ // Ranks have already been validated, so neither value can be NaN.
+ ranks[left].partial_cmp(&ranks[right]).unwrap()
+ });
+ self.fill_quantiles(
+ rank_order.into_iter().map(|index| (index, ranks[index])),
+ &mut quantiles,
+ );
+ Some(quantiles)
+ }
+
+ /// Answers nondecreasing ranks at their original output indices.
+ fn fill_quantiles(
+ &self,
+ ranks: impl DoubleEndedIterator<Item = (usize, f64)>,
+ quantiles: &mut [f64],
+ ) {
if self.centroids.len() == 1 {
- return Some(self.centroids[0].mean);
+ quantiles.fill(self.centroids[0].mean);
+ return;
}
- // at least 2 centroids
let centroids_weight = self.centroids_weight as f64;
- let num_centroids = self.centroids.len();
- let weight = rank * centroids_weight;
- if weight < 1. {
- return Some(self.min);
- }
- if weight > centroids_weight - 1. {
- return Some(self.max);
- }
- let first_weight = self.centroids[0].weight();
- if first_weight > 1. && weight < first_weight / 2. {
- return Some(
- self.min
- + (((weight - 1.) / ((first_weight / 2.) - 1.))
- * (self.centroids[0].mean - self.min)),
- );
- }
- let last_weight = self.centroids[num_centroids - 1].weight();
- if last_weight > 1. && (centroids_weight - weight <= last_weight / 2.)
{
- if last_weight == 2. {
- return Some(self.max);
+ let mut queries = ranks
+ .map(|(index, rank)| (index, rank * centroids_weight))
+ .rev()
+ .peekable();
+
+ // Consume the right tail from the back, so the centroid scan can omit
all tail checks.
+ while let Some((index, _)) = queries.next_if(|&(_, weight)| weight >
centroids_weight - 1.)
+ {
+ quantiles[index] = self.max;
+ }
+ if queries.peek().is_none() {
+ return;
+ }
+
+ let last = self.centroids.last().unwrap();
+ let last_weight = last.weight();
+ if last_weight > 1. {
+ while let Some((index, weight)) =
+ queries.next_if(|&(_, weight)| centroids_weight - weight <=
last_weight / 2.)
+ {
+ quantiles[index] = if last_weight == 2. {
+ self.max
+ } else {
+ self.max
+ - (((centroids_weight - weight - 1.) / ((last_weight /
2.) - 1.))
+ * (self.max - last.mean))
+ };
+ }
+ }
+
+ let mut queries = queries.rev().peekable();
+ while let Some((index, _)) = queries.next_if(|&(_, weight)| weight <
1.) {
+ quantiles[index] = self.min;
+ }
+ if queries.peek().is_none() {
+ return;
+ }
+
+ let first = &self.centroids[0];
+ let first_weight = first.weight();
+ if first_weight > 1. {
+ while let Some((index, weight)) =
+ queries.next_if(|&(_, weight)| weight < first_weight / 2.)
+ {
+ quantiles[index] = self.min
+ + (((weight - 1.) / ((first_weight / 2.) - 1.)) *
(first.mean - self.min));
}
- return Some(
- self.max
- - (((centroids_weight - weight - 1.) / ((last_weight / 2.)
- 1.))
- * (self.max - self.centroids[num_centroids - 1].mean)),
- );
+ }
+ if queries.peek().is_none() {
+ return;
}
- // interpolate between extremes
+ // Answer the remaining queries by centroid interval; both streams
advance only forward.
let mut weight_so_far = first_weight / 2.;
- for i in 0..(num_centroids - 1) {
- let dw = (self.centroids[i].weight() + self.centroids[i +
1].weight()) / 2.;
- if weight_so_far + dw > weight {
- // the target weight is between centroids i and i+1
+ for pair in self.centroids.windows(2) {
+ let left = &pair[0];
+ let right = &pair[1];
+ let dw = (left.weight() + right.weight()) / 2.;
+ loop {
+ let Some(&(index, weight)) = queries.peek() else {
+ return;
+ };
+ if weight_so_far + dw <= weight {
+ break;
+ }
+ queries.next();
let mut left_weight = 0.;
- if self.centroids[i].weight.get() == 1 {
+ if left.weight.get() == 1 {
if weight - weight_so_far < 0.5 {
- return Some(self.centroids[i].mean);
+ quantiles[index] = left.mean;
+ continue;
}
left_weight = 0.5;
}
let mut right_weight = 0.;
- if self.centroids[i + 1].weight.get() == 1 {
+ if right.weight.get() == 1 {
if weight_so_far + dw - weight <= 0.5 {
- return Some(self.centroids[i + 1].mean);
+ quantiles[index] = right.mean;
+ continue;
}
right_weight = 0.5;
}
@@ -1499,24 +1621,16 @@ impl TDigestView<'_> {
// centroid, so the estimate approaches the nearer one.
let distance_from_left = weight - weight_so_far - left_weight;
let distance_to_right = weight_so_far + dw - weight -
right_weight;
- return Some(weighted_average(
- self.centroids[i].mean,
- distance_to_right,
- self.centroids[i + 1].mean,
- distance_from_left,
- ));
+ quantiles[index] =
+ weighted_average(left.mean, distance_to_right, right.mean,
distance_from_left);
}
weight_so_far += dw;
}
- let w1 = weight - (centroids_weight) - ((self.centroids[num_centroids
- 1].weight()) / 2.);
- let w2 = (self.centroids[num_centroids - 1].weight() / 2.) - w1;
- Some(weighted_average(
- self.centroids[num_centroids - 1].mean,
- w1,
- self.max,
- w2,
- ))
+ // Rounding at large total weights can exhaust the scan near the
maximum.
+ for (index, _) in queries {
+ quantiles[index] = self.max;
+ }
}
}
@@ -1532,6 +1646,14 @@ fn check_split_points(split_points: &[f64]) {
}
}
+#[track_caller]
+fn check_ranks(ranks: &[f64]) {
+ assert!(
+ ranks.iter().all(|rank| (0.0..=1.0).contains(rank)),
+ "ranks must be in [0.0, 1.0]; got {ranks:?}"
+ );
+}
+
fn centroid_cmp(a: &Centroid, b: &Centroid) -> Ordering {
match a.mean.partial_cmp(&b.mean) {
Some(order) => order,
diff --git a/tests-integration/tests/tdigest_test/property.rs
b/tests-integration/tests/tdigest_test/property.rs
index 28ac0b4..6e5fbc1 100644
--- a/tests-integration/tests/tdigest_test/property.rs
+++ b/tests-integration/tests/tdigest_test/property.rs
@@ -36,10 +36,13 @@ fn assert_quantiles_are_monotonic(tdigest: &mut TDigestMut)
{
let min = tdigest.min_value().unwrap();
let max = tdigest.max_value().unwrap();
let mut previous = min;
+ let ranks = (0..=RANK_STEPS)
+ .map(|step| step as f64 / RANK_STEPS as f64)
+ .collect::<Vec<_>>();
+ let quantiles = tdigest.quantiles(&ranks).unwrap();
- for step in 0..=RANK_STEPS {
- let rank = step as f64 / RANK_STEPS as f64;
- let quantile = tdigest.quantile(rank).unwrap();
+ for (&rank, quantile) in ranks.iter().zip(quantiles) {
+ assert_eq!(tdigest.quantile(rank), Some(quantile));
assert!(
(previous..=max).contains(&quantile),
"quantile {quantile} at rank {rank} is outside [{previous}, {max}]"
@@ -87,3 +90,42 @@ fn prop_merged_quantile_is_non_decreasing() {
.rng(Gen::new(900))
.quickcheck(property as fn(Vec<u32>, Vec<u32>) -> TestResult);
}
+
+#[test]
+fn prop_batch_quantiles_preserve_input_order_and_duplicates() {
+ fn property(values: Vec<u32>, ranks: Vec<u8>) {
+ let tdigest = digest_of(&values);
+ let frozen = tdigest.clone().freeze();
+ let mut ranks = ranks
+ .into_iter()
+ .map(|rank| f64::from(rank) / f64::from(u8::MAX))
+ .collect::<Vec<_>>();
+ if let Some(&rank) = ranks.first() {
+ ranks.push(rank);
+ }
+ ranks.extend_from_slice(&[1.0, 0.0, -0.0]);
+
+ for sorted in [false, true] {
+ if sorted {
+ ranks.sort_unstable_by(f64::total_cmp);
+ }
+ let expected = if frozen.is_empty() {
+ None
+ } else {
+ Some(
+ ranks
+ .iter()
+ .map(|&rank| frozen.quantile(rank).unwrap())
+ .collect::<Vec<_>>(),
+ )
+ };
+ assert_eq!(tdigest.clone().quantiles(&ranks), expected);
+ assert_eq!(frozen.quantiles(&ranks), expected);
+ }
+ }
+
+ QuickCheck::new()
+ .tests(256)
+ .rng(Gen::new(1200))
+ .quickcheck(property as fn(Vec<u32>, Vec<u8>));
+}
diff --git a/tests-integration/tests/tdigest_test/sketch.rs
b/tests-integration/tests/tdigest_test/sketch.rs
index 38a94b5..e35d2d6 100644
--- a/tests-integration/tests/tdigest_test/sketch.rs
+++ b/tests-integration/tests/tdigest_test/sketch.rs
@@ -35,6 +35,8 @@ fn test_empty() {
assert_eq!(tdigest.max_value(), None);
assert_eq!(tdigest.rank(0.0), None);
assert_eq!(tdigest.quantile(0.5), None);
+ assert_eq!(tdigest.quantiles(&[0.0, 0.5, 1.0]), None);
+ assert_eq!(tdigest.quantiles(&[]), None);
let split_points = [0.0];
assert_eq!(tdigest.pmf(&split_points), None);
@@ -48,6 +50,8 @@ fn test_empty() {
assert_eq!(tdigest.max_value(), None);
assert_eq!(tdigest.rank(0.0), None);
assert_eq!(tdigest.quantile(0.5), None);
+ assert_eq!(tdigest.quantiles(&[0.0, 0.5, 1.0]), None);
+ assert_eq!(tdigest.quantiles(&[]), None);
let split_points = [0.0];
assert_eq!(tdigest.pmf(&split_points), None);
@@ -68,6 +72,12 @@ fn test_one_value() {
assert_eq!(tdigest.quantile(0.0), Some(1.0));
assert_eq!(tdigest.quantile(0.5), Some(1.0));
assert_eq!(tdigest.quantile(1.0), Some(1.0));
+ let ranks = [1.0, 0.5, 0.0, 0.5];
+ assert_eq!(tdigest.quantiles(&ranks), Some(vec![1.0; ranks.len()]));
+ assert_eq!(
+ tdigest.freeze().quantiles(&ranks),
+ Some(vec![1.0; ranks.len()])
+ );
}
#[test]
@@ -360,6 +370,24 @@ fn deserialize_with_centroids(k: u16, min: f64, max: f64,
centroids: &[(f64, u64
TDigestMut::deserialize(&bytes).unwrap()
}
+fn assert_quantile_queries(tdigest: &TDigestMut, ranks: &[f64], expected:
&[f64]) {
+ let frozen = tdigest.clone().freeze();
+ for actual in [
+ tdigest.clone().quantiles(ranks).unwrap(),
+ frozen.quantiles(ranks).unwrap(),
+ ] {
+ assert_eq!(actual.len(), expected.len());
+ for (actual, &expected) in actual.into_iter().zip(expected) {
+ assert_that!(actual, near(expected, 1e-12));
+ }
+ }
+ let mut mutable = tdigest.clone();
+ for (&rank, &expected) in ranks.iter().zip(expected) {
+ assert_that!(mutable.quantile(rank).unwrap(), near(expected, 1e-12));
+ assert_that!(frozen.quantile(rank).unwrap(), near(expected, 1e-12));
+ }
+}
+
#[test]
fn test_quantile_moves_toward_the_nearer_bracketing_centroid() {
let mut tdigest =
@@ -395,6 +423,156 @@ fn test_quantile_handles_two_sample_last_centroid() {
assert_eq!(tdigest.quantile(0.75), Some(100.0));
}
+#[test]
+fn test_batch_quantiles_match_scalar_queries_in_input_order() {
+ let mut tdigest = TDigestMut::new(100).unwrap();
+ for value in 0..10_000 {
+ tdigest.update(((value * 37) % 1_003) as f64);
+ }
+
+ let frozen = tdigest.clone().freeze();
+ for ranks in [
+ vec![-0.0, 0.0, 0.001, 0.25, 0.5, 0.5, 0.99, 1.0],
+ vec![0.99, 0.0, 0.5, 1.0, 0.001, -0.0, 0.5, 0.25],
+ vec![1.0, 0.99, 0.5, 0.5, 0.25, 0.001, 0.0],
+ vec![],
+ ] {
+ let expected = ranks
+ .iter()
+ .map(|&rank| frozen.quantile(rank).unwrap())
+ .collect::<Vec<_>>();
+ // Each mutable batch starts with the original buffered values still
pending.
+ assert_eq!(tdigest.clone().quantiles(&ranks), Some(expected.clone()));
+ assert_eq!(frozen.quantiles(&ranks), Some(expected));
+ }
+}
+
+#[test]
+fn test_batch_quantiles_cross_centroid_and_tail_boundaries() {
+ let tdigest =
+ deserialize_with_centroids(100, 0.0, 100.0, &[(10.0, 10), (50.0, 10),
(90.0, 10)]);
+ // Query masses span both tails and the centers of all three centroids.
+ let queries = [
+ (0.0, 0.0),
+ (1.0, 0.0),
+ (3.0, 5.0),
+ (5.0, 10.0),
+ (10.0, 30.0),
+ (15.0, 50.0),
+ (15.0, 50.0),
+ (20.0, 70.0),
+ (25.0, 90.0),
+ (27.0, 95.0),
+ (29.0, 100.0),
+ (30.0, 100.0),
+ ];
+ let mut reversed = queries;
+ reversed.reverse();
+ let mut unordered = queries;
+ unordered.rotate_left(5);
+
+ for queries in [queries, reversed, unordered] {
+ let ranks = queries.map(|(weight, _)| weight / 30.0);
+ let expected = queries.map(|(_, quantile)| quantile);
+ assert_quantile_queries(&tdigest, &ranks, &expected);
+ }
+ // Batches confined to one region can finish before reaching the centroid
scan.
+ for (weight, expected) in queries {
+ assert_quantile_queries(&tdigest, &[weight / 30.0; 3], &[expected; 3]);
+ }
+}
+
+#[test]
+fn test_quantiles_respect_two_sample_tail_boundaries() {
+ let tdigest = deserialize_with_centroids(100, 0.0, 100.0, &[(10.0, 2),
(90.0, 2)]);
+ // These tails are discontinuous: the left endpoint steps to the first
mean, while the right
+ // endpoint steps from the last mean to max. Neither tail may divide by a
zero span.
+ let ranks = [
+ 0.0,
+ 0.25_f64.next_down(),
+ 0.25,
+ 0.25_f64.next_up(),
+ 0.5,
+ 0.75_f64.next_down(),
+ 0.75,
+ 0.75,
+ 0.75_f64.next_up(),
+ 1.0,
+ ];
+ let expected = [0.0, 0.0, 10.0, 10.0, 50.0, 90.0, 100.0, 100.0, 100.0,
100.0];
+ assert_quantile_queries(&tdigest, &ranks, &expected);
+}
+
+#[test]
+fn test_quantiles_interpolate_around_singleton_centroids() {
+ let tdigest = deserialize_with_centroids(
+ 100,
+ 0.0,
+ 60.0,
+ &[(0.0, 1), (10.0, 3), (20.0, 1), (40.0, 5), (60.0, 1)],
+ );
+ let ranks = [
+ 0.0, 0.75, 1.0, 1.75, 2.5, 3.25, 4.0, 4.5, 4.75, 5.0, 6.25, 7.5, 8.75,
10.0, 11.0,
+ ]
+ .map(|weight| weight / 11.0);
+ let expected = [
+ 0.0, 0.0, 0.0, 5.0, 10.0, 15.0, 20.0, 20.0, 20.0, 20.0, 30.0, 40.0,
50.0, 60.0, 60.0,
+ ];
+ assert_quantile_queries(&tdigest, &ranks, &expected);
+}
+
+#[test]
+fn test_quantiles_stay_within_extrema_at_large_total_weights() {
+ for total_weight in [1_u64 << 53, 1_u64 << 54, u64::MAX] {
+ let tdigest = deserialize_with_centroids(
+ 100,
+ 0.0,
+ 100.0,
+ &[(10.0, total_weight - 2), (50.0, 1), (90.0, 1)],
+ );
+ let frozen = tdigest.clone().freeze();
+ let ranks = [0.0, 0.5, 1.0_f64.next_down(), 1.0, 1.0];
+ for quantiles in [
+ tdigest.clone().quantiles(&ranks).unwrap(),
+ frozen.quantiles(&ranks).unwrap(),
+ ranks.map(|rank| frozen.quantile(rank).unwrap()).to_vec(),
+ ] {
+ assert_eq!(quantiles[0], 0.0);
+ assert_eq!(&quantiles[3..], &[100.0, 100.0]);
+ assert!(
+ quantiles.is_sorted(),
+ "weight {total_weight}: {quantiles:?}"
+ );
+ assert!(
+ quantiles.iter().all(|value| (0.0..=100.0).contains(value)),
+ "weight {total_weight}: {quantiles:?}"
+ );
+ }
+ }
+}
+
+#[test]
+fn test_batch_quantiles_reject_invalid_ranks() {
+ for values in [&[][..], &[1.0, 2.0, 3.0][..]] {
+ let mut tdigest = TDigestMut::default();
+ for &value in values {
+ tdigest.update(value);
+ }
+ let frozen = tdigest.clone().freeze();
+ for invalid in [
+ -f64::EPSILON,
+ 1.0 + f64::EPSILON,
+ f64::NAN,
+ f64::NEG_INFINITY,
+ f64::INFINITY,
+ ] {
+ let ranks = [0.5, invalid];
+ assert!(catch_unwind(AssertUnwindSafe(||
tdigest.quantiles(&ranks))).is_err());
+ assert!(catch_unwind(|| frozen.quantiles(&ranks)).is_err());
+ }
+ }
+}
+
#[test]
fn test_rank_left_tail_is_a_fraction_of_the_total_weight() {
let mut tdigest =
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
