Sắp xếp và tìm kiếm trong Rust

Sắp xếp và tìm kiếm là hai việc bạn sẽ làm trong hầu như mọi chương trình: xếp hạng người chơi theo điểm, liệt kê file theo tên, tìm sản phẩm rẻ nhất. Rust cho vector và slice một bộ phương thức có sẵn cho cả hai việc, nên bạn hiếm khi phải tự viết thuật toán.

Phần lớn các phương thức này nhận một closure nói rõ cách so sánh hai phần tử. Khi đã quen với ý tưởng đó, phần còn lại của bài chỉ là các biến thể của nó.

Trong bài này, các chuỗi được đem đi sắp xếp hay so sánh đều được giữ nguyên tiếng Anh: Rust so sánh chuỗi theo từng byte, nên chữ tiếng Việt có dấu sẽ không ra đúng thứ tự bảng chữ cái tiếng Việt.

sort và sort_unstable

.sort() đặt các phần tử theo thứ tự tăng dần (nhỏ nhất trước). Nó thay đổi vector tại chỗ, nên vector phải là mut. Số được sắp xếp theo giá trị; chuỗi được sắp xếp theo bảng chữ cái.

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);
}

Kết quả:

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

▶ Tự chạy thử

Hai điều cần để ý:

"adam" đứng cuối. Chuỗi được so sánh theo mã ký tự, và mọi chữ hoa đều đứng trước mọi chữ thường. Hãy sắp xếp theo name.to_lowercase() (xem bên dưới) nếu bạn muốn thứ tự “như trong từ điển”.
sort_unstable thường nhanh hơn một chút và không dùng thêm bộ nhớ. “Unstable” (không ổn định) không có nghĩa là có lỗi. Nó nghĩa là các phần tử được so sánh là bằng nhau có thể bị đổi chỗ cho nhau. Với số hay chuỗi bình thường, bạn không thể thấy sự khác biệt, nên đây là lựa chọn mặc định tốt.

Thứ tự ngược

Có ba cách phổ biến để sắp xếp từ lớn nhất đến nhỏ nhất. Ở đây cả ba cho cùng một kết quả.

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 trước x = giảm dần
    println!("{:?}", b);

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

Kết quả:

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

▶ Tự chạy thử

x.cmp(y) trả về một Ordering: Less (nhỏ hơn), Equal (bằng) hoặc Greater (lớn hơn). sort_by dùng nó để quyết định phần tử nào đứng trước. Viết y.cmp(x) đảo ngược mọi quyết định, nên đảo ngược cả thứ tự. Reverse là một lớp bọc nhỏ trong std::cmp làm đúng việc đảo ngược đó cho một khóa.

Sắp xếp số thực

Thử gọi .sort() trên một vector f64 và Rust sẽ từ chối:

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}`

Rustc báo rằng kiểu số thực không triển khai trait Ord. Vì sao? .sort() cần một thứ tự toàn phần (total order, chính là trait Ord): với hai giá trị bất kỳ, một cái phải nhỏ hơn, bằng hoặc lớn hơn cái kia. Số thực có một giá trị đặc biệt, NaN (“not a number”, không phải là số), không nhỏ hơn, không bằng, cũng không lớn hơn bất cứ thứ gì — kể cả chính nó. Vì vậy số thực chỉ có PartialOrd, và .partial_cmp() trả về một Option<Ordering> là None khi gặp NaN.

Bạn có hai cách sửa tốt:

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

    // Nếu bạn chắc chắn không có NaN:
    prices.sort_by(|a, b| a.partial_cmp(b).unwrap());
    println!("{:?}", prices);

    // Chạy được cả khi có NaN (NaN xuống cuối):
    let mut readings = vec![3.2, f64::NAN, -1.0, 0.5];
    readings.sort_by(|a, b| a.total_cmp(b));
    println!("{:?}", readings);
}

Kết quả:

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

▶ Tự chạy thử

partial_cmp(...).unwrap() sẽ panic nếu gặp NaN. total_cmp không bao giờ panic vì nó định sẵn một vị trí cố định cho mọi số thực, kể cả NaN. Hãy ưu tiên total_cmp trừ khi bạn có lý do để không dùng.

sort_by_key và sắp xếp struct

sort_by_key nhận một closure chọn ra thứ để sắp xếp theo. Điều đó rất hợp với struct, nơi bạn chọn một field.

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

fn main() {
    let mut items = vec![
        Product { name: String::from("pen"), price_cents: 150 },
        Product { name: String::from("Notebook"), price_cents: 499 },
        Product { name: String::from("eraser"), 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);
}

Kết quả:

75 - eraser
150 - pen
499 - Notebook
["eraser", "Notebook", "pen"]

▶ Tự chạy thử

Closure tạo khóa phải trả về một giá trị có sở hữu (owned). p.price_cents là một u32, được sao chép, nên không sao. Với field kiểu String, bạn cần một String mới — vì thế lần sắp xếp thứ hai dùng to_lowercase(), hàm này tạo ra một chuỗi mới. (Xem phần lỗi thường gặp bên dưới.)

Sắp xếp theo nhiều field

Một bài toán kinh điển: sắp xếp học sinh theo điểm, cao nhất trước, và khi hai học sinh cùng điểm thì sắp xếp theo tên từ A đến Z. Hãy dùng sort_by với .then_with(). Nó chỉ xét phép so sánh thứ hai khi phép so sánh đầu tiên hòa nhau.

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)               // điểm: cao đến thấp
            .then_with(|| a.name.cmp(&b.name)) // rồi tên: A đến Z
    });

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

Kết quả:

 95  Ava
 88  Emma
 88  Liam
 88  Noah
 72  Mia

▶ Tự chạy thử

Một cách viết ngắn hơn là trả về một tuple làm khóa. Tuple so sánh phần tử đầu tiên, rồi đến phần tử thứ hai, và cứ thế:

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

Cách này cho đúng cùng thứ tự. Nó gọn gàng, nhưng phải clone mọi cái tên, nên sort_by với then_with là thói quen tốt hơn cho danh sách lớn.

Xóa phần tử trùng lặp bằng dedup

.dedup() xóa các phần tử bằng với phần tử ngay trước nó. Vì thế nó chỉ xóa hết mọi phần tử trùng nếu danh sách đã được sắp xếp trước.

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

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

    tags.sort();
    tags.dedup();
    println!("sort rồi dedup: {:?}", tags);
}

Kết quả:

chỉ dedup:      ["rust", "web", "rust", "cli", "web"]
sort rồi dedup: ["cli", "rust", "web"]

▶ Tự chạy thử

Ở lần thử đầu, chỉ hai phần tử "web" nằm cạnh nhau được gộp lại. Hãy sắp xếp trước, rồi mới dedup. Nếu cần giữ thứ tự ban đầu, hãy dùng mẹo HashSet trong bài HashSet.

Tìm kiếm: contains, position, max, min, binary_search

Đây là những công cụ tìm kiếm bạn sẽ dùng nhiều nhất:

contains(&x) — có trong đó không? Trả về bool.
iter().position(...) — phần tử khớp đầu tiên ở đâu? Trả về Option<usize>.
iter().max() / iter().min() — lớn nhất và nhỏ nhất, dưới dạng Option (là None với danh sách rỗng).
iter().max_by_key(...) / min_by_key(...) — lớn nhất hoặc nhỏ nhất theo một field nào đó.
binary_search(&x) — tìm kiếm rất nhanh, nhưng chỉ trên danh sách đã sắp xếp. Trả về Ok(index) nếu tìm thấy, hoặc Err(index) cho biết nó sẽ nằm ở đâu.

fn main() {
    let temps = vec![18, 25, 12, 31, 25];
    println!("có 31 không? {}", temps.contains(&31));
    println!("số đầu tiên trên 20 ở vị trí: {:?}", temps.iter().position(|&t| t > 20));
    println!("lớn nhất: {:?}, nhỏ nhất: {:?}", 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!("người chơi đứng đầu: {}", 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); // giữ danh sách luôn được sắp xếp
    }
    println!("{:?}", sorted);
}

Kết quả:

có 31 không? true
số đầu tiên trên 20 ở vị trí: Some(1)
lớn nhất: Some(31), nhỏ nhất: Some(12)
người chơi đứng đầu: ben
Ok(2)
Err(2)
[10, 20, 25, 30, 40]

▶ Tự chạy thử

binary_search (tìm kiếm nhị phân) kiểm tra phần tử ở giữa, bỏ đi nửa không thể chứa giá trị cần tìm, rồi lặp lại. Trên danh sách một triệu phần tử, đó là khoảng 20 lần kiểm tra thay vì có thể tới một triệu. Câu trả lời Err(pos) cũng rất tiện: chèn vào vị trí pos sẽ giữ danh sách luôn được sắp xếp.

Lỗi thường gặp

Trả về một field String đang được mượn từ sort_by_key. Trông có vẻ tự nhiên nhưng không biên dịch được:

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

Rustc báo rằng không thể move s.name ra khỏi một tham chiếu dùng chung. Closure chỉ mượn từng học sinh, nên nó không thể cho String đi. Hoặc là clone nó (|s| s.name.clone()), hoặc tránh hẳn việc sao chép bằng sort_by(|a, b| a.name.cmp(&b.name)).

Dùng binary_search trên danh sách chưa sắp xếp. Nó sẽ không crash, nhưng câu trả lời vô nghĩa: nó có thể nói một giá trị không có trong danh sách trong khi giá trị đó nằm ngay đó. Luôn sắp xếp trước, hoặc dùng contains / position.

Luyện tập

1. Bảng xếp hạng

Bạn có các người chơi dạng tuple (name, score): ("ben", 70), ("ana", 95), ("chen", 70), ("dev", 88), ("eli", 60). Hãy sắp xếp họ theo điểm, cao nhất trước, nếu hòa thì sắp theo tên từ A đến Z. Chỉ in ra ba người đứng đầu. Gợi ý: dùng sort_by với .then_with(), và slice &players[..3] cho ba người đứng đầu.

Xem lời giải

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}");
    }
}

Kết quả:

95 ana
88 dev
70 ben

▶ Tự chạy thử

Với tuple, .0 là tên và .1 là điểm. ben và chen cùng có 70 điểm, nên tên quyết định, và ben lọt vào top ba.

2. Giá trung vị

Tìm trung vị (giá trị ở giữa) của các mức giá 3.5, 1.25, 9.0, 4.75, 2.0. In ra danh sách đã sắp xếp và giá trung vị. Gợi ý: sắp xếp bằng total_cmp, khi đó phần tử ở giữa của một danh sách có độ dài lẻ nằm ở chỉ số len() / 2.

Xem lời giải

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!("đã sắp xếp: {:?}", prices);
    println!("trung vị: {median}");
}

Kết quả:

đã sắp xếp: [1.25, 2.0, 3.5, 4.75, 9.0]
trung vị: 3.5

▶ Tự chạy thử

Chú thích kiểu Vec<f64> là quan trọng. Nếu thiếu nó, khi tới total_cmp, Rust chưa biết các số là kiểu số thực nào, và nó từ chối biên dịch với thông báo “no method named total_cmp”.

Tóm tắt

sort() và sort_unstable() sắp xếp tại chỗ, nhỏ nhất trước. Dùng reverse(), y.cmp(x) hoặc Reverse để lớn nhất đứng trước.
Số thực không dùng được sort() vì có NaN. Hãy dùng sort_by(|a, b| a.total_cmp(b)).
sort_by_key sắp xếp theo một field được chọn; sort_by với .then_with() sắp xếp theo nhiều field.
dedup() chỉ xóa các phần tử kề nhau bằng nhau, nên hãy sắp xếp trước.
contains, position, max/min và max_by_key tìm kiếm trên mọi danh sách; binary_search nhanh hơn nhiều nhưng cần danh sách đã sắp xếp.

Kiểm tra nhanh

1. Vì sao vec![1.5, 0.5].sort() không biên dịch được?

2. vec![1, 1, 2, 1].dedup() để lại gì trong vector?

3. vec![10, 20, 30].binary_search(&25) trả về gì?

4. Trong a.grade.cmp(&b.grade).then_with(|| a.name.cmp(&b.name)), khi nào tên được so sánh?

Điểm: 0 / 4

Đọc thêm

Các phương thức của slice: sort, sort_by, binary_search và nhiều nữa — tài liệu thư viện chuẩn (tiếng Anh): mọi phương thức sắp xếp và tìm kiếm, kèm ghi chú về tốc độ và tính ổn định.
std::cmp::Ordering — tài liệu thư viện chuẩn (tiếng Anh): Less, Equal, Greater, cùng then, then_with và reverse.
std::cmp::Reverse — tài liệu thư viện chuẩn (tiếng Anh): lớp bọc để sắp xếp một khóa từ lớn nhất đến nhỏ nhất.
f64::total_cmp — tài liệu thư viện chuẩn (tiếng Anh): chính xác NaN, số 0 âm và vô cực nằm ở đâu khi bạn sắp xếp số thực.
Sort a Vector — Rust Cookbook (tiếng Anh): các công thức ngắn để sắp xếp số nguyên, số thực và struct.