Trie luôn tốt hơn hash cho chuỗi? Tôi đo thử: trie tốn RAM gấp 11 lần hash (256 MB vs 23 MB) và exact match chỉ ngang nhau. Nhưng trie thắng tuyệt đối một việc hash không làm nổi: tra tiền tố / autocomplete — 94 lần nhanh hơn, vì hash phải quét toàn bộ tập. Chọn theo có cần prefix hay không.
Cấu trúc kiểm tra thành viên phải chính xác 100%? Tôi đo thử: bloom filter đổi ~0,82% dương tính giả (khớp công thức đến hai chữ số) lấy RAM ít hơn 26 lần và query nhanh 3,3 lần. Điều tài tình: nó không bao giờ sai về việc vắng — nói 'không có' là chắc chắn không có.
Cây và list phải dùng con trỏ, đó là cách chuẩn? Tôi đo thử: thay con trỏ 8 byte bằng chỉ số 4 byte vào một arena làm node nhỏ hơn 33%, RAM ít hơn 33%, và tra cứu nhanh 1,86 lần — vì node nằm liền mạch thay vì malloc rải rác. Con trỏ không phải lựa chọn duy nhất, và thường không phải lựa chọn tốt nhất.
LRU chỉ cần một map, quét tìm phần tử cũ khi đuổi? Tôi đo thử: quét map tìm phần tử ít dùng nhất là O(n) — cache 100 nghìn thì mỗi lần đuổi mất 128 µs, chậm 5862 lần bản đúng. LRU O(1) phải kết hợp hash map (tra O(1)) với danh sách liên kết đôi (thứ tự dùng O(1)). Sức mạnh nằm ở sự kết hợp.
Ma trận kề đơn giản nên cứ dùng? Tôi đo thử: với đồ thị thưa (đa số thực tế), ma trận tốn RAM gấp 127 lần và duyệt chậm 302 lần vì phải quét cả V² ô. Danh sách kề chỉ lưu cạnh thật. Nhưng ma trận lại thắng khi cần hỏi 'có cạnh (i,j) không' — O(1). Chọn theo mật độ đồ thị.
BFS và DFS chỉ khác thứ tự duyệt, bộ nhớ như nhau? Tôi đo thử: trên cây phân nhánh cao, hàng đợi BFS giữ 1 triệu đỉnh cùng lúc còn ngăn xếp DFS chỉ 1.999 — chênh 500 lần. Trên đồ thị sâu, DFS đệ quy tràn stack và sập ở độ sâu ~500 nghìn. Bộ nhớ phụ thuộc hình dạng đồ thị, không phải cái nào cũng như nhau.