wowlab_common/sim/permutations/
cost.rs

1use serde::{Deserialize, Serialize};
2#[cfg(feature = "wasm")]
3use tsify::Tsify;
4use wowlab_types::{
5    constants::HUNDRED,
6    numeric::{f64_to_u64_saturating_ceil, u64_to_f64},
7};
8
9use super::space::{PermutationError, PermutationSpace};
10
11/// Cost row for one screening keep percentage.
12#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
13#[cfg_attr(feature = "wasm", derive(Tsify))]
14#[serde(rename_all = "camelCase")]
15pub struct ScreeningRow {
16    pub keep_pct: f64,
17    pub survivors: u64,
18    pub tournament_cost: u64,
19    pub total_cost: u64,
20    pub savings_pct: f64,
21}
22
23/// Pre-computed cost analysis.
24#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
25#[cfg_attr(feature = "wasm", derive(Tsify))]
26#[serde(rename_all = "camelCase")]
27pub struct CostAnalysis {
28    pub main_effect_iters: u64,
29    pub pair_count: u64,
30    pub pair_iters: u64,
31    pub factorial_total: u64,
32    pub brute_force: u64,
33    pub screening: Vec<ScreeningRow>,
34}
35
36const MAIN_ITERS_PER_ITEM: u64 = 2000;
37const PAIR_ITERS: u64 = 1500;
38const BRUTE_ITERS: u64 = 10000;
39const TOP_K: usize = 4;
40const TOURNAMENT_ITERS_PER_ROUND: u64 = 200;
41const FINAL_STAGE_ITERS: u64 = 50000;
42const FINAL_STAGE_THRESHOLD: u64 = 10;
43const MIN_SURVIVORS: u64 = 100;
44const TOURNAMENT_PAIR_SIZE: u64 = 2;
45#[rustfmt::skip]
46const KEEP_PCTS: [f64; 6] = [
47    0.5,
48    1.0,
49    2.0,
50    5.0,
51    10.0,
52    100.0,
53];
54
55/// Compute cost analysis for a permutation space.
56///
57/// # Errors
58///
59/// Returns an error when the space is invalid or a cost exceeds `u64`.
60pub fn compute_cost_analysis(space: &PermutationSpace) -> Result<CostAnalysis, PermutationError> {
61    space.validate()?;
62    let contested = space.contested_slots();
63    let total_items = u64::from(space.total_candidates());
64    let main_effect_iters = checked_mul(total_items, MAIN_ITERS_PER_ITEM, "main effect cost")?;
65    let pair_count = compute_pair_count(&contested)?;
66    let pair_iters = checked_mul(pair_count, PAIR_ITERS, "pair iteration cost")?;
67    let factorial_total = checked_add(main_effect_iters, pair_iters, "factorial total")?;
68    let brute_force = checked_mul(space.total(), BRUTE_ITERS, "brute force cost")?;
69
70    let screening = KEEP_PCTS
71        .iter()
72        .map(|&keep_pct| screening_row(space.total(), factorial_total, brute_force, keep_pct))
73        .collect::<Result<Vec<_>, _>>()?;
74
75    Ok(CostAnalysis {
76        main_effect_iters,
77        pair_count,
78        pair_iters,
79        factorial_total,
80        brute_force,
81        screening,
82    })
83}
84
85fn compute_pair_count(
86    contested: &[&super::space::SlotCandidates],
87) -> Result<u64, PermutationError> {
88    let mut pair_count = 0_u64;
89
90    for (index, slot) in contested.iter().enumerate() {
91        let left_count = slot.count().min(TOP_K) as u64;
92
93        for other in contested.iter().skip(index + 1) {
94            let right_count = other.count().min(TOP_K) as u64;
95            let product = checked_mul(left_count, right_count, "pair count")?;
96
97            pair_count = checked_add(pair_count, product, "pair count")?;
98        }
99    }
100
101    Ok(pair_count)
102}
103
104fn screening_row(
105    permutation_total: u64,
106    factorial_total: u64,
107    brute_force: u64,
108    keep_pct: f64,
109) -> Result<ScreeningRow, PermutationError> {
110    let survivors = MIN_SURVIVORS.max(f64_to_u64_saturating_ceil(
111        (u64_to_f64(permutation_total) * keep_pct) / HUNDRED,
112    ));
113    let tournament_cost = tournament_cost(survivors)?;
114    let total_cost = checked_add(factorial_total, tournament_cost, "screening total cost")?;
115    let savings_pct = if brute_force > 0 {
116        (1.0 - u64_to_f64(total_cost) / u64_to_f64(brute_force)) * HUNDRED
117    } else {
118        0.0
119    };
120
121    Ok(ScreeningRow {
122        keep_pct,
123        survivors,
124        tournament_cost,
125        total_cost,
126        savings_pct,
127    })
128}
129
130fn tournament_cost(survivors: u64) -> Result<u64, PermutationError> {
131    let mut cost = 0_u64;
132    let mut remaining = survivors;
133
134    while remaining > FINAL_STAGE_THRESHOLD {
135        let round_cost = checked_mul(
136            remaining,
137            TOURNAMENT_ITERS_PER_ROUND,
138            "screening round cost",
139        )?;
140
141        cost = checked_add(cost, round_cost, "screening tournament cost")?;
142        remaining = remaining.div_ceil(TOURNAMENT_PAIR_SIZE);
143    }
144
145    let final_stage_cost = checked_mul(remaining, FINAL_STAGE_ITERS, "screening final-stage cost")?;
146
147    checked_add(cost, final_stage_cost, "screening tournament cost")
148}
149
150fn checked_add(left: u64, right: u64, operation: &'static str) -> Result<u64, PermutationError> {
151    left.checked_add(right)
152        .ok_or_else(|| PermutationError::cost_overflow(operation))
153}
154
155fn checked_mul(left: u64, right: u64, operation: &'static str) -> Result<u64, PermutationError> {
156    left.checked_mul(right)
157        .ok_or_else(|| PermutationError::cost_overflow(operation))
158}
wowlab_common/sim/permutations/cost.rs

wowlab_common/sim/permutations/
cost.rs
