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::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
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        module_path: module_path!(),
20        description: "Assign records to circular storage sectors to minimize expected retrieval latency",
21        fields: &[
22            FieldInfo { name: "probabilities", type_name: "Vec<f64>", description: "Access probabilities p(r) for each record" },
23            FieldInfo { name: "num_sectors", type_name: "usize", description: "Number of sectors on the drum-like device" },
24        ],
25    }
26}
27
28inventory::submit! {
29    ProblemSizeFieldEntry {
30        name: "ExpectedRetrievalCost",
31        fields: &["num_records", "num_sectors"],
32    }
33}
34
35#[derive(Debug, Clone, Serialize, Deserialize)]
36pub struct ExpectedRetrievalCost {
37    probabilities: Vec<f64>,
38    num_sectors: usize,
39}
40
41impl ExpectedRetrievalCost {
42    pub fn new(probabilities: Vec<f64>, num_sectors: usize) -> Self {
43        assert!(
44            !probabilities.is_empty(),
45            "ExpectedRetrievalCost requires at least one record"
46        );
47        assert!(
48            num_sectors >= 2,
49            "ExpectedRetrievalCost requires at least two sectors"
50        );
51        for &probability in &probabilities {
52            assert!(
53                probability.is_finite(),
54                "probabilities must be finite real numbers"
55            );
56            assert!(
57                (0.0..=1.0).contains(&probability),
58                "probabilities must lie in [0, 1]"
59            );
60        }
61        let total_probability: f64 = probabilities.iter().sum();
62        assert!(
63            (total_probability - 1.0).abs() <= FLOAT_TOLERANCE,
64            "probabilities must sum to 1.0"
65        );
66        Self {
67            probabilities,
68            num_sectors,
69        }
70    }
71
72    pub fn probabilities(&self) -> &[f64] {
73        &self.probabilities
74    }
75
76    pub fn num_records(&self) -> usize {
77        self.probabilities.len()
78    }
79
80    pub fn num_sectors(&self) -> usize {
81        self.num_sectors
82    }
83
84    pub fn sector_masses(&self, config: &[usize]) -> Option<Vec<f64>> {
85        if config.len() != self.num_records() {
86            return None;
87        }
88
89        let mut masses = vec![0.0; self.num_sectors];
90        for (record, &sector) in config.iter().enumerate() {
91            if sector >= self.num_sectors {
92                return None;
93            }
94            masses[sector] += self.probabilities[record];
95        }
96        Some(masses)
97    }
98
99    pub fn expected_cost(&self, config: &[usize]) -> Option<f64> {
100        let masses = self.sector_masses(config)?;
101        let mut total = 0.0;
102        for source in 0..self.num_sectors {
103            for target in 0..self.num_sectors {
104                total += masses[source]
105                    * masses[target]
106                    * latency_distance(self.num_sectors, source, target) as f64;
107            }
108        }
109        Some(total)
110    }
111
112    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
113        self.expected_cost(config).is_some()
114    }
115}
116
117impl Problem for ExpectedRetrievalCost {
118    const NAME: &'static str = "ExpectedRetrievalCost";
119    type Value = Min<f64>;
120
121    fn variant() -> Vec<(&'static str, &'static str)> {
122        crate::variant_params![]
123    }
124
125    fn dims(&self) -> Vec<usize> {
126        vec![self.num_sectors; self.num_records()]
127    }
128
129    fn evaluate(&self, config: &[usize]) -> Min<f64> {
130        match self.expected_cost(config) {
131            Some(cost) => Min(Some(cost)),
132            None => Min(None),
133        }
134    }
135}
136
137fn latency_distance(num_sectors: usize, source: usize, target: usize) -> usize {
138    if source < target {
139        target - source - 1
140    } else {
141        num_sectors - source + target - 1
142    }
143}
144
145crate::declare_variants! {
146    default ExpectedRetrievalCost => "num_sectors ^ num_records",
147}
148
149#[cfg(feature = "example-db")]
150pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
151    vec![crate::example_db::specs::ModelExampleSpec {
152        id: "expected_retrieval_cost",
153        instance: Box::new(ExpectedRetrievalCost::new(
154            vec![0.2, 0.15, 0.15, 0.2, 0.1, 0.2],
155            3,
156        )),
157        optimal_config: vec![0, 1, 2, 1, 0, 2],
158        optimal_value: serde_json::json!(1.0025),
159    }]
160}
161
162#[cfg(test)]
163#[path = "../../unit_tests/models/misc/expected_retrieval_cost.rs"]
164mod tests;
problemreductions/models/misc/expected_retrieval_cost.rs

problemreductions/models/misc/
expected_retrieval_cost.rs
