Là một lập trình viên yêu công nghệ, thích viết blog để chia sẻ kiến thức, kinh nghiệm lập trình và những điều thú vị trong thế giới tech.
Bài mảng con tổng lớn nhất có lời giải chia để trị đẹp như sách giáo khoa, O(n log n). Nhưng đo ra Kadane — một vòng quét O(n) tầm thường — nhanh hơn 20 lần (5,3 so 112 ms ở 10 triệu phần tử) và gọn hơn hẳn. Chia để trị mạnh và tổng quát, nhưng đẹp không đồng nghĩa tối ưu. Tôi đo.
Merge sort cùng O(n log n) với quicksort nhưng đo ra chậm hơn 1,25 lần. Tôi đổ lỗi cho malloc trong bước trộn — đo lại thì malloc chỉ chiếm +6%, thủ phạm thật là chép dữ liệu qua đệm (+23 ms). Giá trị thật của merge không phải tốc độ mà là ổn định (0 vs 488.887 cặp đảo) và không có ca xấu. Tôi đo.
Phân trang OFFSET 0 quét 20 hàng (0,02ms), nhưng OFFSET 500000 quét 500020 hàng (34ms) và trang cuối quét cả triệu hàng (64ms). Chi phí tăng tuyến tính theo độ sâu — và tôi suýt bỏ qua vì chỉ thử trang đầu. Keyset pagination nhảy thẳng qua index, nhanh đều 0,03ms mọi trang. Vì sao OFFSET đếm còn keyset tra cứu.
O(n²) nghe như luôn thua O(n log n), nhưng đo ra sai hai lần: ở mảng nhỏ (tới ~128 phần tử) insertion sort nhanh hơn quicksort, và trên mảng đã sắp nó chỉ O(n) — 0,09 ms so với quicksort 1,7 ms, nhanh hơn 19 lần. Big-O là ca xấu nhất tiệm cận; n nhỏ và dữ liệu có sẵn thứ tự thì khác hẳn. Tôi đo.
Không thuật toán sắp xếp đơn nào thắng mọi mặt, nên std::sort của C++ ghép quicksort + insertion + heapsort, mỗi cái che điểm yếu cái kia. Ngưỡng insertion chỉ đáng ~14% chứ không nhiều; và cùng mảng đã sắp giết quicksort pivot cuối (331 ms, đệ quy 50000 tầng) thì introsort xong trong 0,27 ms. 'Tốt nhất' là một kiến trúc, không phải một cái tên. Tôi đo.
Đếm số so sánh thì B-tree thua tìm nhị phân (bậc 64 làm 100 so với 20). Đo thời gian thì thắng (70 ns so với 98 ns) vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật. Và có bậc B tối ưu quanh cỡ dòng cache, không phải càng lớn càng nhanh. Tôi đo.