tisonkun commented on code in PR #168:
URL: https://github.com/apache/datasketches-rust/pull/168#discussion_r3664279518
##########
datasketches/tests/tuple_test/a_not_b.rs:
##########
@@ -15,228 +15,155 @@
// specific language governing permissions and limitations
// under the License.
-//! Behavioral tests for the Tuple a-not-B (set difference) operator.
-//!
-//! The result of `a and not b` retains the keys of `a` that are absent from
`b`, keeping the
-//! summaries from `a`. These tests use a `u64` summary with the default
additive update policy,
-//! so the distinct-count behavior matches a plain Theta a-not-B.
-
+use datasketches::common::NumStdDev;
+use datasketches::error::ErrorKind;
use datasketches::tuple::CompactTupleSketch;
use datasketches::tuple::TupleANotB;
use super::default_tuple_sketch_builder;
use super::tuple_sketch_with_range;
+fn sorted_entries(sketch: &CompactTupleSketch<u64>) -> Vec<(u64, u64)> {
+ let mut entries: Vec<_> = sketch
+ .iter()
+ .map(|(hash, &summary)| (hash, summary))
+ .collect();
+ entries.sort_unstable();
+ entries
+}
+
#[test]
-fn test_basic_difference_keeps_summaries_from_a() {
+fn difference_keeps_only_a_summaries() {
let mut a = default_tuple_sketch_builder().build();
a.update("shared", 3u64);
a.update("only_a", 5u64);
let mut b = default_tuple_sketch_builder().build();
b.update("shared", 9u64);
b.update("only_b", 7u64);
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
+ let result = TupleANotB::default().compute(&a, &b, true).unwrap();
- // "shared" is subtracted; "only_a" survives with A's summary.
- assert_eq!(r.num_retained(), 1);
- assert_eq!(r.iter().next().unwrap().1, &5);
- assert!(!r.is_estimation_mode());
- assert_eq!(r.estimate(), 1.0);
+ assert_eq!(result.num_retained(), 1);
+ assert_eq!(result.estimate(), 1.0);
+ assert_eq!(result.iter().next().unwrap().1, &5);
}
#[test]
-fn test_accepts_updatable_and_compact_inputs() {
+fn accepts_mutable_and_compact_inputs() {
let a = tuple_sketch_with_range(0, 1000);
let b = tuple_sketch_with_range(500, 1000);
+ let op = TupleANotB::default();
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a.compact(true), &b, true).unwrap();
- assert_eq!(r.num_retained(), 500);
-
- let r = a_not_b.compute(&a, &b.compact(false), true).unwrap();
- assert_eq!(r.num_retained(), 500);
-}
-
-#[test]
-fn test_seed_mismatch_returns_error() {
- let mut one_other_seed = default_tuple_sketch_builder().seed(2).build();
- one_other_seed.update("value", 1u64);
- let good = tuple_sketch_with_range(0, 10);
-
- let a_not_b = TupleANotB::with_seed(1);
- assert!(a_not_b.compute(&one_other_seed, &good, true).is_err());
- assert!(a_not_b.compute(&good, &one_other_seed, true).is_err());
-}
-
-#[test]
-fn test_seed_mismatch_ignored_for_empty_inputs() {
- // Empty inputs carry no keys, so their seeds are not validated.
- let empty_other_seed = default_tuple_sketch_builder().seed(2).build();
- let good = tuple_sketch_with_range(0, 10);
-
- let a_not_b = TupleANotB::default();
-
- let r = a_not_b.compute(&empty_other_seed, &good, true).unwrap();
- assert!(r.is_empty());
-
- let r = a_not_b.compute(&good, &empty_other_seed, true).unwrap();
- assert_eq!(r.num_retained(), 10);
-}
-
-#[test]
-fn test_empty_a_returns_empty() {
- let empty = default_tuple_sketch_builder().build();
- let b = tuple_sketch_with_range(0, 1000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&empty, &b, true).unwrap();
-
- assert!(r.is_empty());
- assert_eq!(r.num_retained(), 0);
- assert_eq!(r.estimate(), 0.0);
-}
-
-#[test]
-fn test_empty_b_returns_a() {
- let a = tuple_sketch_with_range(0, 1000);
- let empty = default_tuple_sketch_builder().build();
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &empty, true).unwrap();
-
- assert_eq!(r.num_retained(), 1000);
- assert_eq!(r.estimate(), 1000.0);
-}
-
-#[test]
-fn test_exact_partial_overlap_unordered() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(500, 1000);
-
- let a_not_b = TupleANotB::default();
- let r = a_not_b.compute(&a, &b, true).unwrap();
+ let mutable_result = op.compute(&a, &b, true).unwrap();
+ let compact_result = op
+ .compute(&a.compact(true), &b.compact(false), true)
+ .unwrap();
- // Keys 0..500 survive (exact mode).
- assert!(!r.is_empty());
- assert!(!r.is_estimation_mode());
- assert_eq!(r.num_retained(), 500);
- assert_eq!(r.estimate(), 500.0);
+ assert_eq!(
+ sorted_entries(&mutable_result),
+ sorted_entries(&compact_result)
+ );
+ assert_eq!(mutable_result.num_retained(), 500);
}
#[test]
-fn test_exact_partial_overlap_ordered() {
- let a = tuple_sketch_with_range(0, 1000);
- let b = tuple_sketch_with_range(500, 1000);
+fn ordered_and_unordered_inputs_produce_the_same_result() {
+ let mut a = default_tuple_sketch_builder().lg_k(8).build();
+ let mut b = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..20_000 {
+ a.update(value, 1u64);
+ }
+ for value in 10_000..30_000 {
+ b.update(value, 1u64);
+ }
- let a_not_b = TupleANotB::default();
- let r = a_not_b
+ let op = TupleANotB::default();
+ let unordered = op.compute(&a, &b, true).unwrap();
+ let ordered = op
.compute(&a.compact(true), &b.compact(true), true)
.unwrap();
Review Comment:
Good catch. The public result-ordering contract had been dropped during
consolidation. Restored in `c6579ff`: the test now exercises both
`ordered=true` and `ordered=false`, verifies `is_ordered()` follows the
request, and confirms theta and retained entries are unchanged.
##########
datasketches/tests/tuple_test/sketch.rs:
##########
@@ -17,284 +17,188 @@
use datasketches::common::NumStdDev;
use datasketches::hash_value;
+use datasketches::tuple::CompactTupleSketch;
+use datasketches::tuple::DefaultUpdatePolicy;
+use datasketches::tuple::SummaryPolicy;
+use datasketches::tuple::SummaryUpdatePolicy;
+use datasketches::tuple::TupleSketch;
+use datasketches::tuple::TupleSketchBuilder;
use super::default_tuple_sketch_builder;
#[test]
-fn test_basic_update() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- assert!(sketch.is_empty());
- assert_eq!(sketch.estimate(), 0.0);
-
- sketch.update("value1", 1u64);
- assert!(!sketch.is_empty());
- assert_eq!(sketch.estimate(), 1.0);
+fn updates_distinct_keys_and_accumulates_summaries() {
+ let mut sketch = default_tuple_sketch_builder().build();
+ sketch.update("shared", 2u64);
+ sketch.update("shared", 3u64);
+ sketch.update("other", 7u64);
- sketch.update("value2", 1u64);
assert_eq!(sketch.estimate(), 2.0);
-}
+ assert_eq!(sketch.num_retained(), 2);
-#[test]
-fn test_summary_accumulates_per_key() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- for _ in 0..5 {
- sketch.update("same_key", 2u64);
- }
- assert_eq!(sketch.estimate(), 1.0);
- assert_eq!(sketch.num_retained(), 1);
- // The default policy folds each update into the retained summary: 5 * 2
== 10.
- assert_eq!(sketch.iter().next().unwrap().1, &10);
+ let mut summaries: Vec<u64> = sketch.iter().map(|(_, &summary)|
summary).collect();
+ summaries.sort_unstable();
+ assert_eq!(summaries, [5, 7]);
}
#[test]
-fn test_update_various_types() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
- sketch.update("string", 1u64);
- sketch.update(42i64, 1u64);
- sketch.update(42u64, 1u64);
- // where floating-point numbers have different representations
- sketch.update(hash_value::canonical_float::from_f64(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f64(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(3.15), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(3.15), 1u64);
- sketch.update([1u8, 2, 3], 1u64);
-
- assert!(!sketch.is_empty());
- assert_eq!(sketch.estimate(), 5.0);
-
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
+fn accepts_supported_hash_representations() {
+ let mut sketch = default_tuple_sketch_builder().build();
sketch.update("string", 1u64);
sketch.update(42i64, 1u64);
sketch.update(42u64, 1u64);
- // where floating-point numbers have the same representation
- sketch.update(hash_value::canonical_float::from_f64(5.0), 1u64);
sketch.update(hash_value::canonical_float::from_f64(5.0), 1u64);
sketch.update(hash_value::canonical_float::from_f32(5.0), 1u64);
- sketch.update(hash_value::canonical_float::from_f32(5.0), 1u64);
sketch.update([1u8, 2, 3], 1u64);
- assert!(!sketch.is_empty());
assert_eq!(sketch.estimate(), 4.0);
}
#[test]
-fn test_duplicate_updates() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
+fn default_update_policy_accepts_distinct_rhs_type() {
+ let mut sketch =
TupleSketchBuilder::new(DefaultUpdatePolicy::<String>::default()).build();
+ sketch.update("key", "hello");
+ sketch.update("key", " world");
- for _ in 0..100 {
- sketch.update("same_value", 1u64);
- }
+ assert_eq!(sketch.iter().next().unwrap().1, "hello world");
+}
- assert_eq!(sketch.estimate(), 1.0);
+struct ArraySumPolicy {
+ num_values: usize,
}
-#[test]
-fn test_theta_reduction() {
- let mut sketch = default_tuple_sketch_builder().lg_k(5).build(); // Small
k to trigger theta reduction
- assert!(!sketch.is_estimation_mode());
+impl SummaryPolicy for ArraySumPolicy {
+ type Summary = Vec<f64>;
- // Insert many values to trigger theta reduction
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
+ fn create(&self) -> Self::Summary {
+ vec![0.0; self.num_values]
}
-
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
}
-#[test]
-fn test_trim() {
- let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
-
- // Insert many values
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
+impl<U> SummaryUpdatePolicy<U> for ArraySumPolicy
+where
+ U: AsRef<[f64]>,
+{
+ fn update(&self, summary: &mut Self::Summary, value: U) {
+ let value = value.as_ref();
+ assert_eq!(value.len(), self.num_values);
+ for (summary, value) in summary.iter_mut().zip(value) {
+ *summary += value;
+ }
}
+}
- let before_trim = sketch.num_retained();
- sketch.trim();
- let after_trim = sketch.num_retained();
+#[test]
+fn custom_update_policy_accepts_multiple_value_representations() {
+ let mut sketch = TupleSketchBuilder::new(ArraySumPolicy { num_values: 2
}).build();
+ sketch.update("key", &[1.0, 2.0]);
+ sketch.update("key", vec![3.0, 4.0]);
- // After trim, should have approximately k entries
- assert!(after_trim <= before_trim);
- assert_eq!(sketch.num_retained(), 32);
+ assert_eq!(sketch.num_retained(), 1);
+ assert_eq!(sketch.iter().next().unwrap().1.as_slice(), [4.0, 6.0]);
}
#[test]
-fn test_reset() {
+fn trim_and_reset_update_public_state() {
let mut sketch = default_tuple_sketch_builder().lg_k(5).build();
-
- // Insert many values
- for i in 0..1000 {
- sketch.update(format!("value_{}", i), 1u64);
+ for value in 0..1000 {
+ sketch.update(value, 1u64);
}
- assert!(!sketch.is_empty());
+
+ sketch.trim();
+ assert_eq!(sketch.num_retained(), 32);
assert!(sketch.is_estimation_mode());
- assert!(sketch.num_retained() > 32);
- assert!(sketch.theta() < 1.0);
sketch.reset();
assert!(sketch.is_empty());
+ assert_eq!(sketch.num_retained(), 0);
assert_eq!(sketch.estimate(), 0.0);
assert_eq!(sketch.theta(), 1.0);
- assert_eq!(sketch.num_retained(), 0);
assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
}
#[test]
-fn test_iterator() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
-
- sketch.update("value1", 1u64);
- sketch.update("value2", 1u64);
- sketch.update("value3", 1u64);
+fn bounds_cover_exact_and_estimation_results() {
+ let mut exact = default_tuple_sketch_builder().build();
+ for value in 0..100 {
+ exact.update(value, 1u64);
+ }
+ assert_eq!(exact.lower_bound(NumStdDev::One), 100.0);
+ assert_eq!(exact.upper_bound(NumStdDev::Three), 100.0);
- let count: usize = sketch.iter().count();
- assert_eq!(count, sketch.num_retained());
+ let mut estimated = default_tuple_sketch_builder().lg_k(8).build();
+ for value in 0..50_000 {
+ estimated.update(value, 1u64);
+ }
+ let estimate = estimated.estimate();
+ let lower_one = estimated.lower_bound(NumStdDev::One);
+ let lower_three = estimated.lower_bound(NumStdDev::Three);
+ let upper_one = estimated.upper_bound(NumStdDev::One);
+ let upper_three = estimated.upper_bound(NumStdDev::Three);
+
+ assert!(estimated.is_estimation_mode());
+ assert!(lower_three <= lower_one);
+ assert!(lower_one < estimate);
+ assert!(estimate < upper_one);
+ assert!(upper_one <= upper_three);
}
#[test]
-fn test_bounds_empty_sketch() {
- let sketch = default_tuple_sketch_builder().lg_k(12).build();
+fn empty_sampled_sketch_has_zero_bounds() {
+ let sketch = default_tuple_sketch_builder()
+ .sampling_probability(0.1)
+ .build();
+
assert!(sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.theta(), 1.0);
+ assert!(sketch.is_estimation_mode());
assert_eq!(sketch.estimate(), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 0.0);
- assert_eq!(sketch.lower_bound(NumStdDev::Two), 0.0);
- assert_eq!(sketch.upper_bound(NumStdDev::Two), 0.0);
assert_eq!(sketch.lower_bound(NumStdDev::Three), 0.0);
assert_eq!(sketch.upper_bound(NumStdDev::Three), 0.0);
}
-#[test]
-fn test_bounds_exact_mode() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- for i in 0..2000 {
- sketch.update(i, 1u64);
- }
- assert!(!sketch.is_empty());
- assert!(!sketch.is_estimation_mode());
- assert_eq!(sketch.theta(), 1.0);
- assert_eq!(sketch.estimate(), 2000.0);
- assert_eq!(sketch.lower_bound(NumStdDev::One), 2000.0);
- assert_eq!(sketch.upper_bound(NumStdDev::One), 2000.0);
+fn sorted_entries<'a>(entries: impl Iterator<Item = (u64, &'a u64)>) ->
Vec<(u64, u64)> {
+ let mut entries: Vec<_> = entries.map(|(hash, &summary)| (hash,
summary)).collect();
+ entries.sort_unstable();
+ entries
}
-#[test]
-fn test_bounds_estimation_mode() {
- let mut sketch = default_tuple_sketch_builder().lg_k(12).build();
- let n = 10000;
- for i in 0..n {
- sketch.update(i, 1u64);
- }
- assert!(!sketch.is_empty());
- assert!(sketch.is_estimation_mode());
- assert!(sketch.theta() < 1.0);
-
- let estimate = sketch.estimate();
- let lower_bound_1 = sketch.lower_bound(NumStdDev::One);
- let upper_bound_1 = sketch.upper_bound(NumStdDev::One);
- let lower_bound_2 = sketch.lower_bound(NumStdDev::Two);
- let upper_bound_2 = sketch.upper_bound(NumStdDev::Two);
- let lower_bound_3 = sketch.lower_bound(NumStdDev::Three);
- let upper_bound_3 = sketch.upper_bound(NumStdDev::Three);
-
- // Check estimate is within reasonable margin (2% to be safe)
- assert!(
- (estimate - n as f64).abs() < n as f64 * 0.02,
- "estimate {} is not within 2% of {}",
- estimate,
- n
+fn assert_compact_preserves_state(
+ updatable: &TupleSketch<DefaultUpdatePolicy<u64>>,
+ compact: &CompactTupleSketch<u64>,
+ ordered: bool,
+) {
+ assert_eq!(compact.is_estimation_mode(), updatable.is_estimation_mode());
+ assert_eq!(compact.theta64(), updatable.theta64());
+ assert_eq!(compact.seed_hash(), updatable.seed_hash());
+ assert_eq!(
+ sorted_entries(compact.iter()),
+ sorted_entries(updatable.iter())
);
-
- // Check bounds are in correct order
- assert!(lower_bound_1 < estimate);
- assert!(estimate < upper_bound_1);
- assert!(lower_bound_2 < estimate);
- assert!(estimate < upper_bound_2);
- assert!(lower_bound_3 < estimate);
- assert!(estimate < upper_bound_3);
-
- // Check that wider confidence intervals are indeed wider
- assert!(lower_bound_3 < lower_bound_2);
- assert!(lower_bound_2 < lower_bound_1);
- assert!(upper_bound_1 < upper_bound_2);
- assert!(upper_bound_2 < upper_bound_3);
+ assert_eq!(compact.estimate(), updatable.estimate());
+ assert_eq!(compact.is_ordered(), ordered);
}
#[test]
-fn test_bounds_with_sampling() {
- let mut sketch = default_tuple_sketch_builder()
- .lg_k(12)
- .sampling_probability(0.5)
- .build();
-
- for i in 0..1000 {
- sketch.update(i, 1u64);
+fn compact_preserves_state_in_exact_and_estimation_modes() {
+ for (lg_k, num_updates, expected_estimation_mode) in [(12, 2_000, false),
(5, 5_000, true)] {
+ let mut sketch = default_tuple_sketch_builder().lg_k(lg_k).build();
+ for value in 0..num_updates {
+ sketch.update(value, 1u64);
Review Comment:
Agreed. Fixed in `e10be7e`: every key now receives `key + 1` and `10`, so
summaries vary by key and exercise accumulation. The compact comparison
therefore verifies the hash-summary association in both exact and estimation
modes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
