1use hpr_core::random::SeededRng;
48use serde::{Deserialize, Serialize};
49
50use super::{Factor, check_factors, check_outputs, check_size};
51use crate::error::AnalysisError;
52
53pub const MAX_POPULATION_POINTS: usize = 1 << 24;
55
56pub const MAX_LEVELS: usize = 1 << 16;
58
59#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
62#[serde(try_from = "MorrisData")]
63pub struct Morris {
64 factors: Vec<Factor>,
65 levels: usize,
66 paths: usize,
67}
68
69#[derive(Deserialize)]
71#[serde(deny_unknown_fields)]
72struct MorrisData {
73 factors: Vec<Factor>,
74 levels: usize,
75 paths: usize,
76}
77
78impl TryFrom<MorrisData> for Morris {
79 type Error = AnalysisError;
80
81 fn try_from(data: MorrisData) -> Result<Self, AnalysisError> {
82 Self::new(data.factors, data.levels, data.paths)
83 }
84}
85
86#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
88#[non_exhaustive]
89pub struct Path {
90 pub start: Vec<usize>,
92 pub order: Vec<usize>,
94 pub up: Vec<bool>,
96}
97
98#[derive(Debug, Clone, PartialEq)]
101pub struct MorrisDesign {
102 factors: Vec<Factor>,
103 levels: usize,
104 paths: Vec<Path>,
105}
106
107#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
110#[non_exhaustive]
111pub struct ElementaryEffects {
112 pub name: String,
114 pub count: usize,
116 pub mean: f64,
118 pub mean_absolute: f64,
120 pub standard_deviation: f64,
123 pub mean_absolute_standard_error: f64,
126}
127
128#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
130#[non_exhaustive]
131pub struct Screening {
132 pub levels: usize,
134 pub step: f64,
136 pub effects: Vec<ElementaryEffects>,
138}
139
140impl Morris {
141 pub fn new(factors: Vec<Factor>, levels: usize, paths: usize) -> Result<Self, AnalysisError> {
154 check_factors(&factors)?;
155 if levels < 2 {
156 return Err(AnalysisError::TooFew {
157 what: "grid levels",
158 count: levels,
159 minimum: 2,
160 });
161 }
162 if levels > MAX_LEVELS {
163 return Err(AnalysisError::Count {
164 what: "grid levels",
165 count: levels,
166 limit: MAX_LEVELS,
167 });
168 }
169 if !levels.is_multiple_of(2) {
170 return Err(AnalysisError::Unsupported(format!(
171 "{levels} grid levels: Morris's step is a whole number of levels only for an even number"
172 )));
173 }
174 if paths < 2 {
175 return Err(AnalysisError::TooFew {
176 what: "Morris paths",
177 count: paths,
178 minimum: 2,
179 });
180 }
181 let k = factors.len();
182 check_size("Morris points", paths, k.saturating_add(1), k)?;
183 Ok(Self {
184 factors,
185 levels,
186 paths,
187 })
188 }
189
190 pub fn factors(&self) -> &[Factor] {
192 &self.factors
193 }
194
195 pub fn levels(&self) -> usize {
197 self.levels
198 }
199
200 pub fn paths(&self) -> usize {
202 self.paths
203 }
204
205 pub fn step(&self) -> f64 {
207 step(self.levels)
208 }
209
210 pub fn design(&self, seed: u64) -> MorrisDesign {
215 let k = self.factors.len();
216 let half = self.levels / 2;
217 let paths = (0..self.paths)
218 .map(|j| {
219 let mut rng = SeededRng::for_stream(seed, &[j as u64]);
221 let start: Vec<usize> = (0..k).map(|_| pick(&mut rng, half)).collect();
222 let up: Vec<bool> = (0..k).map(|_| rng.uniform() < 0.5).collect();
223 let mut order: Vec<usize> = (0..k).collect();
224 for i in (1..k).rev() {
225 order.swap(i, pick(&mut rng, i + 1));
226 }
227 let start = start
229 .iter()
230 .zip(&up)
231 .map(|(&level, &up)| if up { level } else { level + half })
232 .collect();
233 Path { start, order, up }
234 })
235 .collect();
236 MorrisDesign {
237 factors: self.factors.clone(),
238 levels: self.levels,
239 paths,
240 }
241 }
242
243 pub fn screen(
250 &self,
251 seed: u64,
252 mut model: impl FnMut(&[f64]) -> f64,
253 ) -> Result<Screening, AnalysisError> {
254 let design = self.design(seed);
255 let outputs: Vec<f64> = design.points().iter().map(|x| model(x)).collect();
256 design.analyze(&outputs)
257 }
258
259 pub fn population(
270 &self,
271 mut model: impl FnMut(&[f64]) -> f64,
272 ) -> Result<Vec<ElementaryEffects>, AnalysisError> {
273 let k = self.factors.len();
274 let p = self.levels;
275 let total = (0..k).fold(1_usize, |n, _| n.saturating_mul(p));
276 if total > MAX_POPULATION_POINTS {
277 return Err(AnalysisError::Count {
278 what: "Morris grid points",
279 count: total,
280 limit: MAX_POPULATION_POINTS,
281 });
282 }
283 let mut levels = vec![0_usize; k];
284 let mut point = vec![0.0; k];
285 let mut outputs = Vec::with_capacity(total);
286 for index in 0..total {
287 let mut rest = index;
288 for (level, (x, factor)) in levels.iter_mut().zip(point.iter_mut().zip(&self.factors)) {
289 *level = rest % p;
290 rest /= p;
291 *x = factor.at(unit(*level, p));
292 }
293 let y = model(&point);
294 if !y.is_finite() {
295 return Err(AnalysisError::Output { index, value: y });
296 }
297 outputs.push(y);
298 }
299 let delta = self.step();
300 let half = p / 2;
301 let mut stride = 1;
302 let mut effects = Vec::with_capacity(k);
303 for factor in &self.factors {
304 let mut ds = Vec::with_capacity(total / 2);
305 for (index, &lower) in outputs.iter().enumerate() {
306 if (index / stride) % p < half {
307 ds.push((outputs[index + half * stride] - lower) / delta);
308 }
309 }
310 effects.push(moments(factor.name(), &ds, false));
311 stride *= p;
312 }
313 Ok(effects)
314 }
315}
316
317impl MorrisDesign {
318 pub fn paths(&self) -> &[Path] {
320 &self.paths
321 }
322
323 pub fn len(&self) -> usize {
325 self.paths.len() * (self.factors.len() + 1)
326 }
327
328 pub fn is_empty(&self) -> bool {
330 self.len() == 0
331 }
332
333 pub fn points(&self) -> Vec<Vec<f64>> {
336 let half = self.levels / 2;
337 let p = self.levels;
338 let mut points = Vec::with_capacity(self.len());
339 for path in &self.paths {
340 let mut levels = path.start.clone();
341 points.push(self.at(&levels));
342 for &i in &path.order {
343 levels[i] = if path.up[i] {
344 levels[i] + half
345 } else {
346 levels[i] - half
347 };
348 debug_assert!(levels[i] < p, "a path stays on the grid");
349 points.push(self.at(&levels));
350 }
351 }
352 points
353 }
354
355 fn at(&self, levels: &[usize]) -> Vec<f64> {
357 levels
358 .iter()
359 .zip(&self.factors)
360 .map(|(&level, factor)| factor.at(unit(level, self.levels)))
361 .collect()
362 }
363
364 pub fn analyze(&self, outputs: &[f64]) -> Result<Screening, AnalysisError> {
374 check_outputs(outputs, self.len())?;
375 let k = self.factors.len();
376 let delta = step(self.levels);
377 let mut effects = (0..k)
378 .map(|_| Vec::with_capacity(self.paths.len()))
379 .collect::<Vec<_>>();
380 for (path, ys) in self.paths.iter().zip(outputs.chunks_exact(k + 1)) {
381 for (s, &i) in path.order.iter().enumerate() {
382 let change = ys[s + 1] - ys[s];
383 effects[i].push(if path.up[i] { change } else { -change } / delta);
384 }
385 }
386 Ok(Screening {
387 levels: self.levels,
388 step: delta,
389 effects: self
390 .factors
391 .iter()
392 .zip(&effects)
393 .map(|(factor, ds)| moments(factor.name(), ds, true))
394 .collect(),
395 })
396 }
397}
398
399fn step(levels: usize) -> f64 {
401 (levels / 2) as f64 / (levels - 1) as f64
403}
404
405fn unit(level: usize, levels: usize) -> f64 {
407 level as f64 / (levels - 1) as f64
409}
410
411fn pick(rng: &mut SeededRng, n: usize) -> usize {
413 ((rng.uniform() * n as f64) as usize).min(n - 1)
415}
416
417fn moments(name: &str, ds: &[f64], sample: bool) -> ElementaryEffects {
420 let n = ds.len() as f64;
422 let mean = ds.iter().sum::<f64>() / n;
423 let mean_absolute = ds.iter().map(|d| d.abs()).sum::<f64>() / n;
424 let squares = |center: f64, abs: bool| {
425 ds.iter()
426 .map(|&d| {
427 let e = if abs { d.abs() } else { d } - center;
428 e * e
429 })
430 .sum::<f64>()
431 };
432 let (standard_deviation, mean_absolute_standard_error) = if sample {
433 (
434 (squares(mean, false) / (n - 1.0)).sqrt(),
435 (squares(mean_absolute, true) / (n - 1.0) / n).sqrt(),
436 )
437 } else {
438 ((squares(mean, false) / n).sqrt(), 0.0)
439 };
440 ElementaryEffects {
441 name: name.to_owned(),
442 count: ds.len(),
443 mean,
444 mean_absolute,
445 standard_deviation,
446 mean_absolute_standard_error,
447 }
448}
449
450#[cfg(test)]
451mod tests {
452 use super::*;
453
454 fn unit_factors(k: usize) -> Vec<Factor> {
455 (0..k)
456 .map(|i| Factor::new(format!("x{i}"), 0.0, 1.0).unwrap())
457 .collect()
458 }
459
460 #[test]
461 fn the_step_is_half_the_levels() {
462 let m = Morris::new(unit_factors(2), 4, 2).unwrap();
463 assert_eq!(m.step(), 2.0 / 3.0);
464 assert_eq!(Morris::new(unit_factors(2), 2, 2).unwrap().step(), 1.0);
465 assert_eq!(
466 Morris::new(unit_factors(2), 8, 2).unwrap().step(),
467 4.0 / 7.0
468 );
469 }
470
471 #[test]
472 fn a_screening_refuses_what_it_cant_lay_out() {
473 assert!(matches!(
474 Morris::new(Vec::new(), 4, 10),
475 Err(AnalysisError::TooFew {
476 what: "factors",
477 ..
478 })
479 ));
480 assert!(matches!(
481 Morris::new(unit_factors(2), 0, 10),
482 Err(AnalysisError::TooFew {
483 what: "grid levels",
484 count: 0,
485 ..
486 })
487 ));
488 match Morris::new(unit_factors(2), 5, 10) {
489 Err(AnalysisError::Unsupported(why)) => assert!(why.starts_with("5 grid levels")),
490 other => panic!("{other:?}"),
491 }
492 assert!(matches!(
493 Morris::new(unit_factors(2), MAX_LEVELS + 2, 10),
494 Err(AnalysisError::Count {
495 what: "grid levels",
496 limit: MAX_LEVELS,
497 ..
498 })
499 ));
500 assert!(Morris::new(unit_factors(2), MAX_LEVELS, 10).is_ok());
501 assert!(matches!(
502 Morris::new(unit_factors(2), 4, 1),
503 Err(AnalysisError::TooFew {
504 what: "Morris paths",
505 count: 1,
506 ..
507 })
508 ));
509 assert!(matches!(
511 Morris::new(unit_factors(1), 4, 1 << 62),
512 Err(AnalysisError::Count {
513 what: "Morris points",
514 limit: crate::sensitivity::MAX_DESIGN_POINTS,
515 ..
516 })
517 ));
518 assert!(Morris::new(unit_factors(1), 4, 1 << 19).is_ok());
519 assert!(matches!(
520 Morris::new(unit_factors(2), 4, usize::MAX / 2),
521 Err(AnalysisError::Count {
522 what: "Morris points",
523 count: usize::MAX,
524 ..
525 })
526 ));
527 }
528
529 #[test]
530 fn every_path_steps_each_factor_once_by_delta_and_stays_on_the_grid() {
531 let m = Morris::new(unit_factors(5), 6, 40).unwrap();
532 let design = m.design(7);
533 let points = design.points();
534 assert_eq!(points.len(), 40 * 6);
535 for (path, chunk) in design.paths().iter().zip(points.as_chunks::<6>().0) {
536 let mut order = path.order.clone();
537 order.sort_unstable();
538 assert_eq!(order, (0..5).collect::<Vec<_>>());
539 for (s, &i) in path.order.iter().enumerate() {
540 for (j, (after, before)) in chunk[s + 1].iter().zip(&chunk[s]).enumerate() {
541 let moved = after - before;
542 if j == i {
543 let expected = if path.up[i] { 0.6 } else { -0.6 };
544 assert!((moved - expected).abs() < 1e-15, "{moved}");
545 } else {
546 assert_eq!(moved, 0.0);
547 }
548 }
549 }
550 for x in chunk.iter().flatten() {
551 assert!((0.0..=1.0).contains(x));
552 let level = x * 5.0;
553 assert!((level - level.round()).abs() < 1e-12);
554 }
555 }
556 }
557
558 #[test]
559 fn path_j_is_the_same_however_many_are_drawn() {
560 let short = Morris::new(unit_factors(4), 4, 3).unwrap().design(11);
561 let long = Morris::new(unit_factors(4), 4, 30).unwrap().design(11);
562 assert_eq!(short.paths(), &long.paths()[..3]);
563 assert_ne!(long.paths()[3], long.paths()[4]);
564 let other = Morris::new(unit_factors(4), 4, 3).unwrap().design(12);
565 assert_ne!(short.paths(), other.paths());
566 }
567
568 #[test]
569 fn a_linear_model_has_its_slopes_as_every_effect() {
570 let factors = vec![
572 Factor::new("a", 0.0, 1.0).unwrap(),
573 Factor::new("b", -1.0, 3.0).unwrap(),
574 Factor::new("c", 5.0, 6.0).unwrap(),
575 ];
576 let screening = Morris::new(factors, 4, 12)
577 .unwrap()
578 .screen(3, |x| 3.0 * x[0] - 2.0 * x[1])
579 .unwrap();
580 let expected = [3.0, -8.0, 0.0];
581 for (e, want) in screening.effects.iter().zip(expected) {
582 assert_eq!(e.count, 12);
583 assert!((e.mean - want).abs() < 1e-12, "{e:?}");
584 assert!((e.mean_absolute - want.abs()).abs() < 1e-12, "{e:?}");
585 assert!(e.standard_deviation < 1e-12, "{e:?}");
586 assert!(e.mean_absolute_standard_error < 1e-12, "{e:?}");
587 }
588 }
589
590 #[test]
591 fn a_step_down_gives_the_effect_at_the_lower_point() {
592 let m = Morris::new(unit_factors(1), 2, 6).unwrap();
594 let design = m.design(1);
595 assert!(design.paths().iter().any(|p| p.up[0]));
596 assert!(design.paths().iter().any(|p| !p.up[0]));
597 let outputs: Vec<f64> = design.points().iter().map(|x| x[0] * x[0]).collect();
598 let e = &design.analyze(&outputs).unwrap().effects[0];
599 assert_eq!(
600 (e.mean, e.mean_absolute, e.standard_deviation),
601 (1.0, 1.0, 0.0)
602 );
603 }
604
605 #[test]
606 fn the_population_of_a_product_is_its_closed_form() {
607 let m = Morris::new(unit_factors(2), 4, 2).unwrap();
609 let population = m.population(|x| x[0] * x[1]).unwrap();
610 let levels = [0.0, 1.0 / 3.0, 2.0 / 3.0, 1.0];
611 let mean = levels.iter().sum::<f64>() / 4.0;
612 let variance = levels.iter().map(|l| (l - mean).powi(2)).sum::<f64>() / 4.0;
613 for e in &population {
614 assert_eq!(e.count, 8);
615 assert!((e.mean - mean).abs() < 1e-15);
616 assert!((e.mean_absolute - mean).abs() < 1e-15);
617 assert!((e.standard_deviation - variance.sqrt()).abs() < 1e-15);
618 assert_eq!(e.mean_absolute_standard_error, 0.0);
619 }
620 }
621
622 #[test]
623 fn the_population_refuses_a_grid_too_large_and_names_a_bad_point() {
624 let m = Morris::new(unit_factors(13), 4, 2).unwrap();
625 assert!(matches!(
626 m.population(|_| 0.0),
627 Err(AnalysisError::Count {
628 what: "Morris grid points",
629 count: 67_108_864,
630 limit: MAX_POPULATION_POINTS,
631 })
632 ));
633 let m = Morris::new(unit_factors(2), 4, 2).unwrap();
634 match m.population(|x| {
636 if x == [2.0 / 3.0, 1.0 / 3.0] {
637 f64::NAN
638 } else {
639 0.0
640 }
641 }) {
642 Err(AnalysisError::Output { index, .. }) => assert_eq!(index, 6),
643 other => panic!("{other:?}"),
644 }
645 }
646
647 #[test]
648 fn a_screening_reads_back_through_its_checks() {
649 let m = Morris::new(unit_factors(2), 4, 10).unwrap();
650 let json = serde_json::to_string(&m).unwrap();
651 assert_eq!(serde_json::from_str::<Morris>(&json).unwrap(), m);
652 let odd = json.replace("\"levels\":4", "\"levels\":3");
653 let refused = serde_json::from_str::<Morris>(&odd)
654 .unwrap_err()
655 .to_string();
656 assert!(refused.contains("3 grid levels"), "{refused}");
657 }
658}