Ordinamento e ricerca in Rust

Ordinare e cercare sono due lavori che farai in quasi tutti i programmi: fare la classifica dei giocatori per punteggio, elencare i file per nome, trovare il prodotto più economico. Rust dà a vettori e slice una serie di metodi già pronti per entrambe le cose, quindi raramente dovrai scrivere un algoritmo tuo.

Quasi tutti questi metodi ricevono una closure che dice come confrontare due elementi. Una volta che ti sei abituato a questa idea, il resto della pagina è solo una serie di variazioni.

sort e sort_unstable

.sort() mette gli elementi in ordine crescente (prima il più piccolo). Modifica il vettore sul posto, quindi il vettore deve essere mut. I numeri si ordinano per valore; le stringhe in ordine alfabetico.

fn main() {
    let mut scores = vec![42, 7, 99, 7, 15];
    scores.sort();
    println!("{:?}", scores);

    let mut names = vec!["Zoe", "adam", "Bob", "Ana"];
    names.sort_unstable();
    println!("{:?}", names);
}

Output:

[7, 7, 15, 42, 99]
["Ana", "Bob", "Zoe", "adam"]

▶ Provalo tu

Due cose da notare:

• "adam" finisce in fondo. Le stringhe si confrontano per codice del carattere, e tutte le lettere maiuscole vengono prima di tutte le minuscole. Ordina per name.to_lowercase() (lo vedi più sotto) se vuoi l’ordine «da dizionario». Per lo stesso motivo, le lettere accentate come «è» finiscono dopo tutte le lettere senza accento.
• sort_unstable di solito è un po’ più veloce e non usa memoria in più. «Instabile» non vuol dire che ha dei bug. Vuol dire che gli elementi considerati uguali potrebbero scambiarsi di posto. Con semplici numeri o stringhe non puoi accorgertene, quindi è una buona scelta di default.

Ordine inverso

Ci sono tre modi comuni per ordinare dal più grande al più piccolo. Qui danno tutti lo stesso risultato.

use std::cmp::Reverse;

fn main() {
    let mut a = vec![3, 8, 1, 5];
    a.sort();
    a.reverse();
    println!("{:?}", a);

    let mut b = vec![3, 8, 1, 5];
    b.sort_by(|x, y| y.cmp(x)); // y prima di x = decrescente
    println!("{:?}", b);

    let mut c = vec![3, 8, 1, 5];
    c.sort_by_key(|&n| Reverse(n));
    println!("{:?}", c);
}

Output:

[8, 5, 3, 1]
[8, 5, 3, 1]
[8, 5, 3, 1]

▶ Provalo tu

x.cmp(y) restituisce un Ordering: Less, Equal o Greater (minore, uguale, maggiore). sort_by lo usa per decidere quale elemento va prima. Scrivere y.cmp(x) rovescia ogni decisione, e quindi rovescia tutto l’ordine. Reverse è un piccolo involucro di std::cmp che fa lo stesso rovesciamento per una chiave.

Ordinare i float

Prova .sort() su un vettore di f64 e Rust si rifiuta:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0];
    prices.sort();
}

error[E0277]: the trait bound `{float}: Ord` is not satisfied
 --> src/main.rs:3:12
  |
3 |     prices.sort();
  |            ^^^^ the trait `Ord` is not implemented for `{float}`

Il compilatore dice che i numeri decimali ({float}) non implementano il trait Ord. Perché? .sort() ha bisogno di un ordine totale (il trait Ord): per due valori qualsiasi, uno deve essere minore, uguale o maggiore dell’altro. I float hanno un valore speciale, NaN («not a number», non è un numero), che non è minore, uguale o maggiore di niente, nemmeno di sé stesso. Quindi i float hanno solo PartialOrd, e .partial_cmp() restituisce un Option<Ordering> che vale None per NaN.

Hai due buone soluzioni:

fn main() {
    let mut prices = vec![2.5, 0.99, 10.0, 4.75];

    // Se sei sicuro che non ci sia nessun NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Funziona anche con NaN (NaN va in fondo):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Output:

[0.99, 2.5, 4.75, 10.0]
[-1.0, 0.5, 3.2, NaN]

▶ Provalo tu

partial_cmp(...).unwrap() va in panic se incontra un NaN. total_cmp non va mai in panic, perché stabilisce un posto fisso per ogni float, compreso NaN. Preferisci total_cmp, a meno che tu non abbia un motivo per non farlo.

sort_by_key e ordinare struct

sort_by_key riceve una closure che sceglie in base a cosa ordinare. È perfetto per le struct, dove scegli un campo.

#[derive(Debug)]
struct Product {
    name: String,
    price_cents: u32,
}

fn main() {
    let mut items = vec![
        Product { name: String::from("penna"), price_cents: 150 },
        Product { name: String::from("Quaderno"), price_cents: 499 },
        Product { name: String::from("gomma"), price_cents: 75 },
    ];

    items.sort_by_key(|p| p.price_cents);
    for p in &items {
        println!("{} - {}", p.price_cents, p.name);
    }

    items.sort_by_key(|p| p.name.to_lowercase());
    let names: Vec<&str> = items.iter().map(|p| p.name.as_str()).collect();
    println!("{:?}", names);
}

Output:

75 - gomma
150 - penna
499 - Quaderno
["gomma", "penna", "Quaderno"]

▶ Provalo tu

La closure della chiave deve restituire un valore posseduto. p.price_cents è un u32, che viene copiato, quindi va bene. Per un campo String ti serve una nuova String: ecco perché il secondo ordinamento usa to_lowercase(), che ne crea una. Senza to_lowercase(), «Quaderno» finirebbe per primo, perché le maiuscole vengono prima delle minuscole. (Vedi la sezione sugli errori più sotto.)

Ordinare per più campi

Un compito classico: ordinare gli studenti per voto, dal più alto, e quando due studenti hanno lo stesso voto, ordinarli per nome dalla A alla Z. Usa sort_by con .then_with(). Guarda il secondo confronto solo quando il primo è in parità.

struct Student {
    name: String,
    grade: u32,
}

fn main() {
    let mut class = vec![
        Student { name: String::from("Liam"), grade: 88 },
        Student { name: String::from("Ava"), grade: 95 },
        Student { name: String::from("Noah"), grade: 88 },
        Student { name: String::from("Emma"), grade: 88 },
        Student { name: String::from("Mia"), grade: 72 },
    ];

    class.sort_by(|a, b| {
        b.grade.cmp(&a.grade)               // voto: dal più alto al più basso
            .then_with(|| a.name.cmp(&b.name)) // poi nome: dalla A alla Z
    });

    for s in &class {
        println!("{:>3}  {}", s.grade, s.name);
    }
}

Output:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Provalo tu

Un’alternativa più breve è restituire una tupla come chiave. Le tuple confrontano il primo elemento, poi il secondo e così via:

class.sort_by_key(|s| (Reverse(s.grade), s.name.clone()));

Questo dà esattamente lo stesso ordine. È ordinato, ma clona ogni nome, quindi per liste grandi sort_by con then_with è un’abitudine migliore.

Togliere i duplicati con dedup

.dedup() toglie gli elementi uguali a quello subito prima. Quindi toglie tutti i duplicati solo se la lista è stata ordinata prima.

fn main() {
    let mut tags = vec!["rust", "web", "rust", "cli", "web", "web"];

    let mut not_sorted = tags.clone();
    not_sorted.dedup();
    println!("solo dedup:   {:?}", not_sorted);

    tags.sort();
    tags.dedup();
    println!("sort + dedup: {:?}", tags);
}

Output:

solo dedup:   ["rust", "web", "rust", "cli", "web"]
sort + dedup: ["cli", "rust", "web"]

▶ Provalo tu

Al primo tentativo sono stati uniti solo i due "web" che stavano uno accanto all’altro. Prima ordina, poi dedup. Se devi mantenere l’ordine originale, usa il trucco con HashSet della pagina su HashSet.

Cercare: contains, position, max, min, binary_search

Ecco gli strumenti di ricerca che userai di più:

• contains(&x): c’è? Restituisce un bool.
• iter().position(...): dov’è la prima corrispondenza? Restituisce Option<usize>.
• iter().max() / iter().min(): il più grande e il più piccolo, come Option (è None per una lista vuota).
• iter().max_by_key(...) / min_by_key(...): il più grande o il più piccolo in base a un campo.
• binary_search(&x): una ricerca velocissima, ma solo su una lista ordinata. Restituisce Ok(indice) se lo trova, oppure Err(indice) che dice dove andrebbe messo.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("c'è il 31? {}", temps.contains(&31));
    println!("il primo sopra 20 è a: {:?}", temps.iter().position(|&t| t > 20));
    println!("max: {:?}, min: {:?}", temps.iter().max(), temps.iter().min());

    let players = vec![("ana", 340), ("ben", 515), ("chen", 220)];
    let best = players.iter().max_by_key(|(_, score)| *score).unwrap();
    println!("miglior giocatore: {}", best.0);

    let mut sorted = vec![10, 20, 30, 40];
    println!("{:?}", sorted.binary_search(&30));
    let missing = sorted.binary_search(&25);
    println!("{:?}", missing);
    if let Err(pos) = missing {
        sorted.insert(pos, 25); // mantiene la lista ordinata
    }
    println!("{:?}", sorted);
}

Output:

c'è il 31? true
il primo sopra 20 è a: Some(1)
max: Some(31), min: Some(12)
miglior giocatore: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Provalo tu

binary_search (ricerca binaria) controlla l’elemento in mezzo, butta via la metà che non può contenere il valore e ripete. Su una lista di un milione di elementi sono circa 20 controlli invece di un milione. Anche la risposta Err(pos) è comoda: inserire in pos mantiene la lista ordinata.

Attenzione

Anche max() e min() hanno bisogno di Ord, quindi non funzionano neanche loro con i float. Usa invece max_by(|a, b| a.total_cmp(b)): è la stessa soluzione vista per l’ordinamento.

Errori comuni

Restituire da sort_by_key un campo String preso in prestito. Sembra naturale, ma non compila:

students.sort_by_key(|s| s.name);

error[E0507]: cannot move out of `s.name` which is behind a shared reference
  --> src/main.rs:12:30
   |
12 |     students.sort_by_key(|s| s.name);
   |                              ^^^^^^ move occurs because `s.name` has type `String`, which does not implement the `Copy` trait

Il compilatore dice che non può spostare s.name fuori da un riferimento condiviso, perché String non implementa Copy. La closure prende solo in prestito ogni studente, quindi non può cedere la String. Puoi clonarla (|s| s.name.clone()) oppure evitare del tutto la copia con sort_by(|a, b| a.name.cmp(&b.name)).

Usare binary_search su una lista non ordinata. Non va in crash, ma la risposta non ha senso: può dirti che un valore manca quando invece è proprio lì. Ordina sempre prima, oppure usa contains / position.

Pratica

1. Classifica

Hai dei giocatori come tuple (nome, punteggio): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Ordinali per punteggio, dal più alto, e a parità per nome dalla A alla Z. Stampa solo i primi tre. Suggerimento: usa sort_by con .then_with(), e una slice &players[..3] per i primi tre.

Mostra la soluzione

fn main() {
    let mut players = vec![("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60)];

    players.sort_by(|a, b| b.1.cmp(&a.1).then_with(|| a.0.cmp(&b.0)));

    for (name, score) in &players[..3] {
        println!("{score} {name}");
    }
}

Output:

95 ana
88 dev
70 ben

▶ Provalo tu

In una tupla, .0 è il nome e .1 è il punteggio. ben e chen hanno entrambi 70, quindi decide il nome, e ben entra nei primi tre.

2. Il prezzo mediano

Trova la mediana (il valore di mezzo) dei prezzi 3.5, 1.25, 9.0, 4.75, 2.0. Stampa la lista ordinata e la mediana. Suggerimento: ordina con total_cmp; poi l’elemento di mezzo di una lista di lunghezza dispari è all’indice len() / 2.

Mostra la soluzione

fn main() {
    let mut prices: Vec<f64> = vec![3.5, 1.25, 9.0, 4.75, 2.0];

    prices.sort_by(|a, b| a.total_cmp(b));
    let median = prices[prices.len() / 2];

    println!("ordinati: {:?}", prices);
    println!("mediana: {median}");
}

Output:

ordinati: [1.25, 2.0, 3.5, 4.75, 9.0]
mediana: 3.5

▶ Provalo tu

L’annotazione di tipo Vec<f64> è importante. Senza, quando arriva a total_cmp Rust non sa ancora di quale tipo float siano i numeri, e si rifiuta di compilare con «no method named total_cmp» (nessun metodo chiamato total_cmp).

Riepilogo

• sort() e sort_unstable() ordinano sul posto, dal più piccolo. Usa reverse(), y.cmp(x) o Reverse per partire dal più grande.
• I float non possono usare sort() a causa di NaN. Usa sort_by(|a, b| a.total_cmp(b)).
• sort_by_key ordina in base a un campo scelto; sort_by con .then_with() ordina per più campi.
• dedup() toglie solo i vicini uguali, quindi prima ordina.
• contains, position, max/min e max_by_key cercano in qualsiasi lista; binary_search è molto più veloce ma ha bisogno di una lista ordinata.

Verifica veloce

Verifica veloce

1. Perché vec![1.5, 0.5].sort() non compila?

I float non si possono mettere in un Vec sort funziona solo con le stringhe I float non implementano Ord, perché NaN non si può confrontare Il vettore non è mut

2. Che cosa resta nel vettore dopo vec![1, 1, 2, 1].dedup()?

[1, 2] [1, 2, 1] [2] [1, 1, 2, 1]

3. Che cosa restituisce vec![10, 20, 30].binary_search(&25)?

Err(2) Ok(2) None -1

4. In a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), quando viene confrontato il nome?

Sempre, prima del voto Mai Solo quando i nomi sono diversi Solo quando i due voti sono uguali

Punteggio: 0 / 4

Per approfondire

• Metodi delle slice: sort, sort_by, binary_search e altri — documentazione della libreria standard (in inglese): tutti i metodi per ordinare e cercare, con note su velocità e stabilità.
• std::cmp::Ordering — documentazione della libreria standard (in inglese): Less, Equal, Greater, più then, then_with e reverse.
• std::cmp::Reverse — documentazione della libreria standard (in inglese): l’involucro per ordinare una chiave dal più grande al più piccolo.
• f64::total_cmp — documentazione della libreria standard (in inglese): dove finiscono esattamente NaN, lo zero negativo e l’infinito quando ordini i float.
• Sort a Vector — Rust Cookbook (in inglese): brevi ricette per ordinare interi, float e struct.