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.
Đệ quy đuôi được đồn là liều thuốc chống tràn ngăn xếp. Nhưng cùng một hàm: gcc -O0 tràn ở 1 triệu tầng, gcc -O2 chạy 100 triệu vì biến thành vòng lặp, còn CPython không bao giờ tối ưu đuôi — vẫn tràn ở 1000 khung. 'Đệ quy đuôi an toàn' chỉ đúng khi trình biên dịch thật sự làm TCO. Tôi đo.
Bitset nhỏ hơn mảng bool 8 lần, giao hai tập bằng AND nhanh 12,9 lần (64 phần tử mỗi lệnh). Nhưng đặt một bit lẻ chậm hơn ghi một byte 1,46 lần khi vừa cache — rồi nhanh hơn 6,3 lần khi tràn cache. Lợi thật của bitset là mật độ cache, không phải mẹo bit. Tôi đo cả đường cong.
LRU cài đúng đạt O(1) nhờ băm + danh sách liên kết đôi (nhanh 323 lần bản O(n) ở cache 10.000). Nhưng cache to gấp 25 lần chỉ thêm 37 điểm hit, và một lượt quét tuần tự lớn hơn cache khiến LRU trúng 0% — đuổi ngẫu nhiên lại được 41,6%. Hiệu quả cache phụ thuộc hoàn toàn vào mẫu truy cập. Tôi đo.
Tra chuỗi chính xác, bảng băm nhanh hơn trie 3,4 lần và tốn ít bộ nhớ hơn 40 lần — trie nhảy con trỏ từng ký tự, mỗi bước một cache-miss. Nhưng đếm mọi khóa có tiền tố cho trước, trie nhanh hơn 32 lần vì băm phải quét cả bảng. Lợi thật của trie là tiền tố, không phải tốc độ tra. Tôi đo.
Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs) — nhưng phải dựng mảng trước, tốn 358 ms cho văn bản 2 triệu ký tự. Cho một lần tìm, KMP thắng đậm; suffix array chỉ có lãi sau ~93 truy vấn trên cùng văn bản. 'Nhanh nhất' vô nghĩa nếu chưa hỏi tìm bao nhiêu lần. Tôi đo.