1use serde::{Deserialize, Serialize};
30
31use crate::error::AnalysisError;
32
33#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
36#[serde(try_from = "DistributionData")]
37pub struct Distribution {
38 attempted: usize,
39 sorted: Vec<f64>,
40}
41
42#[derive(Deserialize)]
44#[serde(deny_unknown_fields)]
45struct DistributionData {
46 attempted: usize,
47 sorted: Vec<f64>,
48}
49
50impl TryFrom<DistributionData> for Distribution {
51 type Error = AnalysisError;
52
53 fn try_from(data: DistributionData) -> Result<Self, AnalysisError> {
54 Self::new(data.sorted, data.attempted)
55 }
56}
57
58#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
60pub struct Summary {
61 pub attempted: usize,
63 pub count: usize,
65 pub mean: Option<f64>,
67 pub standard_deviation: Option<f64>,
69 pub min: Option<f64>,
71 pub p05: Option<f64>,
73 pub p50: Option<f64>,
75 pub p95: Option<f64>,
77 pub max: Option<f64>,
79 pub p05_counting_missing: Option<CountedQuantile>,
83 pub p95_counting_missing: Option<CountedQuantile>,
86}
87
88#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
91#[serde(rename_all = "snake_case")]
92pub enum MissingEnd {
93 Below,
95 Above,
97}
98
99#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
101#[serde(rename_all = "snake_case")]
102pub enum CountedQuantile {
103 Value(f64),
105 Unbounded,
108}
109
110#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
113pub struct Share {
114 pub low: f64,
116 pub high: f64,
118}
119
120impl Distribution {
121 pub fn new(values: Vec<f64>, attempted: usize) -> Result<Self, AnalysisError> {
129 if values.len() > attempted {
130 return Err(AnalysisError::Count {
131 what: "values in a distribution, against the runs tried",
132 count: values.len(),
133 limit: attempted,
134 });
135 }
136 if let Some(&bad) = values.iter().find(|v| !v.is_finite()) {
137 return Err(AnalysisError::Domain {
138 what: "value in a distribution",
139 value: bad,
140 });
141 }
142 let mut sorted = values;
143 sorted.sort_by(f64::total_cmp);
144 Ok(Self { attempted, sorted })
145 }
146
147 pub fn attempted(&self) -> usize {
149 self.attempted
150 }
151
152 pub fn count(&self) -> usize {
154 self.sorted.len()
155 }
156
157 pub fn missing(&self) -> usize {
159 self.attempted - self.sorted.len()
160 }
161
162 pub fn sorted(&self) -> &[f64] {
164 &self.sorted
165 }
166
167 pub fn min(&self) -> Option<f64> {
169 self.sorted.first().copied()
170 }
171
172 pub fn max(&self) -> Option<f64> {
174 self.sorted.last().copied()
175 }
176
177 pub fn mean(&self) -> Option<f64> {
179 let shift = self.min()?;
180 Some(shift + self.shifted_mean(shift))
181 }
182
183 pub fn standard_deviation(&self) -> Option<f64> {
186 if self.sorted.len() < 2 {
187 return None;
188 }
189 let shift = self.min()?;
190 let mean = self.shifted_mean(shift);
191 let sum_squares: f64 = self
192 .sorted
193 .iter()
194 .map(|&x| {
195 let d = (x - shift) - mean;
196 d * d
197 })
198 .sum();
199 Some((sum_squares / (self.sorted.len() - 1) as f64).sqrt())
201 }
202
203 fn shifted_mean(&self, shift: f64) -> f64 {
205 let sum: f64 = self.sorted.iter().map(|&x| x - shift).sum();
206 sum / self.sorted.len() as f64
208 }
209
210 pub fn quantile(&self, p: f64) -> Result<Option<f64>, AnalysisError> {
217 if !(0.0..=1.0).contains(&p) {
218 return Err(AnalysisError::Domain {
219 what: "quantile probability",
220 value: p,
221 });
222 }
223 let Some(&last) = self.sorted.last() else {
224 return Ok(None);
225 };
226 let h = (self.sorted.len() - 1) as f64 * p;
228 let below = h.floor();
229 let index = below as usize;
230 let Some(&above) = self.sorted.get(index + 1) else {
231 return Ok(Some(last));
232 };
233 let low = self.sorted[index];
234 Ok(Some(low + (h - below) * (above - low)))
235 }
236
237 pub fn quantile_counting_missing(
249 &self,
250 p: f64,
251 end: MissingEnd,
252 ) -> Result<Option<CountedQuantile>, AnalysisError> {
253 if !(0.0..=1.0).contains(&p) {
254 return Err(AnalysisError::Domain {
255 what: "quantile probability",
256 value: p,
257 });
258 }
259 if self.attempted == 0 {
260 return Ok(None);
261 }
262 let missing = self.missing();
263 let value = |j: usize| match end {
265 MissingEnd::Above => self.sorted.get(j).copied(),
266 MissingEnd::Below => j
267 .checked_sub(missing)
268 .and_then(|i| self.sorted.get(i).copied()),
269 };
270 let h = (self.attempted - 1) as f64 * p;
272 let below = h.floor();
273 let index = below as usize;
274 let Some(low) = value(index) else {
275 return Ok(Some(CountedQuantile::Unbounded));
276 };
277 if index + 1 == self.attempted {
278 return Ok(Some(CountedQuantile::Value(low)));
279 }
280 match value(index + 1) {
281 Some(above) => Ok(Some(CountedQuantile::Value(
282 low + (h - below) * (above - low),
283 ))),
284 None if h == below => Ok(Some(CountedQuantile::Value(low))),
286 None => Ok(Some(CountedQuantile::Unbounded)),
287 }
288 }
289
290 pub fn share_at_least(&self, threshold: f64) -> Result<Option<Share>, AnalysisError> {
298 if threshold.is_nan() {
299 return Err(AnalysisError::Domain {
300 what: "threshold of a share",
301 value: threshold,
302 });
303 }
304 if self.attempted == 0 {
305 return Ok(None);
306 }
307 let passed = self.sorted.len() - self.sorted.partition_point(|&x| x < threshold);
308 let attempted = self.attempted as f64;
310 Ok(Some(Share {
311 low: passed as f64 / attempted,
312 high: (passed + self.missing()) as f64 / attempted,
313 }))
314 }
315
316 pub fn summary(&self) -> Summary {
318 let quantile = |p: f64| self.quantile(p).ok().flatten();
320 let counting_missing = |p: f64, end: MissingEnd| {
321 if self.missing() == 0 {
322 None
323 } else {
324 self.quantile_counting_missing(p, end).ok().flatten()
325 }
326 };
327 Summary {
328 attempted: self.attempted,
329 count: self.count(),
330 mean: self.mean(),
331 standard_deviation: self.standard_deviation(),
332 min: self.min(),
333 p05: quantile(0.05),
334 p50: quantile(0.5),
335 p95: quantile(0.95),
336 max: self.max(),
337 p05_counting_missing: counting_missing(0.05, MissingEnd::Below),
338 p95_counting_missing: counting_missing(0.95, MissingEnd::Above),
339 }
340 }
341}
342
343#[cfg(test)]
344mod tests {
345 use super::*;
346
347 #[test]
348 fn equal_values_give_their_value_and_no_spread() {
349 let d = Distribution::new(vec![0.1; 7], 7).unwrap();
352 assert_eq!(d.mean(), Some(0.1));
353 assert_eq!(d.standard_deviation(), Some(0.0));
354 assert_eq!(d.quantile(0.37).unwrap(), Some(0.1));
355 }
356
357 #[test]
358 fn moments_and_quantiles_by_hand() {
359 let d = Distribution::new(vec![4.0, 1.0, 3.0, 2.0], 6).unwrap();
360 assert_eq!(d.sorted(), &[1.0, 2.0, 3.0, 4.0]);
361 assert_eq!((d.count(), d.missing(), d.attempted()), (4, 2, 6));
362 assert_eq!(d.mean(), Some(2.5));
363 assert_eq!(d.standard_deviation(), Some((5.0_f64 / 3.0).sqrt()));
365 assert_eq!(d.quantile(0.0).unwrap(), Some(1.0));
368 assert_eq!(d.quantile(0.5).unwrap(), Some(2.5));
369 assert!((d.quantile(0.9).unwrap().unwrap() - 3.7).abs() < 1e-15);
370 assert_eq!(d.quantile(1.0).unwrap(), Some(4.0));
371 let summary = d.summary();
372 assert_eq!((summary.min, summary.max), (Some(1.0), Some(4.0)));
373 assert_eq!(summary.p50, Some(2.5));
374 }
375
376 #[test]
377 fn a_share_is_bounded_by_the_runs_with_no_value() {
378 let d = Distribution::new(vec![1.0, 2.0, 3.0, 4.0], 6).unwrap();
380 let share = d.share_at_least(3.0).unwrap().unwrap();
381 assert_eq!((share.low, share.high), (2.0 / 6.0, 4.0 / 6.0));
382 let all = Distribution::new(vec![1.0, 2.0], 2).unwrap();
383 let share = all.share_at_least(1.0).unwrap().unwrap();
384 assert_eq!((share.low, share.high), (1.0, 1.0));
385 let share = all.share_at_least(f64::INFINITY).unwrap().unwrap();
386 assert_eq!((share.low, share.high), (0.0, 0.0));
387 let share = all.share_at_least(f64::NEG_INFINITY).unwrap().unwrap();
388 assert_eq!((share.low, share.high), (1.0, 1.0));
389 let none = Distribution::new(vec![], 0).unwrap();
391 assert_eq!(none.share_at_least(1.0).unwrap(), None);
392 assert!(matches!(
393 all.share_at_least(f64::NAN),
394 Err(AnalysisError::Domain {
395 what: "threshold of a share",
396 ..
397 })
398 ));
399 }
400
401 #[test]
402 fn a_quantile_counting_the_missing_runs_by_hand() {
403 let d = Distribution::new(vec![4.0, 1.0, 3.0, 2.0], 6).unwrap();
405 let above = |p| d.quantile_counting_missing(p, MissingEnd::Above).unwrap();
406 let below = |p| d.quantile_counting_missing(p, MissingEnd::Below).unwrap();
407 assert_eq!(above(0.0), Some(CountedQuantile::Value(1.0)));
408 assert_eq!(above(0.5), Some(CountedQuantile::Value(3.5)));
409 assert_eq!(above(0.6), Some(CountedQuantile::Value(4.0)));
411 assert_eq!(above(0.65), Some(CountedQuantile::Unbounded));
412 assert_eq!(above(0.95), Some(CountedQuantile::Unbounded));
413 assert_eq!(below(0.5), Some(CountedQuantile::Value(1.5)));
415 assert_eq!(below(0.4), Some(CountedQuantile::Value(1.0)));
416 assert_eq!(below(0.35), Some(CountedQuantile::Unbounded));
417 assert_eq!(below(0.05), Some(CountedQuantile::Unbounded));
418 assert_eq!(below(1.0), Some(CountedQuantile::Value(4.0)));
419 let none = Distribution::new(vec![], 0).unwrap();
421 assert_eq!(
422 none.quantile_counting_missing(0.5, MissingEnd::Above)
423 .unwrap(),
424 None
425 );
426 let empty = Distribution::new(vec![], 3).unwrap();
427 for end in [MissingEnd::Above, MissingEnd::Below] {
428 assert_eq!(
429 empty.quantile_counting_missing(0.0, end).unwrap(),
430 Some(CountedQuantile::Unbounded)
431 );
432 }
433 for p in [-0.1, 1.1, f64::NAN] {
434 assert!(matches!(
435 d.quantile_counting_missing(p, MissingEnd::Above),
436 Err(AnalysisError::Domain { what: "quantile probability", value })
437 if value.to_bits() == p.to_bits()
438 ));
439 }
440 }
441
442 #[test]
443 fn with_no_missing_run_it_is_the_quantile_bit_for_bit() {
444 let values: Vec<f64> = (0..37)
445 .map(|i| f64::from(i).mul_add(0.37, 1.0).sin())
446 .collect();
447 let d = Distribution::new(values, 37).unwrap();
448 for step in 0..=200 {
449 let p = f64::from(step) / 200.0;
450 let plain = d.quantile(p).unwrap().unwrap();
451 for end in [MissingEnd::Above, MissingEnd::Below] {
452 assert_eq!(
453 d.quantile_counting_missing(p, end).unwrap(),
454 Some(CountedQuantile::Value(plain)),
455 "p = {p}"
456 );
457 }
458 }
459 let summary = d.summary();
461 assert_eq!(summary.p05_counting_missing, None);
462 assert_eq!(summary.p95_counting_missing, None);
463 }
464
465 #[test]
466 fn the_missing_runs_widen_each_tail_toward_its_own_end() {
467 let d = Distribution::new((1..=20).map(f64::from).collect(), 21).unwrap();
471 let summary = d.summary();
472 assert!((summary.p95.unwrap() - 19.05).abs() < 1e-12);
473 assert!((summary.p05.unwrap() - 1.95).abs() < 1e-12);
474 assert_eq!(
475 summary.p95_counting_missing,
476 Some(CountedQuantile::Value(20.0))
477 );
478 assert_eq!(
479 summary.p05_counting_missing,
480 Some(CountedQuantile::Value(1.0))
481 );
482 let d = Distribution::new((1..=19).map(f64::from).collect(), 21).unwrap();
485 let summary = d.summary();
486 assert_eq!(
487 summary.p95_counting_missing,
488 Some(CountedQuantile::Unbounded)
489 );
490 assert_eq!(
491 summary.p05_counting_missing,
492 Some(CountedQuantile::Unbounded)
493 );
494 }
495
496 #[test]
497 fn a_bound_serializes_as_a_value_or_unbounded() {
498 assert_eq!(
499 serde_json::to_string(&CountedQuantile::Value(2.5)).unwrap(),
500 r#"{"value":2.5}"#
501 );
502 assert_eq!(
503 serde_json::to_string(&CountedQuantile::Unbounded).unwrap(),
504 r#""unbounded""#
505 );
506 }
507
508 #[test]
509 fn empty_and_single_samples() {
510 let empty = Distribution::new(vec![], 3).unwrap();
511 assert_eq!(empty.mean(), None);
512 assert_eq!(empty.quantile(0.5).unwrap(), None);
513 assert_eq!(empty.missing(), 3);
514 let one = Distribution::new(vec![2.0], 1).unwrap();
515 assert_eq!(one.mean(), Some(2.0));
516 assert_eq!(one.standard_deviation(), None);
517 assert_eq!(one.quantile(0.3).unwrap(), Some(2.0));
518 }
519
520 #[test]
521 fn a_distribution_reads_back_through_its_checks() {
522 let d = Distribution::new(vec![3.0, 1.0, 2.0], 4).unwrap();
523 let json = serde_json::to_string(&d).unwrap();
524 assert_eq!(json, r#"{"attempted":4,"sorted":[1.0,2.0,3.0]}"#);
525 assert_eq!(serde_json::from_str::<Distribution>(&json).unwrap(), d);
526 let unsorted: Distribution =
528 serde_json::from_str(r#"{"attempted":3,"sorted":[3.0,1.0,2.0]}"#).unwrap();
529 assert_eq!(unsorted.sorted(), &[1.0, 2.0, 3.0]);
530 let error = serde_json::from_str::<Distribution>(r#"{"attempted":1,"sorted":[3.0,1.0]}"#)
531 .unwrap_err();
532 assert!(error.to_string().contains("more than 1"), "{error}");
533 }
534
535 #[test]
536 fn bad_inputs_are_refused() {
537 assert!(matches!(
538 Distribution::new(vec![1.0, f64::NAN], 2),
539 Err(AnalysisError::Domain { what: "value in a distribution", value }) if value.is_nan()
540 ));
541 assert!(matches!(
542 Distribution::new(vec![1.0, 2.0], 1),
543 Err(AnalysisError::Count {
544 count: 2,
545 limit: 1,
546 ..
547 })
548 ));
549 let d = Distribution::new(vec![1.0], 1).unwrap();
550 for p in [-0.1, 1.1, f64::NAN] {
551 assert!(matches!(
552 d.quantile(p),
553 Err(AnalysisError::Domain { what: "quantile probability", value })
554 if value.to_bits() == p.to_bits()
555 ));
556 }
557 }
558}