pub(super) fn score(occurrence: &super::Occurrence) -> f64 {
occurrence.value * super::DEPTH_DECAY.powf(occurrence.depth as f64)
}
pub(super) fn choose<R>(
candidates: &[(usize, f64, u64)],
temperature: f64,
random: &mut R,
) -> Result<usize, String>
where
R: FnMut() -> Result<f64, String>,
{
if temperature == 0.0 {
let maximum = candidates
.iter()
.map(|candidate| candidate.1)
.max_by(f64::total_cmp)
.ok_or_else(|| "Kmap candidate set was empty".to_owned())?;
let maxima: Vec<usize> = candidates
.iter()
.enumerate()
.filter(|(_, candidate)| candidate.1.total_cmp(&maximum).is_eq())
.map(|(index, _)| index)
.collect();
let index = (random_unit(random)? * maxima.len() as f64) as usize;
return maxima
.get(index.min(maxima.len() - 1))
.copied()
.ok_or_else(|| "Kmap maximum candidate set was empty".to_owned());
}
let maximum_log = candidates
.iter()
.map(|candidate| candidate.1.ln())
.max_by(f64::total_cmp)
.ok_or_else(|| "Kmap candidate set was empty".to_owned())?;
let weights: Vec<f64> = candidates
.iter()
.map(|candidate| ((candidate.1.ln() - maximum_log) / temperature).exp())
.collect();
let total: f64 = weights.iter().sum();
let threshold = random_unit(random)? * total;
let mut cumulative = 0.0;
for (index, weight) in weights.into_iter().enumerate() {
cumulative += weight;
if threshold < cumulative {
return Ok(index);
}
}
Ok(candidates.len() - 1)
}
fn random_unit<R>(random: &mut R) -> Result<f64, String>
where
R: FnMut() -> Result<f64, String>,
{
let value = random()?;
if value.is_finite() && (0.0..1.0).contains(&value) {
Ok(value)
} else {
Err("Kmap random value must be finite and in [0, 1)".to_owned())
}
}
pub(super) fn os_random_unit() -> Result<f64, String> {
let mut bytes = [0_u8; 8];
getrandom::fill(&mut bytes).map_err(|error| format!("Kmap randomness failed: {error}"))?;
let value = u64::from_ne_bytes(bytes) >> 11;
Ok(value as f64 / (1_u64 << 53) as f64)
}
#[cfg(test)]
mod tests {
use super::{choose, score};
use crate::affordable;
use crate::{NodeId, Occurrence};
#[test]
fn chooser_preserves_zero_temperature_ties() {
let candidates = [(0, 0.5, 0), (1, 1.0, 0), (2, 1.0, 0)];
let mut random = || Ok(0.75);
assert_eq!(choose(&candidates, 0.0, &mut random), Ok(2));
}
#[test]
fn score_and_budget_boundaries_hold() {
let occurrence = Occurrence::new(NodeId([0; 12]), 2.0, 2);
assert!((score(&occurrence) - 0.98).abs() < 1e-12);
assert!(affordable(0, 3, 0.3).unwrap());
assert!(!affordable(0, 4, 0.3).unwrap());
}
}