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.
BFS và DFS được dạy như cặp sinh đôi cùng O(V+E), nên tưởng thay thế được. Nhưng trên lưới 1000×1000 chúng tìm thứ khác hẳn: BFS ra đường ngắn nhất 1998 cạnh, DFS ra đường 499.500 cạnh — dài gấp 250 lần. Bộ nhớ cũng phình theo hai chiều khác nhau. 'Cùng độ phức tạp' không có nghĩa 'cùng việc'. Tôi đo.
Dijkstra là thuật toán tham lam nhưng đúng — nhờ đúng một điều kiện: trọng số không âm. Cho nó một cạnh âm (2→1 = -3), nó chốt dist[1]=4 sai trong khi đáp án thật là 2, mà không một cảnh báo. Và cấu trúc bên trong quyết định quy mô: heap nhanh hơn mảng 36 lần trên đồ thị thưa. Tôi đo.
Thêm vào mảng động là O(1) khấu hao, nhưng đo đường cong từng thao tác thấy gai O(n): lần cấp phát cuối sao chép 2,1 triệu phần tử mất 392µs, gấp 400.000 lần một lần thêm thường. Và tăng dung lượng mỗi lần +1 để 'tiết kiệm bộ nhớ' hóa ra là O(n²), chậm 17.851 lần. Tôi đo cả đường cong.
Cấp rồi giải 3 triệu object nhỏ tốn 47 ms, còn arena chỉ 6,2 ms (nhanh 8 lần). 1 triệu object 16 byte ngốn 38,6 MB thay vì 16 MB vì metadata và căn lề. Và free sạch rồi RSS vẫn đứng 168 MB. malloc trong vòng nóng là kẻ giết hiệu năng ẩn — gom vào arena chữa cả ba. Tôi đo.
Quicksort pivot cố định gặp mảng đã sắp xếp làm 2,05 tỉ so sánh (901 ms); pivot ngẫu nhiên chỉ 1,3 triệu (1,1 ms) — ít hơn 1524 lần. Và skip list cân bằng bằng tung đồng xu, đạt ~log n mà không một phép xoay. Gieo ngẫu nhiên đúng chỗ là tăng an toàn, không phải thêm rủi ro. Tôi đo.
Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. Tôi đo.