Capstone: benchmark sort và graph traversal

Giới thiệu

Bạn đo tốc độ sắp xếp và duyệt đồ thị. Kết quả giúp bạn chọn thuật toán đúng.

Kiến thức cần nhớ

Sắp xếp $O(n^2)$ và $O(n log n)$

• Sắp xếp $O(n^2)$ đơn giản, hợp với mảng nhỏ.
• Sắp xếp $O(n log n)$ nhanh hơn nhiều khi n lớn.
• Ví dụ đời thường: xếp 10 quyển sách tay nhanh, xếp 10.000 cần máy.
• Luôn đo trên cùng máy và cùng dữ liệu.

# đo thời gian sắp xếp (giây)
import time
t = time.time()  # bắt đầu bấm giờ
a = sorted([3, 1, 2])  # sắp xếp mẫu
print(time.time() - t)  # in thời gian chạy

BFS và DFS

• BFS đi theo lớp, tìm đường ngắn nhất khi không trọng số.
• DFS đi sâu một nhánh trước, hợp kiểm tra liên thông.
• Ví dụ đời thường: BFS như loang nước, DFS như đi mê cung.
• Cả hai đều thăm mỗi đỉnh đúng một lần.

Dijkstra cơ bản

• Dijkstra tìm đường rẻ nhất khi cạnh không âm.
• Định nghĩa: luôn mở đỉnh có khoảng cách nhỏ nhất trước.
• Ví dụ đời thường: giống chọn đường đi xe rẻ nhất.
• Dùng heap để lấy đỉnh nhanh.

Ví dụ

• Input [3, 1, 2] -> output [1, 2, 3] vì sắp xếp tăng dần.
• Đồ thị A-B-C thẳng hàng, BFS từ A thăm theo thứ tự A, B, C.

💻 Bài tập

Ngôn ngữ: C++ (hoặc ngôn ngữ chính của bạn). Gom code ngày 10, 11, 21, 40-43, 80. Nộp vào day-151-capstone/.

Bài 1: Thư viện gộp

Gom thành 1 thư viện có cấu trúc rõ:

algo/
  sort/      bubble, insertion, merge, quick (3 biến thể), shell, heap
  graph/     Graph, bfs, dfs, dijkstra, astar, topoSort, components
  bench/     makeData, timeMs, CSV writer
tests/       mọi test cũ + test mới

1. Build bằng CMake (hoặc Makefile), 1 lệnh make test chạy toàn bộ test.
2. Mọi thuật toán sắp xếp dùng chung interface template<class It, class Cmp> void sort(It first, It last, Cmp cmp).
3. Bật -Wall -Wextra -Werror và sanitizer trong chế độ test.

Bài 2: Benchmark tái lập

1. Script bench.sh chạy benchmark sắp xếp (6 thuật toán x 5 loại dữ liệu x 4 cỡ) và đồ thị (BFS, DFS, Dijkstra, A* trên lưới 1000x1000 và đồ thị ngẫu nhiên 10^6 cạnh).
2. Ghi CSV có thông tin máy (CPU, RAM, compiler, cờ build).
3. Script Python vẽ biểu đồ từ CSV.
4. Chạy 2 lần: kết quả chênh không quá 10%.

Bài 3: Báo cáo capstone (nâng cao)

REPORT.md 2-3 trang:

1. Bảng và biểu đồ.
2. Đối chiếu từng kết quả với Big-O. Chỉ ra ít nhất 2 chỗ lệch và giải thích (cache, hằng số, dữ liệu).
3. So với std::sort và boost::graph (hoặc networkx). Bạn chậm hơn bao nhiêu lần, vì sao.
4. Mục "Bài học": 5 điều bạn hiểu sâu hơn so với ngày 10.

✅ Tiêu chí hoàn thành

• make test chạy toàn bộ, sanitizer sạch.
• Benchmark tái lập được, chênh dưới 10%.
• Báo cáo có đối chiếu Big-O và so thư viện chuẩn.
• Repo có CI (GitHub Actions) chạy test mỗi lần push.

❓ Câu hỏi ôn tập

1. Khi nào $O(n^2)$ vẫn ổn?
2. BFS khác DFS ở điểm nào?
3. Dijkstra cấm loại cạnh nào?
4. Vì sao phải đo trên cùng máy?

🌕 Bạn đã hoàn thành ngày 151. Làm hết bài tập phía trên rồi sang ngày tiếp theo.