problemreductions/models/misc/
expected_retrieval_cost.rs

1//! Expected Retrieval Cost problem implementation.
2//!
3//! Given record access probabilities, find an assignment of records to circular
4//! storage sectors that minimizes the expected rotational latency.
5
6use crate::registry::{ConstructionError, FieldInfo, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11const FLOAT_TOLERANCE: f64 = 1e-9;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "ExpectedRetrievalCost",
16        display_name: "Expected Retrieval Cost",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Assign records to circular storage sectors to minimize expected retrieval latency",
22        fields: &[
23            FieldInfo { name: "probabilities", type_name: "Vec<f64>", description: "Access probabilities p(r) for each record" },
24            FieldInfo { name: "num_sectors", type_name: "usize", description: "Number of sectors on the drum-like device" },
25        ],
26    }
27}
28
29#[derive(Debug, Clone, Serialize)]
30pub struct ExpectedRetrievalCost {
31    probabilities: Vec<f64>,
32    num_sectors: usize,
33}
34
35impl ExpectedRetrievalCost {
36    pub fn new(probabilities: Vec<f64>, num_sectors: usize) -> Result<Self, ConstructionError> {
37        if probabilities.is_empty() {
38            return Err(ConstructionError::Conversion(
39                "ExpectedRetrievalCost requires at least one record".into(),
40            ));
41        }
42        if num_sectors < 2 {
43            return Err(ConstructionError::Conversion(
44                "ExpectedRetrievalCost requires at least two sectors".into(),
45            ));
46        }
47        for (index, &probability) in probabilities.iter().enumerate() {
48            if !probability.is_finite() {
49                return Err(ConstructionError::NonFiniteFloat(format!(
50                    "probability at index {index} must be finite"
51                )));
52            }
53            if !(0.0..=1.0).contains(&probability) {
54                return Err(ConstructionError::Conversion(format!(
55                    "probability at index {index} must lie in [0, 1]"
56                )));
57            }
58        }
59        let total_probability: f64 = probabilities.iter().sum();
60        if !total_probability.is_finite() || (total_probability - 1.0).abs() > FLOAT_TOLERANCE {
61            if !total_probability.is_finite() {
62                return Err(ConstructionError::NonFiniteFloat(
63                    "summing probabilities produced a non-finite value".into(),
64                ));
65            }
66            return Err(ConstructionError::Conversion(
67                "probabilities must sum to 1.0".into(),
68            ));
69        }
70        Ok(Self {
71            probabilities,
72            num_sectors,
73        })
74    }
75
76    pub fn probabilities(&self) -> &[f64] {
77        &self.probabilities
78    }
79
80    pub fn num_records(&self) -> usize {
81        self.probabilities.len()
82    }
83
84    pub fn num_sectors(&self) -> usize {
85        self.num_sectors
86    }
87
88    pub fn sector_masses(
89        &self,
90        config: &[usize],
91    ) -> Result<Option<Vec<f64>>, crate::traits::EvaluationError> {
92        if config.len() != self.num_records() {
93            return Ok(None);
94        }
95
96        let mut masses = vec![0.0; self.num_sectors];
97        for (record, &sector) in config.iter().enumerate() {
98            if sector >= self.num_sectors {
99                return Ok(None);
100            }
101            let mass = masses[sector] + self.probabilities[record];
102            if !mass.is_finite() {
103                return Err(crate::traits::EvaluationError::NonFiniteResult(
104                    "summing expected-retrieval sector probabilities".to_string(),
105                ));
106            }
107            masses[sector] = mass;
108        }
109        Ok(Some(masses))
110    }
111
112    pub fn expected_cost(
113        &self,
114        config: &[usize],
115    ) -> Result<Option<f64>, crate::traits::EvaluationError> {
116        let Some(masses) = self.sector_masses(config)? else {
117            return Ok(None);
118        };
119        let mut total = 0.0;
120        for source in 0..self.num_sectors {
121            for target in 0..self.num_sectors {
122                let latency = i64::try_from(latency_distance(self.num_sectors, source, target))
123                    .map_err(|_| {
124                        crate::traits::EvaluationError::IntegerOverflow(
125                            "converting expected-retrieval latency to i64".to_string(),
126                        )
127                    })?;
128                let latency = crate::types::i64_to_exact_f64(latency).map_err(|_| {
129                    crate::traits::EvaluationError::InexactFloatConversion(
130                        "converting expected-retrieval latency to f64".to_string(),
131                    )
132                })?;
133                let term = masses[source] * masses[target] * latency;
134                let next = total + term;
135                if !term.is_finite() || !next.is_finite() {
136                    return Err(crate::traits::EvaluationError::NonFiniteResult(
137                        "computing expected retrieval cost".to_string(),
138                    ));
139                }
140                total = next;
141            }
142        }
143        Ok(Some(total))
144    }
145
146    pub fn is_valid_solution(
147        &self,
148        config: &[usize],
149    ) -> Result<bool, crate::traits::EvaluationError> {
150        Ok(self.expected_cost(config)?.is_some())
151    }
152}
153
154#[derive(Deserialize)]
155struct ExpectedRetrievalCostData {
156    probabilities: Vec<f64>,
157    num_sectors: usize,
158}
159
160impl<'de> Deserialize<'de> for ExpectedRetrievalCost {
161    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
162    where
163        D: serde::Deserializer<'de>,
164    {
165        let data = ExpectedRetrievalCostData::deserialize(deserializer)?;
166        Self::new(data.probabilities, data.num_sectors).map_err(serde::de::Error::custom)
167    }
168}
169
170impl Problem for ExpectedRetrievalCost {
171    const NAME: &'static str = "ExpectedRetrievalCost";
172    type Solution = Vec<usize>;
173    type Value = Min<f64>;
174
175    crate::problem_parameters![("num_records", num_records), ("num_sectors", num_sectors),];
176
177    fn variant() -> Vec<(&'static str, &'static str)> {
178        crate::variant_params![]
179    }
180
181    fn evaluate(
182        &self,
183        config: &Self::Solution,
184    ) -> Result<Min<f64>, crate::traits::EvaluationError> {
185        if config.len() != self.num_records() {
186            return Err(crate::traits::EvaluationError::InvalidConfiguration(
187                "sector assignment length does not match the records".into(),
188            ));
189        }
190        if config.iter().any(|&sector| sector >= self.num_sectors) {
191            return Err(crate::traits::EvaluationError::InvalidConfiguration(
192                "sector assignment contains an out-of-range sector".into(),
193            ));
194        }
195        Ok({
196            match self.expected_cost(config)? {
197                Some(cost) => Min(Some(cost)),
198                None => Min(None),
199            }
200        })
201    }
202}
203
204impl crate::solvers::BruteForceProblem for ExpectedRetrievalCost {
205    fn dimensions(&self) -> Vec<usize> {
206        vec![self.num_sectors; self.num_records()]
207    }
208}
209
210fn latency_distance(num_sectors: usize, source: usize, target: usize) -> usize {
211    if source < target {
212        target - source - 1
213    } else {
214        num_sectors - source + target - 1
215    }
216}
217
218crate::declare_variants! {
219    default ExpectedRetrievalCost => "num_sectors ^ num_records",
220}
221
222crate::register_brute_force! {
223    ExpectedRetrievalCost,
224}
225
226#[cfg(feature = "example-db")]
227pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
228    vec![crate::example_db::specs::ModelExampleSpec {
229        id: "expected_retrieval_cost",
230        instance: Box::new(
231            ExpectedRetrievalCost::new(vec![0.2, 0.15, 0.15, 0.2, 0.1, 0.2], 3).unwrap(),
232        ),
233        optimal_config: serde_json::json!(vec![0, 1, 2, 1, 0, 2]),
234        optimal_value: serde_json::json!(1.0025),
235    }]
236}
237
238#[cfg(test)]
239#[path = "../../unit_tests/models/misc/expected_retrieval_cost.rs"]
240mod tests;
problemreductions/models/misc/expected_retrieval_cost.rs

problemreductions/models/misc/
expected_retrieval_cost.rs
