sva_core/solve/
search.rs

1// Concern: a bounded compass search, asked for each point and told its cost, steps halving onto a grid | Non-concern: what a point costs (mod.rs) | IO: (axes, stops) -> points
2
3use super::vary::{Precision, Vary};
4
5#[derive(Clone, Copy, Debug, PartialEq, Eq)]
6pub enum Stopped {
7    Converged,
8    Budget,
9    Cancelled,
10}
11
12impl Stopped {
13    pub fn name(self) -> &'static str {
14        match self {
15            Stopped::Converged => "converged",
16            Stopped::Budget => "budget",
17            Stopped::Cancelled => "cancelled",
18        }
19    }
20}
21
22#[derive(Clone, Copy, Debug, PartialEq)]
23pub struct Stops {
24    pub max_renders: usize,
25    /// Each axis stops once its step is under this fraction of its first step.
26    pub step_tol: f64,
27    pub cost_tol: f64,
28}
29
30pub const DEFAULT_MAX_RENDERS: usize = 200;
31pub const DEFAULT_STEP_TOL: f64 = 1.0 / 64.0;
32pub const DEFAULT_COST_TOL: f64 = 0.0;
33/// Without `/<step>`, the first step is this fraction of the bounds' span.
34pub const FIRST_STEP_OF_SPAN: f64 = 0.25;
35
36/// One variable's coordinate: itself, or its log on a log scale.
37#[derive(Clone, Debug)]
38struct Axis {
39    lo: f64,
40    hi: f64,
41    log: bool,
42    first: f64,
43    /// Decimals the first step is written to, where values land on a decimal grid.
44    decimals: Option<usize>,
45}
46
47impl Axis {
48    fn of(vary: &Vary, start: f64) -> Axis {
49        let (lo, hi) = match vary.log {
50            true => (vary.lo.ln(), vary.hi.ln()),
51            false => (vary.lo, vary.hi),
52        };
53        let first = match (vary.step, vary.log) {
54            (Some(ratio), true) => ratio.ln(),
55            (Some(step), false) => step,
56            (None, _) => (hi - lo) * FIRST_STEP_OF_SPAN,
57        };
58        let decimals = match vary.log {
59            false => Some(decimals(first).max(decimals(vary.lo)).max(decimals(start))),
60            true => None,
61        };
62        Axis {
63            lo,
64            hi,
65            log: vary.log,
66            first,
67            decimals,
68        }
69    }
70
71    fn value(&self, u: f64) -> f64 {
72        match self.log {
73            true => u.exp().clamp(self.lo.exp(), self.hi.exp()),
74            false => u,
75        }
76    }
77
78    fn coordinate(&self, value: f64) -> f64 {
79        match self.log {
80            true => value.ln(),
81            false => value,
82        }
83    }
84
85    /// On the grid `step` lays from the low bound, inside the bounds.
86    fn snapped(&self, u: f64, step: f64) -> f64 {
87        let k = ((u - self.lo) / step).round();
88        (self.lo + k * step).clamp(self.lo, self.hi)
89    }
90}
91
92fn decimals(v: f64) -> usize {
93    let text = format!("{v}");
94    text.split_once('.').map_or(0, |(_, frac)| frac.len())
95}
96
97pub struct Search {
98    axes: Vec<Axis>,
99    stops: Stops,
100    x: Vec<f64>,
101    best: Option<f64>,
102    steps: Vec<f64>,
103    halvings: u32,
104    poll: Vec<Vec<f64>>,
105    polled: Vec<(Vec<f64>, f64)>,
106    seen: Vec<(Vec<f64>, f64)>,
107    asked: Option<Vec<f64>>,
108    renders: usize,
109    stopped: Option<Stopped>,
110}
111
112pub enum Next {
113    /// The values to render at, one per variable, in the order they were given.
114    Render(Vec<f64>),
115    Done(Stopped),
116}
117
118impl Search {
119    pub fn new(vary: &[Vary], start: &[f64], stops: Stops) -> Search {
120        let axes: Vec<Axis> = vary
121            .iter()
122            .zip(start)
123            .map(|(v, s)| Axis::of(v, *s))
124            .collect();
125        let x = axes
126            .iter()
127            .zip(vary.iter().zip(start))
128            .map(|(axis, (one, v))| {
129                let u = axis.coordinate(*v).clamp(axis.lo, axis.hi);
130                match (one.step, one.log) {
131                    (Some(_), false) => axis.snapped(u, axis.first),
132                    _ => u,
133                }
134            })
135            .collect();
136        let steps = axes.iter().map(|a| a.first).collect();
137        Search {
138            axes,
139            stops,
140            x,
141            best: None,
142            steps,
143            halvings: 0,
144            poll: Vec::new(),
145            polled: Vec::new(),
146            seen: Vec::new(),
147            asked: None,
148            renders: 0,
149            stopped: None,
150        }
151    }
152
153    pub fn values(&self, u: &[f64]) -> Vec<f64> {
154        self.axes.iter().zip(u).map(|(a, u)| a.value(*u)).collect()
155    }
156
157    /// A linear grid's decimals, finer by one per halving; on a log scale, enough significant
158    /// digits that a step still moves the value.
159    pub fn digits(&self) -> Vec<Precision> {
160        self.axes
161            .iter()
162            .zip(&self.steps)
163            .map(|(a, step)| match a.decimals {
164                Some(d) => Precision::Decimals(d + self.halvings as usize),
165                None => Precision::Significant((2.0 - step.log10().floor()).max(3.0) as usize),
166            })
167            .collect()
168    }
169
170    pub fn cancel(&mut self) {
171        self.stopped = Some(Stopped::Cancelled);
172    }
173
174    pub fn tell(&mut self, cost: f64) {
175        let point = self
176            .asked
177            .take()
178            .expect("told the cost of a point it asked");
179        self.renders += 1;
180        self.seen.push((point.clone(), cost));
181        match self.best {
182            None => self.best = Some(cost),
183            Some(_) => self.polled.push((point, cost)),
184        }
185    }
186
187    pub fn next(&mut self) -> Next {
188        loop {
189            if let Some(stopped) = self.stopped {
190                return Next::Done(stopped);
191            }
192            if self.best.is_none() {
193                return self.render(self.x.clone());
194            }
195            if let Some(point) = self.poll.pop() {
196                match self.seen.iter().find(|(p, _)| *p == point) {
197                    Some((_, cost)) => self.polled.push((point, *cost)),
198                    None => return self.render(point),
199                }
200                continue;
201            }
202            if !self.polled.is_empty() {
203                self.moved();
204                continue;
205            }
206            let best = self.best.expect("a first cost");
207            let floors = self.axes.iter().map(|a| a.first * self.stops.step_tol);
208            let fine = self.steps.iter().zip(floors).all(|(s, floor)| *s < floor);
209            if best <= self.stops.cost_tol || fine {
210                self.stopped = Some(Stopped::Converged);
211                continue;
212            }
213            self.poll = self.candidates();
214            if self.poll.is_empty() {
215                self.halve();
216            }
217        }
218    }
219
220    fn render(&mut self, point: Vec<f64>) -> Next {
221        if self.renders >= self.stops.max_renders {
222            self.stopped = Some(Stopped::Budget);
223            return Next::Done(Stopped::Budget);
224        }
225        self.asked = Some(point.clone());
226        Next::Render(self.values(&point))
227    }
228
229    /// `+step` then `-step` on each axis in order, reversed so `pop` takes them in order.
230    fn candidates(&self) -> Vec<Vec<f64>> {
231        let mut out = Vec::new();
232        for (i, axis) in self.axes.iter().enumerate() {
233            for sign in [1.0, -1.0] {
234                let mut y = self.x.clone();
235                y[i] = axis.snapped(self.x[i] + sign * self.steps[i], self.steps[i]);
236                if y[i] != self.x[i] && !out.contains(&y) {
237                    out.push(y);
238                }
239            }
240        }
241        out.reverse();
242        out
243    }
244
245    /// The best of a whole poll, ties to the earliest, moves the point; else every step halves.
246    fn moved(&mut self) {
247        let polled = std::mem::take(&mut self.polled);
248        let best = self.best.expect("a first cost");
249        let winner = polled
250            .into_iter()
251            .fold(None::<(Vec<f64>, f64)>, |held, (p, c)| match &held {
252                Some((_, h)) if *h <= c => held,
253                _ => Some((p, c)),
254            });
255        match winner {
256            Some((point, cost)) if cost < best => {
257                self.x = point;
258                self.best = Some(cost);
259            }
260            _ => self.halve(),
261        }
262    }
263
264    fn halve(&mut self) {
265        self.steps.iter_mut().for_each(|s| *s /= 2.0);
266        self.halvings += 1;
267    }
268}
sva_core/solve/search.rs

sva_core/solve/
search.rs
