ArtNotes

9-String et Collections

7 min de lecture

9. String, Vecteurs et Collections

Les collections en Rust sont puissantes et sûres. Comprendre String vs &str, les Vec avancés, HashMap, et le borrowing avec les collections est essentiel pour écrire du code efficace.

9.1 String vs &str

&str — Slice de chaîne (référence)

&str est une référence vers une séquence d’UTF-8. Elle est le plus souvent &'static str (codée dans le binaire) ou empruntée depuis une String.

let s: &str = "hello";          // &'static str, toujours valide
let s2: &str = &s[0..2];        // "he" — slice d'un &str
 
fn longueur(s: &str) -> usize {
    s.len()     // nombre d'octets, pas de caractères !
}
 
fn nb_characters(s: &str) -> usize {
    s.chars().count()  // nombre de characters Unicode
}

String — Chaîne propriétaire (heap)

String est une chaîne allouée sur le heap, modifiable, propriétaire de ses données.

OpérationExempleCoût
CréerString::from("hello")Allocation
Concaténers.push_str(" world")Réallocation possible
Ajouter un chars.push('!')Réallocation possible
Insérers.insert(0, 'H')Décalage mémoire
Remplacers.replace("ll", "LL")Nouvelle allocation
Couper&s[0..5]Gratuit (slice)
let mut s = String::with_capacity(100);  // pré-allouer
s.push_str("hello");
s.push(' ');
s.push_str("world");
println!("{s}");  // "hello world"
 
// Conversions
let s = String::from("hello");
let slice: &str = &s;        // String → &str (gratuit)
let s2: String = slice.to_string();  // &str → String (allocation)

Comparaison

fn prendre_str(s: &str) { println!("{s}"); }
fn prendre_string(s: String) { println!("{s}"); }
 
let s = String::from("hello");
 
prendre_str(&s);        // ✅ String → &str (emprunt)
prendre_string(s);      // ✅ move de la String
// prendre_str(&s);      // ⛔ s a été moved
 
// Pattern idiomatique : TOUJOURS prendre &str, jamais &String ou String
fn naive(s: &String) {}  // ❌ inutilement restrictif
fn idiomatique(s: &str) {}  // ✅ accepte &String ET &str

9.2 Vec — Vecteurs avancés

Création et allocation

let v = vec![1, 2, 3];                 // macro
let v = Vec::with_capacity(100);        // pré-alloué, pas de réallocation
let v: Vec<i32> = (0..10).collect();    // depuis un itérateur
let v = vec![0.0; 1_000_000];           // 1M zéros (une seule allocation)

Capacité et réallocation

let mut v = Vec::with_capacity(4);
println!("len: {}, cap: {}", v.len(), v.capacity());  // 0, 4
 
v.push(1); v.push(2); v.push(3); v.push(4);
println!("len: {}, cap: {}", v.len(), v.capacity());  // 4, 4
 
v.push(5);  // dépasse la capacité → réallocation (x2 généralement)
println!("len: {}, cap: {}", v.len(), v.capacity());  // 5, 8
 
// Forcer une capacité exacte
v.shrink_to_fit();  // réduit à la taille exacte (peut coûter une réallocation)
v.reserve(100);     // réserve pour 100 éléments supplémentaires

Modifications efficaces

let mut v = vec![1, 2, 3, 4, 5];
 
// Retirer sans décalage (ne préserve pas l'ordre)
v.swap_remove(1); // [1, 5, 3, 4]   (O(1) au lieu de O(n))
 
// Conserver uniquement les éléments selon un prédicat
v.retain(|&x| x > 2);  // [5, 3, 4]
 
// Insérer (coûteux — O(n))
v.insert(0, 10);  // [10, 5, 3, 4]
 
// Sort et dedup
v.sort();
v.dedup();  // supprime les doublons consécutifs

Vues : split, chunks, windows

let v = vec![1, 2, 3, 4, 5, 6];
 
// Chunks (groupes contigus sans recouvrement)
for chunk in v.chunks(2) {
    println!("{:?}", chunk);  // [1,2], [3,4], [5,6]
}
 
// Windows (groupes contigus avec recouvrement)
for window in v.windows(3) {
    println!("{:?}", window);  // [1,2,3], [2,3,4], [3,4,5], [4,5,6]
}
 
// Split selon prédicat
let parts: Vec<&[i32]> = v.split(|x| x % 3 == 0).collect();
// [1,2], [4,5], []  (le 3 et 6 sont les séparateurs)

Matrices 2D

// Matrice stockée en Row-Major (contiguë en mémoire)
struct Matrix {
    data: Vec<f64>,           // [row0_col0, row0_col1, ..., rowN_colM]
    n_rows: usize,
    n_cols: usize,
}
 
impl Matrix {
    fn new(n_rows: usize, n_cols: usize) -> Self {
        Self {
            data: vec![0.0; n_rows * n_cols],
            n_rows,
            n_cols,
        }
    }
 
    fn get(&self, i: usize, j: usize) -> f64 {
        self.data[i * self.n_cols + j]
    }
 
    fn get_mut(&mut self, i: usize, j: usize) -> &mut f64 {
        &mut self.data[i * self.n_cols + j]
    }
 
    // Vue d'une ligne (gratuit, pas de copie)
    fn row(&self, i: usize) -> &[f64] {
        let start = i * self.n_cols;
        &self.data[start..start + self.n_cols]
    }
 
    fn transpose(&self) -> Self {
        let mut result = Self::new(self.n_cols, self.n_rows);
        for i in 0..self.n_rows {
            for j in 0..self.n_cols {
                result.data[j * self.n_rows + i] = self.data[i * self.n_cols + j];
            }
        }
        result
    }
}
 
// Utilisation
let mut m = Matrix::new(3, 1000);  // 3 gradients de dimension 1000
for i in 0..3 {
    for j in 0..1000 {
        *m.get_mut(i, j) = rand::random();
    }
}

9.3 HashMap et HashSet

HashMap

use std::collections::HashMap;
 
let mut worker_grads: HashMap<usize, Vec<f64>> = HashMap::new();
 
// Insertion
worker_grads.insert(0, vec![1.0, 2.0, 3.0]);
worker_grads.insert(1, vec![4.0, 5.0, 6.0]);
 
// Accès
if let Some(grad) = worker_grads.get(&0) {
    println!("gradient worker 0: {:?}", grad);
}
 
// Entrée (entry API) — la façon idiomatique
for worker_id in 0..10 {
    worker_grads.entry(worker_id).or_insert_with(|| vec![0.0; 3]);
}
 
// Itération
for (id, grad) in &worker_grads {
    println!("worker {id}: {} dim", grad.len());
}
 
// Avec des types personnalisés comme clé
#[derive(Hash, Eq, PartialEq)]
struct WorkerKey {
    id: usize,
    round: usize,
}
 
let mut history: HashMap<WorkerKey, Vec<f64>> = HashMap::new();

HashSet

use std::collections::HashSet;
 
let mut byzantine_workers: HashSet<usize> = HashSet::new();
byzantine_workers.insert(3);
byzantine_workers.insert(7);
 
if byzantine_workers.contains(&3) {
    println!("worker 3 est suspect");
}
 
// Opérations ensemblistes
let honest: HashSet<_> = (0..10).collect();
let suspected: HashSet<_> = [3, 7, 9].iter().copied().collect();
 
let clean = &honest - &suspected;  // différence : {0,1,2,4,5,6,8}
let intersection = &honest & &suspected;  // intersection : {3,7,9}

9.4 Itérateurs et Collections

Collecter dans différentes collections

let data = vec![1, 2, 3, 2, 1];
 
let set: HashSet<i32> = data.iter().copied().collect();     // {1, 2, 3}
let map: HashMap<i32, usize> = data.iter()
    .enumerate()
    .map(|(i, &v)| (v, i))
    .collect();  // {1: 4, 2: 3, 3: 2} (dernier index)
 
let vec: Vec<i32> = (0..5).collect();
let string: String = vec!["a", "b", "c"].join(",");  // "a,b,c"

Group by (avec HashMap)

use std::collections::HashMap;
 
let grads_by_worker: Vec<(usize, f64)> = vec![
    (0, 1.0), (1, 2.0), (0, 3.0), (2, 4.0), (1, 5.0),
];
 
let grouped: HashMap<usize, Vec<f64>> = grads_by_worker
    .iter()
    .fold(HashMap::new(), |mut acc, &(worker, val)| {
        acc.entry(worker).or_insert_with(Vec::new).push(val);
        acc
    });
// {0: [1.0, 3.0], 1: [2.0, 5.0], 2: [4.0]}

9.5 Iterator vs Index

let v = vec![1, 2, 3, 4, 5];
 
// Par index (vérification de bornes à chaque accès)
let mut sum = 0;
for i in 0..v.len() {
    sum += v[i];
}
 
// Par itérateur (pas de vérification de bornes, plus rapide)
let sum: i32 = v.iter().sum();
 
// Par itérateur avec index
for (i, val) in v.iter().enumerate() {
    println!("v[{i}] = {val}");
}

Performance : itérateur vs index

fn sum_index(v: &[f64]) -> f64 {
    let mut sum = 0.0;
    for i in 0..v.len() {
        sum += v[i];  // bounds check à chaque itération
    }
    sum
}
 
fn sum_iter(v: &[f64]) -> f64 {
    v.iter().sum()  // pas de bounds check, vectorization possible
}
 
// L'itérateur est :
// 1. PLUS RAPIDE (le compilateur élide les bounds checks)
// 2. PLUS SÛR (pas de risque d'index out of bounds)
// 3. PLUS LISIBLE

9.6 Résumé

CollectionOrdreDoublonsAccèsUsage
Vec<T>✅ Insertion✅Index O(1)Collection principale
HashMap<K,V>❌Clés uniquesHash O(1)Lookup par clé
HashSet<T>❌NonHash O(1)Ensemble d’unicité
BTreeMap<K,V>✅ TriéClés uniquesO(log n)Range queries
VecDeque<T>✅✅Front/Back O(1)File FIFO
LinkedList<T>✅✅ItérationRarement utile
BinaryHeap<T>Priorité✅Max O(1)File de priorité

Règles pour les collections

// ✅ Prendre &[T] plutôt que &Vec<T>
fn process(grads: &[Vec<f64>]) {}
 
// ✅ Pré-allouer quand la taille est connue
let mut v = Vec::with_capacity(1000);
 
// ✅ swap_remove plutôt que remove si l'ordre n'importe pas
v.swap_remove(i);  // O(1)
 
// ❌ Éviter l'accès index répété dans une boucle
for i in 0..v.len() { process(v[i]); }    // ❌
for item in &v { process(item); }          // ✅
 
// ❌ Éviter les chaînes de String qui fragmentent
let s = a + &b + &c;  // 2 allocations
let s = format!("{a}{b}{c}");  // 1 allocation

9.6 Calcul Matriciel avec ndarray

Pour les gradients (vecteurs, matrices), ndarray est le standard Rust — analogue à NumPy :

[dependencies]
ndarray = "0.16"
use ndarray::{Array2, Array1, Axis, s};
 
// Matrice n_workers × dimension
let grads = Array2::from_shape_vec((3, 4), vec![
    1.0, 2.0, 3.0, 4.0,
    5.0, 6.0, 7.0, 8.0,
    9.0, 10.0, 11.0, 12.0,
]).unwrap();
 
// Accès
println!("grad[1, 2] = {}", grads[[1, 2]]);  // 7.0
 
// Statistiques par colonne (dimension)
let col_means: Array1<f64> = grads.mean_axis(Axis(0)).unwrap();   // [5.0, 6.0, 7.0, 8.0]
let col_sums: Array1<f64> = grads.sum_axis(Axis(0));              // [15, 18, 21, 24]
 
// Normes et distances (combiné avec `itertools`)
use ndarray_stats::QuantileExt;
 
let col = grads.column(0);
let min = col.min().unwrap();     // 1.0
let max = col.max().unwrap();     // 9.0
 
// Slicing
let subset = grads.slice(s![..2, ..]);  // 2 premières lignes
 
// Map sur éléments
let doubled = grads.mapv(|x| x * 2.0);
 
// Conversion depuis/vers Vec
let flat: Vec<f64> = grads.into_raw_vec();
// Row-major : [1,2,3,4,5,6,7,8,9,10,11,12]

ndarray est particulièrement utile pour implémenter les GARs avec des opérations vectorisées (distance L2, médiane par colonne). Voir 14-Projet GAR Rust.

🔗 Voir aussi

Vue Graphique

Liens retour