ariesdevil commented on code in PR #168:
URL: https://github.com/apache/datasketches-rust/pull/168#discussion_r3664123494
##########
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:
If we use `1u64`, all the keys are always `1u64`, so we cannot ensure
compaction is correct.
```rust
for key in 0..num_updates {
sketch.update(key, key + 1);
sketch.update(key, 10);
}
```
I think this pattern will be better.
--
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]
