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.
Sắp xếp nào cũng như nhau, cứ std::sort? Tôi đo thử: sắp tại chỗ tốn ~0 bộ nhớ phụ nhưng không ổn định; sắp cấp thêm (merge) tốn 80 MB buffer cho 20 triệu int nhưng giữ thứ tự phần tử bằng nhau. Và quicksort pivot xấu trên dữ liệu đã sắp xếp thành O(n²), chậm 2428 lần.