rill_ml/sparse/
mod.rs

1//! Sparse feature representation for high-dimensional data.
2//!
3//! RillML uses a sorted `(FeatureId, value)` vector instead of
4//! `HashMap<String, f64>` as the core sparse representation. This keeps
5//! serialization deterministic and memory predictable.
6
7use crate::error::{RillError, checked_finite_add};
8
9/// Feature identifier type. Use integers, not strings.
10pub type FeatureId = u64;
11
12/// Sparse feature vector: sorted `(FeatureId, value)` pairs.
13///
14/// # Requirements
15///
16/// - Sorted by `FeatureId` in ascending order.
17/// - No duplicate `FeatureId`s.
18/// - Zero values may be omitted.
19/// - Not a `HashMap<String, f64>`.
20///
21/// # Examples
22///
23/// ```
24/// use rill_ml::sparse::SparseFeatures;
25///
26/// let features = SparseFeatures::from_sorted(vec![
27///     (1, 0.5),
28///     (3, 2.0),
29///     (7, -1.0),
30/// ]).unwrap();
31/// assert_eq!(features.len(), 3);
32/// assert_eq!(features.get(3), Some(2.0));
33/// ```
34#[derive(Debug, Clone, Default)]
35#[cfg_attr(feature = "serde", derive(serde::Serialize))]
36pub struct SparseFeatures {
37    values: Vec<(FeatureId, f64)>,
38}
39
40impl SparseFeatures {
41    /// Create an empty sparse feature vector.
42    pub fn new() -> Self {
43        Self { values: Vec::new() }
44    }
45
46    /// Build from a `Vec` that is already sorted by `FeatureId` and contains
47    /// no duplicates.
48    ///
49    /// Returns an error if the input is unsorted, has duplicates, or contains
50    /// non-finite values.
51    pub fn from_sorted(values: Vec<(FeatureId, f64)>) -> Result<Self, RillError> {
52        let result = Self { values };
53        result.validate()?;
54        Ok(result)
55    }
56
57    /// Build from an unsorted `Vec`, sorting and merging duplicates by
58    /// summing their values.
59    ///
60    /// Non-finite values are rejected after merging.
61    pub fn from_unsorted(mut values: Vec<(FeatureId, f64)>) -> Result<Self, RillError> {
62        if values.is_empty() {
63            return Ok(Self::new());
64        }
65        values.sort_by_key(|(id, _)| *id);
66
67        let mut merged: Vec<(FeatureId, f64)> = Vec::with_capacity(values.len());
68        for (id, val) in values {
69            if let Some(last) = merged.last_mut()
70                && last.0 == id
71            {
72                last.1 = checked_finite_add(last.1, val, "sparse value")?;
73                continue;
74            }
75            merged.push((id, val));
76        }
77        let result = Self { values: merged };
78        result.validate_finite()?;
79        Ok(result)
80    }
81
82    /// Append a single feature. The `id` must be strictly greater than the
83    /// last inserted id.
84    pub fn push(&mut self, id: FeatureId, value: f64) -> Result<(), RillError> {
85        if let Some(&(last_id, _)) = self.values.last()
86            && id <= last_id
87        {
88            return Err(RillError::UnsortedFeatureIds);
89        }
90        if !value.is_finite() {
91            return Err(RillError::NonFiniteValue {
92                field: "sparse_value",
93                value,
94            });
95        }
96        self.values.push((id, value));
97        Ok(())
98    }
99
100    /// Access the internal `(FeatureId, value)` slice.
101    pub fn values(&self) -> &[(FeatureId, f64)] {
102        &self.values
103    }
104
105    /// Number of non-zero (explicitly stored) features.
106    pub fn len(&self) -> usize {
107        self.values.len()
108    }
109
110    /// Whether no features are stored.
111    pub fn is_empty(&self) -> bool {
112        self.values.is_empty()
113    }
114
115    /// Look up the value for a given `FeatureId` via binary search.
116    pub fn get(&self, id: FeatureId) -> Option<f64> {
117        self.values
118            .binary_search_by_key(&id, |(fid, _)| *fid)
119            .ok()
120            .map(|idx| self.values[idx].1)
121    }
122
123    /// Iterate over `(FeatureId, &value)` pairs.
124    pub fn iter(&self) -> impl Iterator<Item = (FeatureId, f64)> + '_ {
125        self.values.iter().map(|&(id, val)| (id, val))
126    }
127
128    /// Validate sorting, uniqueness, and finiteness.
129    pub fn validate(&self) -> Result<(), RillError> {
130        for window in self.values.windows(2) {
131            if window[0].0 >= window[1].0 {
132                if window[0].0 == window[1].0 {
133                    return Err(RillError::DuplicateFeatureId(window[0].0));
134                }
135                return Err(RillError::UnsortedFeatureIds);
136            }
137        }
138        self.validate_finite()
139    }
140
141    fn validate_finite(&self) -> Result<(), RillError> {
142        for &(_, val) in &self.values {
143            if !val.is_finite() {
144                return Err(RillError::NonFiniteValue {
145                    field: "sparse_value",
146                    value: val,
147                });
148            }
149        }
150        Ok(())
151    }
152}
153
154#[cfg(feature = "serde")]
155impl<'de> serde::Deserialize<'de> for SparseFeatures {
156    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
157    where
158        D: serde::Deserializer<'de>,
159    {
160        #[derive(serde::Deserialize)]
161        struct SparseFeaturesState {
162            values: Vec<(FeatureId, f64)>,
163        }
164
165        let state = SparseFeaturesState::deserialize(deserializer)?;
166        Self::from_sorted(state.values).map_err(serde::de::Error::custom)
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173
174    #[test]
175    fn empty_construction() {
176        let sf = SparseFeatures::new();
177        assert!(sf.is_empty());
178        assert_eq!(sf.len(), 0);
179    }
180
181    #[test]
182    fn from_sorted_success() {
183        let sf = SparseFeatures::from_sorted(vec![(1, 0.5), (3, 2.0), (7, -1.0)]).unwrap();
184        assert_eq!(sf.len(), 3);
185    }
186
187    #[test]
188    fn from_sorted_unsorted_rejected() {
189        let result = SparseFeatures::from_sorted(vec![(3, 1.0), (1, 2.0)]);
190        assert!(matches!(result, Err(RillError::UnsortedFeatureIds)));
191    }
192
193    #[test]
194    fn from_sorted_duplicate_rejected() {
195        let result = SparseFeatures::from_sorted(vec![(1, 0.5), (1, 2.0)]);
196        assert!(matches!(result, Err(RillError::DuplicateFeatureId(1))));
197    }
198
199    #[test]
200    fn duplicate_merge_rejects_overflow() {
201        let result = SparseFeatures::from_unsorted(vec![(1, f64::MAX), (1, f64::MAX)]);
202        assert!(result.is_err());
203    }
204
205    #[cfg(feature = "serde")]
206    #[test]
207    fn serde_rejects_invalid_state() {
208        let unsorted = r#"{"values":[[2,1.0],[1,1.0]]}"#;
209        assert!(serde_json::from_str::<SparseFeatures>(unsorted).is_err());
210    }
211
212    #[test]
213    fn from_unsorted_sorts_and_merges() {
214        let sf = SparseFeatures::from_unsorted(vec![(3, 1.0), (1, 2.0), (3, 0.5)]).unwrap();
215        assert_eq!(sf.len(), 2);
216        assert_eq!(sf.get(1), Some(2.0));
217        assert_eq!(sf.get(3), Some(1.5));
218    }
219
220    #[test]
221    fn push_success() {
222        let mut sf = SparseFeatures::new();
223        sf.push(1, 0.5).unwrap();
224        sf.push(5, 2.0).unwrap();
225        assert_eq!(sf.len(), 2);
226    }
227
228    #[test]
229    fn push_unsorted_rejected() {
230        let mut sf = SparseFeatures::new();
231        sf.push(5, 1.0).unwrap();
232        assert!(sf.push(3, 2.0).is_err());
233    }
234
235    #[test]
236    fn push_duplicate_rejected() {
237        let mut sf = SparseFeatures::new();
238        sf.push(5, 1.0).unwrap();
239        assert!(sf.push(5, 2.0).is_err());
240    }
241
242    #[test]
243    fn get_binary_search() {
244        let sf = SparseFeatures::from_sorted(vec![(1, 10.0), (5, 50.0), (10, 100.0)]).unwrap();
245        assert_eq!(sf.get(1), Some(10.0));
246        assert_eq!(sf.get(5), Some(50.0));
247        assert_eq!(sf.get(10), Some(100.0));
248        assert_eq!(sf.get(3), None);
249        assert_eq!(sf.get(100), None);
250    }
251
252    #[test]
253    fn non_finite_rejected() {
254        let result = SparseFeatures::from_sorted(vec![(1, f64::NAN)]);
255        assert!(result.is_err());
256        let result = SparseFeatures::from_sorted(vec![(1, f64::INFINITY)]);
257        assert!(result.is_err());
258    }
259
260    #[test]
261    fn iter_works() {
262        let sf = SparseFeatures::from_sorted(vec![(1, 0.5), (3, 2.0)]).unwrap();
263        let collected: Vec<(FeatureId, f64)> = sf.iter().collect();
264        assert_eq!(collected, vec![(1, 0.5), (3, 2.0)]);
265    }
266
267    #[test]
268    #[cfg(feature = "serde")]
269    fn serde_roundtrip() {
270        let sf = SparseFeatures::from_sorted(vec![(1, 0.5), (3, 2.0), (7, -1.0)]).unwrap();
271        let json = serde_json::to_string(&sf).unwrap();
272        let restored: SparseFeatures = serde_json::from_str(&json).unwrap();
273        assert_eq!(restored.len(), 3);
274        assert_eq!(restored.get(3), Some(2.0));
275    }
276}
rill_ml/sparse/mod.rs

rill_ml/sparse/
mod.rs
