This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch codex/kll-api-and-performance in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 9402a41171f8fe7df6b761ee3aa99a819b891a5b Author: tison <[email protected]> AuthorDate: Wed Sep 2 12:19:56 2026 +0800 test(kll): organize deterministic coverage --- tests-integration/tests/kll_test/core.rs | 86 +++++ tests-integration/tests/kll_test/generic.rs | 68 ++++ tests-integration/tests/kll_test/main.rs | 5 +- tests-integration/tests/kll_test/merge.rs | 124 +++++++ tests-integration/tests/kll_test/query.rs | 173 +++++++++ tests-integration/tests/kll_test/sketch.rs | 550 ---------------------------- tests-integration/tests/serde_tests/kll.rs | 84 +++++ 7 files changed, 539 insertions(+), 551 deletions(-) diff --git a/tests-integration/tests/kll_test/core.rs b/tests-integration/tests/kll_test/core.rs new file mode 100644 index 0000000..24915ab --- /dev/null +++ b/tests-integration/tests/kll_test/core.rs @@ -0,0 +1,86 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use datasketches::error::ErrorKind; +use datasketches::kll::KllSketch; + +const DEFAULT_K: u16 = 200; +const MIN_K: u16 = 8; +const MAX_K: u16 = u16::MAX; + +#[test] +fn k_limits() { + KllSketch::<f32>::new(MIN_K).unwrap(); + KllSketch::<f32>::new(MAX_K).unwrap(); + + let error = KllSketch::<f32>::new(MIN_K - 1).unwrap_err(); + assert_eq!(error.kind(), ErrorKind::InvalidArgument); +} + +#[test] +fn empty_and_reset_state() { + let mut sketch = KllSketch::<f32>::new(64).unwrap(); + assert!(sketch.is_empty()); + assert!(!sketch.is_estimation_mode()); + assert_eq!(sketch.n(), 0); + assert_eq!(sketch.num_retained(), 0); + assert_eq!(sketch.min_item(), None); + assert_eq!(sketch.max_item(), None); + + for item in 0..10_000 { + sketch.update(item as f32); + } + assert!(sketch.is_estimation_mode()); + assert!(sketch.num_retained() > 0); + + sketch.reset(); + assert_eq!(sketch.k(), 64); + assert_eq!(sketch.min_k(), 64); + assert!(sketch.is_empty()); + assert!(!sketch.is_estimation_mode()); + assert_eq!(sketch.n(), 0); + assert_eq!(sketch.num_retained(), 0); + assert_eq!(sketch.min_item(), None); + assert_eq!(sketch.max_item(), None); +} + +#[test] +fn unordered_updates_are_ignored() { + let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); + sketch.update(f32::NAN); + assert!(sketch.is_empty()); + + sketch.update(0.0); + sketch.update(f32::NAN); + assert_eq!(sketch.n(), 1); + assert_eq!(sketch.num_retained(), 1); +} + +#[test] +fn retained_count_stays_consistent_through_compaction_and_roundtrip() { + let mut sketch = KllSketch::<f32>::new(32).unwrap(); + for item in 0..100_000 { + sketch.update(item as f32); + assert!(sketch.num_retained() <= sketch.n() as usize); + } + + let decoded = KllSketch::<f32>::deserialize(&sketch.serialize()).unwrap(); + assert_eq!(decoded.n(), sketch.n()); + assert_eq!(decoded.num_retained(), sketch.num_retained()); + assert_eq!(decoded.min_item(), Some(&0.0)); + assert_eq!(decoded.max_item(), Some(&99_999.0)); +} diff --git a/tests-integration/tests/kll_test/generic.rs b/tests-integration/tests/kll_test/generic.rs new file mode 100644 index 0000000..62b0fe3 --- /dev/null +++ b/tests-integration/tests/kll_test/generic.rs @@ -0,0 +1,68 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::cmp::Ordering; + +use datasketches::kll::KllComparator; +use datasketches::kll::KllSketch; +use datasketches::kll::SearchCriteria; + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +struct NumericStringOrder; + +impl KllComparator<String> for NumericStringOrder { + fn compare(&self, left: &String, right: &String) -> Ordering { + left.parse::<u64>() + .unwrap() + .cmp(&right.parse::<u64>().unwrap()) + } + + fn is_compatible(&self, _other: &Self) -> bool { + true + } +} + +#[test] +fn custom_comparator_controls_queries_and_survives_roundtrip() { + let mut sketch = + KllSketch::<String, NumericStringOrder>::new_with_comparator(200, NumericStringOrder) + .unwrap(); + for item in ["2", "10", "1"] { + sketch.update(item.to_owned()); + } + + assert_eq!(sketch.min_item().map(String::as_str), Some("1")); + assert_eq!(sketch.max_item().map(String::as_str), Some("10")); + assert_eq!( + sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), + "2" + ); + + let decoded = KllSketch::<String, NumericStringOrder>::deserialize_with_comparator( + &sketch.serialize(), + NumericStringOrder, + ) + .unwrap(); + assert_eq!(decoded.n(), sketch.n()); + assert_eq!(decoded.num_retained(), sketch.num_retained()); + assert_eq!(decoded.min_item().map(String::as_str), Some("1")); + assert_eq!(decoded.max_item().map(String::as_str), Some("10")); + assert_eq!( + decoded.quantile(0.5, SearchCriteria::Inclusive).unwrap(), + "2" + ); +} diff --git a/tests-integration/tests/kll_test/main.rs b/tests-integration/tests/kll_test/main.rs index 825a628..26441bc 100644 --- a/tests-integration/tests/kll_test/main.rs +++ b/tests-integration/tests/kll_test/main.rs @@ -15,4 +15,7 @@ // specific language governing permissions and limitations // under the License. -mod sketch; +mod core; +mod generic; +mod merge; +mod query; diff --git a/tests-integration/tests/kll_test/merge.rs b/tests-integration/tests/kll_test/merge.rs new file mode 100644 index 0000000..a20f19a --- /dev/null +++ b/tests-integration/tests/kll_test/merge.rs @@ -0,0 +1,124 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use std::cmp::Ordering; + +use datasketches::error::ErrorKind; +use datasketches::kll::KllComparator; +use datasketches::kll::KllSketch; +use datasketches::kll::SearchCriteria; + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +struct DirectionalOrder { + descending: bool, +} + +impl KllComparator<i64> for DirectionalOrder { + fn compare(&self, left: &i64, right: &i64) -> Ordering { + if self.descending { + right.cmp(left) + } else { + left.cmp(right) + } + } + + fn is_compatible(&self, other: &Self) -> bool { + self == other + } +} + +#[test] +fn merge_preserves_weight_extrema_and_query_invariants() { + let mut left = KllSketch::<f32>::new(200).unwrap(); + let mut right = KllSketch::<f32>::new(200).unwrap(); + for item in 0..10_000 { + left.update(item as f32); + right.update((19_999 - item) as f32); + } + + left.merge(&right).unwrap(); + + assert_eq!(left.n(), 20_000); + assert_eq!(left.min_item(), Some(&0.0)); + assert_eq!(left.max_item(), Some(&19_999.0)); + assert_eq!(left.sorted_view().total_weight(), left.n()); + let quantiles = left + .quantiles(&[0.0, 0.25, 0.5, 0.75, 1.0], SearchCriteria::Inclusive) + .unwrap(); + assert!(quantiles.windows(2).all(|pair| pair[0] <= pair[1])); +} + +#[test] +fn merge_tracks_the_smallest_estimation_k() { + let mut left = KllSketch::<f32>::new(256).unwrap(); + let mut right = KllSketch::<f32>::new(128).unwrap(); + for item in 0..10_000 { + left.update(item as f32); + right.update((20_000 - item) as f32); + } + + left.merge(&right).unwrap(); + + assert_eq!(left.min_k(), right.min_k()); + assert_eq!(left.normalized_rank_error(), right.normalized_rank_error()); + assert_eq!(left.normalized_pmf_error(), right.normalized_pmf_error()); +} + +#[test] +fn merging_an_empty_lower_k_sketch_does_not_change_accuracy() { + let mut sketch = KllSketch::<f32>::new(256).unwrap(); + for item in 0..10_000 { + sketch.update(item as f32); + } + let empty = KllSketch::<f32>::new(128).unwrap(); + let rank_error = sketch.normalized_rank_error(); + + sketch.merge(&empty).unwrap(); + + assert_eq!(sketch.n(), 10_000); + assert_eq!(sketch.normalized_rank_error(), rank_error); +} + +#[test] +fn merge_updates_extrema_from_either_side() { + let mut first = KllSketch::<f32>::new(200).unwrap(); + let mut second = KllSketch::<f32>::new(200).unwrap(); + first.update(1.0); + second.update(2.0); + + second.merge(&first).unwrap(); + + assert_eq!(second.min_item(), Some(&1.0)); + assert_eq!(second.max_item(), Some(&2.0)); +} + +#[test] +fn merge_rejects_incompatible_comparators_without_mutation() { + let mut ascending = + KllSketch::new_with_comparator(200, DirectionalOrder { descending: false }).unwrap(); + let mut descending = + KllSketch::new_with_comparator(200, DirectionalOrder { descending: true }).unwrap(); + ascending.update(1); + descending.update(2); + + let error = ascending.merge(&descending).unwrap_err(); + + assert_eq!(error.kind(), ErrorKind::InvalidArgument); + assert_eq!(ascending.n(), 1); + assert_eq!(ascending.min_item(), Some(&1)); + assert_eq!(ascending.max_item(), Some(&1)); +} diff --git a/tests-integration/tests/kll_test/query.rs b/tests-integration/tests/kll_test/query.rs new file mode 100644 index 0000000..81343c9 --- /dev/null +++ b/tests-integration/tests/kll_test/query.rs @@ -0,0 +1,173 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use datasketches::error::ErrorKind; +use datasketches::kll::KllSketch; +use datasketches::kll::SearchCriteria; + +const DEFAULT_K: u16 = 200; +const NUMERIC_NOISE_TOLERANCE: f64 = 1e-6; + +#[test] +fn empty_and_invalid_queries_return_errors() { + let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); + assert!(sketch.rank(&0.0, SearchCriteria::Inclusive).is_err()); + assert!(sketch.quantile(0.5, SearchCriteria::Inclusive).is_err()); + assert!(sketch.pmf(&[0.0], SearchCriteria::Inclusive).is_err()); + assert!(sketch.cdf(&[0.0], SearchCriteria::Inclusive).is_err()); + + sketch.update(0.0); + for rank in [-1.0, f64::NAN, 1.1] { + let error = sketch + .quantile(rank, SearchCriteria::Inclusive) + .unwrap_err(); + assert_eq!(error.kind(), ErrorKind::InvalidArgument); + } + for split_points in [&[1.0, 0.0][..], &[f32::NAN][..]] { + let error = sketch + .cdf(split_points, SearchCriteria::Inclusive) + .unwrap_err(); + assert_eq!(error.kind(), ErrorKind::InvalidArgument); + } +} + +#[test] +fn inclusive_and_exclusive_semantics_cover_duplicates() { + let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); + for item in [1.0, 1.0, 2.0, 2.0] { + sketch.update(item); + } + + assert_eq!(sketch.rank(&1.0, SearchCriteria::Exclusive).unwrap(), 0.0); + assert_eq!(sketch.rank(&1.0, SearchCriteria::Inclusive).unwrap(), 0.5); + assert_eq!(sketch.rank(&2.0, SearchCriteria::Exclusive).unwrap(), 0.5); + assert_eq!(sketch.rank(&2.0, SearchCriteria::Inclusive).unwrap(), 1.0); + assert_eq!( + sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), + 1.0 + ); + assert_eq!( + sketch.quantile(0.5, SearchCriteria::Exclusive).unwrap(), + 2.0 + ); +} + +#[test] +fn exact_mode_queries_match_the_stream() { + let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); + for item in 1..=100 { + sketch.update(item as f32); + } + + assert_eq!( + sketch.quantile(0.0, SearchCriteria::Inclusive).unwrap(), + 1.0 + ); + assert_eq!( + sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), + 50.0 + ); + assert_eq!( + sketch.quantile(1.0, SearchCriteria::Inclusive).unwrap(), + 100.0 + ); + for item in 1..=100 { + assert_eq!( + sketch + .rank(&(item as f32), SearchCriteria::Inclusive) + .unwrap(), + item as f64 / 100.0 + ); + } +} + +#[test] +fn estimation_mode_queries_preserve_deterministic_invariants() { + let mut sketch = KllSketch::<f32>::new(64).unwrap(); + for item in 0..10_000 { + sketch.update(item as f32); + } + + let mut previous_rank = 0.0; + for item in (0..10_000).step_by(100) { + let rank = sketch + .rank(&(item as f32), SearchCriteria::Inclusive) + .unwrap(); + assert!(rank >= previous_rank); + assert!((0.0..=1.0).contains(&rank)); + previous_rank = rank; + } + assert_eq!(sketch.min_item(), Some(&0.0)); + assert_eq!(sketch.max_item(), Some(&9_999.0)); + assert!(sketch.normalized_rank_error() < sketch.normalized_pmf_error()); +} + +#[test] +fn rank_cdf_and_pmf_are_consistent() { + let mut sketch = KllSketch::<f32>::new(64).unwrap(); + for item in 0..10_000 { + sketch.update(item as f32); + } + let split_points: Vec<_> = (100..10_000).step_by(100).map(|item| item as f32).collect(); + + for criteria in [SearchCriteria::Inclusive, SearchCriteria::Exclusive] { + let cdf = sketch.cdf(&split_points, criteria).unwrap(); + let pmf = sketch.pmf(&split_points, criteria).unwrap(); + let mut subtotal = 0.0; + for (index, split_point) in split_points.iter().enumerate() { + subtotal += pmf[index]; + assert!((cdf[index] - subtotal).abs() <= NUMERIC_NOISE_TOLERANCE); + assert_eq!(cdf[index], sketch.rank(split_point, criteria).unwrap()); + } + assert!((pmf.iter().sum::<f64>() - 1.0).abs() <= NUMERIC_NOISE_TOLERANCE); + } +} + +#[test] +fn sorted_view_supports_repeated_and_batch_queries() { + let mut sketch = KllSketch::<f32>::new(64).unwrap(); + for item in 0..1_000 { + sketch.update(item as f32); + } + let view = sketch.sorted_view(); + let ranks = [0.0, 0.25, 0.5, 0.75, 1.0]; + let quantiles = sketch.quantiles(&ranks, SearchCriteria::Inclusive).unwrap(); + + assert_eq!(view.len(), sketch.num_retained()); + assert_eq!(view.total_weight(), sketch.n()); + assert_eq!( + view.quantiles(&ranks, SearchCriteria::Inclusive).unwrap(), + quantiles + ); + for (&rank, quantile) in ranks.iter().zip(&quantiles) { + assert_eq!( + view.quantile(rank, SearchCriteria::Inclusive).unwrap(), + *quantile + ); + assert_eq!( + view.rank(quantile, SearchCriteria::Inclusive).unwrap(), + sketch.rank(quantile, SearchCriteria::Inclusive).unwrap() + ); + } + + sketch.update(2_000.0); + assert_eq!(view.total_weight(), 1_000); + assert_eq!( + view.quantile(1.0, SearchCriteria::Inclusive).unwrap(), + 999.0 + ); +} diff --git a/tests-integration/tests/kll_test/sketch.rs b/tests-integration/tests/kll_test/sketch.rs deleted file mode 100644 index 5fcd068..0000000 --- a/tests-integration/tests/kll_test/sketch.rs +++ /dev/null @@ -1,550 +0,0 @@ -// Licensed to the Apache Software Foundation (ASF) under one -// or more contributor license agreements. See the NOTICE file -// distributed with this work for additional information -// regarding copyright ownership. The ASF licenses this file -// to you under the Apache License, Version 2.0 (the -// "License"); you may not use this file except in compliance -// with the License. You may obtain a copy of the License at -// -// http://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, -// software distributed under the License is distributed on an -// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -// KIND, either express or implied. See the License for the -// specific language governing permissions and limitations -// under the License. - -use std::cmp::Ordering; - -use datasketches::error::ErrorKind; -use datasketches::kll::KllComparator; -use datasketches::kll::KllSketch; -use datasketches::kll::SearchCriteria; - -const DEFAULT_K: u16 = 200; -const MIN_K: u16 = 8; -const MAX_K: u16 = u16::MAX; -const NUMERIC_NOISE_TOLERANCE: f64 = 1e-6; - -fn assert_approx_eq(actual: f64, expected: f64, tolerance: f64) { - let delta = (actual - expected).abs(); - assert!( - delta <= tolerance, - "expected {expected} +/- {tolerance}, got {actual}" - ); -} - -fn rank_eps(sketch: &KllSketch<f32>) -> f64 { - sketch.normalized_rank_error() -} - -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -struct NumericStringOrder; - -impl KllComparator<String> for NumericStringOrder { - fn compare(&self, left: &String, right: &String) -> Ordering { - left.parse::<u64>() - .unwrap() - .cmp(&right.parse::<u64>().unwrap()) - } - - fn is_compatible(&self, _other: &Self) -> bool { - true - } -} - -#[derive(Debug, Clone, Copy, PartialEq, Eq)] -struct DirectionalOrder { - descending: bool, -} - -impl KllComparator<i64> for DirectionalOrder { - fn compare(&self, left: &i64, right: &i64) -> Ordering { - if self.descending { - right.cmp(left) - } else { - left.cmp(right) - } - } - - fn is_compatible(&self, other: &Self) -> bool { - self == other - } -} - -#[test] -fn test_k_limits() { - let _min = KllSketch::<f32>::new(MIN_K).unwrap(); - let _max = KllSketch::<f32>::new(MAX_K).unwrap(); -} - -#[test] -fn test_k_too_small_returns_error() { - let error = KllSketch::<f32>::new(MIN_K - 1).unwrap_err(); - assert_eq!(error.kind(), ErrorKind::InvalidArgument); -} - -#[test] -fn test_empty() { - let sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - assert!(sketch.is_empty()); - assert!(!sketch.is_estimation_mode()); - assert_eq!(sketch.n(), 0); - assert_eq!(sketch.num_retained(), 0); - assert!(sketch.min_item().is_none()); - assert!(sketch.max_item().is_none()); - assert!(sketch.rank(&0.0, SearchCriteria::Inclusive).is_err()); - assert!(sketch.quantile(0.5, SearchCriteria::Inclusive).is_err()); - assert!(sketch.pmf(&[0.0f32], SearchCriteria::Inclusive).is_err()); - assert!(sketch.cdf(&[0.0f32], SearchCriteria::Inclusive).is_err()); -} - -#[test] -fn test_quantile_out_of_range_returns_error() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch.update(0.0); - let error = sketch - .quantile(-1.0, SearchCriteria::Inclusive) - .unwrap_err(); - assert_eq!(error.kind(), ErrorKind::InvalidArgument); -} - -#[test] -fn test_one_item() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch.update(1.0); - assert!(!sketch.is_empty()); - assert!(!sketch.is_estimation_mode()); - assert_eq!(sketch.n(), 1); - assert_eq!(sketch.num_retained(), 1); - assert_eq!(sketch.rank(&1.0, SearchCriteria::Exclusive).unwrap(), 0.0); - assert_eq!(sketch.rank(&1.0, SearchCriteria::Inclusive).unwrap(), 1.0); - assert_eq!(sketch.rank(&2.0, SearchCriteria::Exclusive).unwrap(), 1.0); - assert_eq!(sketch.min_item().cloned(), Some(1.0)); - assert_eq!(sketch.max_item().cloned(), Some(1.0)); - assert_eq!( - sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), - 1.0 - ); -} - -#[test] -fn test_duplicate_items_follow_inclusive_and_exclusive_semantics() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - for item in [1.0, 1.0, 2.0, 2.0] { - sketch.update(item); - } - - assert_eq!(sketch.rank(&1.0, SearchCriteria::Exclusive).unwrap(), 0.0); - assert_eq!(sketch.rank(&1.0, SearchCriteria::Inclusive).unwrap(), 0.5); - assert_eq!(sketch.rank(&2.0, SearchCriteria::Exclusive).unwrap(), 0.5); - assert_eq!(sketch.rank(&2.0, SearchCriteria::Inclusive).unwrap(), 1.0); - assert_eq!( - sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), - 1.0 - ); - assert_eq!( - sketch.quantile(0.5, SearchCriteria::Exclusive).unwrap(), - 2.0 - ); -} - -#[test] -fn test_nan_is_ignored() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch.update(f32::NAN); - assert!(sketch.is_empty()); - sketch.update(0.0); - sketch.update(f32::NAN); - assert_eq!(sketch.n(), 1); -} - -#[test] -fn test_many_items_exact_mode() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let n = DEFAULT_K as usize; - for i in 1..=n { - sketch.update(i as f32); - assert_eq!(sketch.n(), i as u64); - } - assert!(!sketch.is_empty()); - assert!(!sketch.is_estimation_mode()); - assert_eq!(sketch.num_retained(), n); - assert_eq!(sketch.min_item().cloned(), Some(1.0)); - assert_eq!( - sketch.quantile(0.0, SearchCriteria::Inclusive).unwrap(), - 1.0 - ); - assert_eq!(sketch.max_item().cloned(), Some(n as f32)); - assert_eq!( - sketch.quantile(1.0, SearchCriteria::Inclusive).unwrap(), - n as f32 - ); - - for i in 1..=n { - let inclusive_rank = i as f64 / n as f64; - assert_eq!( - sketch.rank(&(i as f32), SearchCriteria::Inclusive).unwrap(), - inclusive_rank - ); - let exclusive_rank = (i - 1) as f64 / n as f64; - assert_eq!( - sketch.rank(&(i as f32), SearchCriteria::Exclusive).unwrap(), - exclusive_rank - ); - } -} - -#[test] -fn test_ten_items_quantiles() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - for i in 1..=10 { - sketch.update(i as f32); - } - assert_eq!( - sketch.quantile(0.0, SearchCriteria::Inclusive).unwrap(), - 1.0 - ); - assert_eq!( - sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), - 5.0 - ); - assert_eq!( - sketch.quantile(0.99, SearchCriteria::Inclusive).unwrap(), - 10.0 - ); - assert_eq!( - sketch.quantile(1.0, SearchCriteria::Inclusive).unwrap(), - 10.0 - ); -} - -#[test] -fn test_hundred_items_quantiles() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - for i in 0..100 { - sketch.update(i as f32); - } - assert_eq!( - sketch.quantile(0.0, SearchCriteria::Inclusive).unwrap(), - 0.0 - ); - assert_eq!( - sketch.quantile(0.01, SearchCriteria::Inclusive).unwrap(), - 0.0 - ); - assert_eq!( - sketch.quantile(0.5, SearchCriteria::Inclusive).unwrap(), - 49.0 - ); - assert_eq!( - sketch.quantile(0.99, SearchCriteria::Inclusive).unwrap(), - 98.0 - ); - assert_eq!( - sketch.quantile(1.0, SearchCriteria::Inclusive).unwrap(), - 99.0 - ); -} - -#[test] -fn test_many_items_estimation_mode_rank_error() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let n = 10_000; - for i in 0..n { - sketch.update(i as f32); - } - assert!(!sketch.is_empty()); - assert!(sketch.is_estimation_mode()); - assert_eq!(sketch.min_item().cloned(), Some(0.0)); - assert_eq!(sketch.max_item().cloned(), Some((n - 1) as f32)); - - let rank_eps = rank_eps(&sketch); - for i in (0..n).step_by(10) { - let true_rank = i as f64 / n as f64; - let rank = sketch.rank(&(i as f32), SearchCriteria::Exclusive).unwrap(); - assert_approx_eq(rank, true_rank, rank_eps); - } - - assert!(sketch.num_retained() > 0); -} - -#[test] -fn test_rank_cdf_pmf_consistency() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let n = 200; - let mut values = Vec::with_capacity(n); - for i in 0..n { - sketch.update(i as f32); - values.push(i as f32); - } - - let ranks = sketch.cdf(&values, SearchCriteria::Exclusive).unwrap(); - let pmf = sketch.pmf(&values, SearchCriteria::Exclusive).unwrap(); - - let mut subtotal = 0.0; - for i in 0..n { - let rank = sketch.rank(&values[i], SearchCriteria::Exclusive).unwrap(); - assert_eq!(rank, ranks[i]); - subtotal += pmf[i]; - assert!( - (ranks[i] - subtotal).abs() <= NUMERIC_NOISE_TOLERANCE, - "cdf vs pmf mismatch at index {i}" - ); - } - - let ranks = sketch.cdf(&values, SearchCriteria::Inclusive).unwrap(); - let pmf = sketch.pmf(&values, SearchCriteria::Inclusive).unwrap(); - - let mut subtotal = 0.0; - for i in 0..n { - let rank = sketch.rank(&values[i], SearchCriteria::Inclusive).unwrap(); - assert_eq!(rank, ranks[i]); - subtotal += pmf[i]; - assert!( - (ranks[i] - subtotal).abs() <= NUMERIC_NOISE_TOLERANCE, - "cdf vs pmf mismatch at index {i}" - ); - } -} - -#[test] -fn test_sorted_view_supports_repeated_and_batch_queries() { - let mut sketch = KllSketch::<f32>::new(64).unwrap(); - for item in 0..1_000 { - sketch.update(item as f32); - } - - let view = sketch.sorted_view(); - let ranks = [0.0, 0.25, 0.5, 0.75, 1.0]; - let quantiles = sketch.quantiles(&ranks, SearchCriteria::Inclusive).unwrap(); - - assert_eq!(view.len(), sketch.num_retained()); - assert_eq!(view.total_weight(), sketch.n()); - assert_eq!( - view.quantiles(&ranks, SearchCriteria::Inclusive).unwrap(), - quantiles - ); - for (&rank, quantile) in ranks.iter().zip(&quantiles) { - assert_eq!( - view.quantile(rank, SearchCriteria::Inclusive).unwrap(), - *quantile - ); - assert_eq!( - view.rank(quantile, SearchCriteria::Inclusive).unwrap(), - sketch.rank(quantile, SearchCriteria::Inclusive).unwrap() - ); - } - - sketch.update(2_000.0); - assert_eq!(view.total_weight(), 1_000); - assert_eq!( - view.quantile(1.0, SearchCriteria::Inclusive).unwrap(), - 999.0 - ); -} - -#[test] -fn test_empty_sorted_view_queries_return_errors() { - let sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let view = sketch.sorted_view(); - - assert!(view.is_empty()); - assert!(view.quantile(0.5, SearchCriteria::Inclusive).is_err()); - assert!(view.rank(&0.0, SearchCriteria::Inclusive).is_err()); -} - -#[test] -fn test_out_of_order_split_points_return_error() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch.update(0.0); - let split_points = [1.0, 0.0]; - let error = sketch - .cdf(&split_points, SearchCriteria::Inclusive) - .unwrap_err(); - assert_eq!(error.kind(), ErrorKind::InvalidArgument); -} - -#[test] -fn test_nan_split_point_returns_error() { - let mut sketch = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch.update(0.0); - let split_points = [f32::NAN]; - let error = sketch - .cdf(&split_points, SearchCriteria::Inclusive) - .unwrap_err(); - assert_eq!(error.kind(), ErrorKind::InvalidArgument); -} - -#[test] -fn test_merge() { - let mut sketch1 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let mut sketch2 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let n = 10_000; - for i in 0..n { - sketch1.update(i as f32); - sketch2.update((2 * n - i - 1) as f32); - } - - assert_eq!(sketch1.min_item().cloned(), Some(0.0)); - assert_eq!(sketch1.max_item().cloned(), Some((n - 1) as f32)); - assert_eq!(sketch2.min_item().cloned(), Some(n as f32)); - assert_eq!(sketch2.max_item().cloned(), Some((2 * n - 1) as f32)); - - sketch1.merge(&sketch2).unwrap(); - - assert!(!sketch1.is_empty()); - assert_eq!(sketch1.n(), (2 * n) as u64); - assert_eq!(sketch1.min_item().cloned(), Some(0.0)); - assert_eq!(sketch1.max_item().cloned(), Some((2 * n - 1) as f32)); - let median = sketch1.quantile(0.5, SearchCriteria::Inclusive).unwrap(); - let rank_eps = rank_eps(&sketch1); - assert_approx_eq(median as f64, n as f64, n as f64 * rank_eps); -} - -#[test] -fn test_merge_lower_k() { - let mut sketch1 = KllSketch::<f32>::new(256).unwrap(); - let mut sketch2 = KllSketch::<f32>::new(128).unwrap(); - let n = 10_000; - for i in 0..n { - sketch1.update(i as f32); - sketch2.update((2 * n - i - 1) as f32); - } - - sketch1.merge(&sketch2).unwrap(); - - assert_eq!(sketch1.n(), (2 * n) as u64); - assert_eq!(sketch1.min_item().cloned(), Some(0.0)); - assert_eq!(sketch1.max_item().cloned(), Some((2 * n - 1) as f32)); - assert_eq!( - sketch1.normalized_rank_error(), - sketch2.normalized_rank_error() - ); - assert_eq!( - sketch1.normalized_pmf_error(), - sketch2.normalized_pmf_error() - ); - let median = sketch1.quantile(0.5, SearchCriteria::Inclusive).unwrap(); - let rank_eps = rank_eps(&sketch1); - assert_approx_eq(median as f64, n as f64, n as f64 * rank_eps); -} - -#[test] -fn test_merge_exact_mode_lower_k() { - let mut sketch1 = KllSketch::<f32>::new(256).unwrap(); - let sketch2 = KllSketch::<f32>::new(128).unwrap(); - let n = 10_000; - for i in 0..n { - sketch1.update(i as f32); - } - - let err_before = sketch1.normalized_pmf_error(); - sketch1.merge(&sketch2).unwrap(); - assert_eq!(sketch1.normalized_pmf_error(), err_before); - - assert_eq!(sketch1.n(), n as u64); - assert_eq!(sketch1.min_item().cloned(), Some(0.0)); - assert_eq!(sketch1.max_item().cloned(), Some((n - 1) as f32)); - let median = sketch1.quantile(0.5, SearchCriteria::Inclusive).unwrap(); - let rank_eps = rank_eps(&sketch1); - assert_approx_eq(median as f64, (n / 2) as f64, (n as f64 / 2.0) * rank_eps); -} - -#[test] -fn test_merge_min_max_from_other() { - let mut sketch1 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - let mut sketch2 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch1.update(1.0); - sketch2.update(2.0); - sketch2.merge(&sketch1).unwrap(); - assert_eq!(sketch2.min_item().cloned(), Some(1.0)); - assert_eq!(sketch2.max_item().cloned(), Some(2.0)); -} - -#[test] -fn test_merge_rejects_incompatible_comparators_without_mutation() { - let mut ascending = - KllSketch::new_with_comparator(200, DirectionalOrder { descending: false }).unwrap(); - let mut descending = - KllSketch::new_with_comparator(200, DirectionalOrder { descending: true }).unwrap(); - ascending.update(1); - descending.update(2); - - let error = ascending.merge(&descending).unwrap_err(); - - assert_eq!(error.kind(), ErrorKind::InvalidArgument); - assert_eq!(ascending.n(), 1); - assert_eq!(ascending.min_item(), Some(&1)); - assert_eq!(ascending.max_item(), Some(&1)); -} - -#[test] -fn test_merge_min_max_large_other() { - let mut sketch1 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - for i in 0..1_000_000 { - sketch1.update(i as f32); - } - let mut sketch2 = KllSketch::<f32>::new(DEFAULT_K).unwrap(); - sketch2.merge(&sketch1).unwrap(); - assert_eq!(sketch2.min_item().cloned(), Some(0.0)); - assert_eq!(sketch2.max_item().cloned(), Some(999_999.0)); -} - -#[test] -fn test_reset_retains_configuration() { - let mut sketch = KllSketch::<f32>::new(64).unwrap(); - for i in 0..10_000 { - sketch.update(i as f32); - } - assert!(sketch.is_estimation_mode()); - - sketch.reset(); - - assert_eq!(sketch.k(), 64); - assert_eq!(sketch.min_k(), 64); - assert!(sketch.is_empty()); - assert!(!sketch.is_estimation_mode()); - assert_eq!(sketch.n(), 0); - assert_eq!(sketch.num_retained(), 0); - assert_eq!(sketch.min_item(), None); - assert_eq!(sketch.max_item(), None); -} - -#[test] -fn test_custom_comparator_roundtrip() { - let mut sketch = - KllSketch::<String, NumericStringOrder>::new_with_comparator(200, NumericStringOrder) - .unwrap(); - for item in ["2", "10", "1"] { - sketch.update(item.to_owned()); - } - - assert_eq!(sketch.min_item().map(String::as_str), Some("1")); - assert_eq!(sketch.max_item().map(String::as_str), Some("10")); - assert_eq!( - sketch - .quantile(0.5, SearchCriteria::Inclusive) - .as_deref() - .unwrap(), - "2" - ); - - let bytes = sketch.serialize(); - let decoded = KllSketch::<String, NumericStringOrder>::deserialize_with_comparator( - &bytes, - NumericStringOrder, - ) - .unwrap(); - assert_eq!(decoded.n(), sketch.n()); - assert_eq!(decoded.min_item().map(String::as_str), Some("1")); - assert_eq!(decoded.max_item().map(String::as_str), Some("10")); - assert_eq!( - decoded - .quantile(0.5, SearchCriteria::Inclusive) - .as_deref() - .unwrap(), - "2" - ); -} diff --git a/tests-integration/tests/serde_tests/kll.rs b/tests-integration/tests/serde_tests/kll.rs index aac4099..f8ecbb7 100644 --- a/tests-integration/tests/serde_tests/kll.rs +++ b/tests-integration/tests/serde_tests/kll.rs @@ -20,6 +20,7 @@ //! These tests verify binary compatibility with Apache DataSketches implementations: //! - Java (datasketches-java) //! - C++ (datasketches-cpp) +//! - Go (datasketches-go) //! //! Test data is generated by the reference implementations and stored in: //! `tests/serde_tests/{java_generated_files,cpp_generated_files}/`. @@ -28,8 +29,13 @@ use std::cmp::Ordering; use std::fs; use std::path::PathBuf; +use datasketches::codec::SketchBytes; +use datasketches::codec::SketchSlice; +use datasketches::error::Error; +use datasketches::error::ErrorKind; use datasketches::kll::KllComparator; use datasketches::kll::KllSketch; +use datasketches::kll::KllValue; use crate::serialization_test_data; @@ -48,6 +54,35 @@ impl KllComparator<String> for NumericStringOrder { } } +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct Record { + key: i64, + category: u16, +} + +impl KllValue for Record { + const MIN_SERIALIZED_SIZE: usize = 10; + + fn serialized_size(_value: &Self) -> usize { + 10 + } + + fn serialize(value: &Self, bytes: &mut SketchBytes) { + bytes.write_i64_le(value.key); + bytes.write_u16_le(value.category); + } + + fn deserialize(input: &mut SketchSlice<'_>) -> Result<Self, Error> { + let key = input + .read_i64_le() + .map_err(|_| Error::new(ErrorKind::InvalidData, "missing record key"))?; + let category = input + .read_u16_le() + .map_err(|_| Error::new(ErrorKind::InvalidData, "missing record category"))?; + Ok(Self { key, category }) + } +} + fn test_f32_file(path: PathBuf, expected_n: usize) { let bytes = fs::read(&path).unwrap(); let sketch = KllSketch::<f32>::deserialize(&bytes) @@ -324,6 +359,55 @@ fn test_cpp_kll_string_compatibility() { } } +#[test] +fn test_go_kll_float_compatibility() { + for n in [0, 1, 10, 100, 1000, 10000, 100000, 1000000] { + let path = serialization_test_data("go_generated_files", &format!("kll_float_n{n}_go.sk")); + test_f32_file(path, n); + } +} + +#[test] +fn test_go_kll_double_compatibility() { + for n in [0, 1, 10, 100, 1000, 10000, 100000, 1000000] { + let path = serialization_test_data("go_generated_files", &format!("kll_double_n{n}_go.sk")); + test_f64_file(path, n); + } +} + +#[test] +fn test_go_kll_long_compatibility() { + for n in [0, 1, 10, 100, 1000, 10000, 100000, 1000000] { + let path = serialization_test_data("go_generated_files", &format!("kll_long_n{n}_go.sk")); + test_i64_file(path, n); + } +} + +#[test] +fn test_go_kll_string_compatibility() { + for n in [0, 1, 10, 100, 1000, 10000, 100000, 1000000] { + let path = serialization_test_data("go_generated_files", &format!("kll_string_n{n}_go.sk")); + test_string_file(path, n); + } +} + +#[test] +fn test_custom_kll_value_roundtrip() { + let mut sketch = KllSketch::<Record>::new(64).unwrap(); + for key in 0..1_000 { + sketch.update(Record { + key, + category: (key % 7) as u16, + }); + } + + let decoded = KllSketch::<Record>::deserialize(&sketch.serialize()).unwrap(); + + assert_eq!(decoded, sketch); + assert_eq!(decoded.n(), 1_000); + assert_eq!(decoded.num_retained(), sketch.num_retained()); +} + #[test] fn test_rejects_truncated_or_trailing_data() { let mut sketch = KllSketch::<f32>::default(); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
