Mini project 1: benchmark sắp xếp và cấu trúc cơ bản
Ôn lại trước khi học
Giới thiệu
Bài này gom kiến thức tuần đầu thành 1 thí nghiệm. Bạn đo rồi kết luận bằng số.
Kiến thức cần nhớ
Mục tiêu dự án
- Đo 5 thuật toán sắp xếp trên cùng dữ liệu.
- Đo 6 cấu trúc list, tuple, stack, queue, dict, set.
- Ra báo cáo có bảng số và biểu đồ.
- Ví dụ đời thường: đua xe cùng đường để so.
Thí nghiệm công bằng
- Cùng 1 máy, cùng 1 bộ dữ liệu mỗi lượt.
- Đo nhiều lần lấy trung vị cho đỡ nhiễu.
- Tách thời gian tạo dữ liệu khỏi thời gian chạy.
- Ví dụ đời thường: chấm thi cùng đề cùng giờ.
Đo gì và báo cáo gì
- Đo thời gian, số lần so sánh, đổi chỗ.
- Vẽ đường cong thời gian theo n.
- Báo cáo 5 phần: mục tiêu, cách làm, số liệu, giải thích, khuyến nghị.
- Ví dụ đời thường: bảng điểm kèm nhận xét.
| Dạng dữ liệu | Thuật toán thắng |
|---|---|
| Nhỏ, đã xếp 1 phần | Bubble, insertion |
| Gần xếp lệch ít | Insertion |
| Lớn cần ổn định | Merge |
| Lớn cần nhanh tại chỗ | Quick |
Ví dụ
- Input: mọi thuật toán trên cùng dãy 100 số ngẫu nhiên. Output: kết quả trùng nhau, thời gian chênh ít.
- Giải thích: n nhỏ nên chưa thấy khác biệt lớn.
💻 Bài tập
Ngôn ngữ: C++ (dùng lại code ngày 1, 2, 4, 5, 10, 11). Nộp vào day-021-mini-project/. Đây là mini project, dành 90 phút.
Bài 1: Khung benchmark
Viết bench.hpp với:
| Thành phần | Yêu cầu |
|---|---|
std::vector<int> makeData(Kind k, size_t n, uint32_t seed) | Kind: Random, Sorted, Reversed, NearlySorted (đổi 1% cặp), FewUnique (giá trị trong [0, 10)) |
double timeMs(std::function<void()> f, int repeat) | Chạy repeat lần, trả trung vị (ms) |
| Kiểm tra đúng | Sau mỗi lần sắp, assert(std::is_sorted(...)) |
| Xuất CSV | results.csv với cột algo,kind,n,ms,comparisons,swaps |
Ràng buộc: mỗi lần chạy dùng bản copy mới của dữ liệu. Thời gian tạo và copy dữ liệu không tính vào kết quả.
Bài 2: Chạy thí nghiệm sắp xếp
Chạy 5 thuật toán (bubble, insertion, merge, quickRandom, shell) với n = 1000, 5000, 20000 trên 5 loại dữ liệu. Bubble và insertion bỏ qua n > 20000.
Vẽ biểu đồ ms theo n cho dữ liệu Random bằng Python matplotlib hoặc gnuplot. Trục log nếu cần.
Bài 3: Thí nghiệm cấu trúc dữ liệu
Đo với , mỗi dòng 1 thao tác:
thao_tac DynamicArray SList RingQueue IntHashSet std::set
push_back n phần tử ... ... ... - -
push_front n phần tử ... ... - - -
tra cứu n lần (có mặt) ...(linear) ... - ... ...
xóa đầu n lần ... ... ... - -
Báo cáo
Viết REPORT.md gồm 5 phần: Mục tiêu, Cách làm (máy, cờ biên dịch, số lần lặp), Số liệu (bảng + biểu đồ), Giải thích (nối số liệu với Big-O và cache), Khuyến nghị (bảng "dữ liệu kiểu này thì dùng gì").
✅ Tiêu chí hoàn thành
-
results.csvcó đủ dòng, mọi lần sắp đều passis_sorted. - Có ít nhất 1 biểu đồ đường thời gian theo
n. -
REPORT.mdđủ 5 phần, mỗi kết luận có số liệu đi kèm. - Chỉ ra ít nhất 1 chỗ số đo không khớp dự đoán Big-O và giải thích vì sao.
❓ Câu hỏi ôn tập
- Muốn công bằng khi đo thì làm gì?
- Tạo 4 dạng dữ liệu thế nào?
- Đo 3 chỉ số nào mỗi lần chạy?
- Báo cáo gồm mấy phần?
🌕 Bạn đã hoàn thành ngày 21. Làm hết bài tập phía trên rồi sang ngày tiếp theo.