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.
Nối chuỗi trong vòng lặp s = s + phần trông vô hại? Tôi đo thử: với chuỗi bất biến (tạo chuỗi mới mỗi lần), nối 200 nghìn ký tự đã copy 20 tỷ byte — O(N²), 2151 ns/ký tự; nếu 20 triệu thì mất 72 phút. Buffer/StringBuilder append tại chỗ chỉ 2,18 ns/ký tự, O(N) — nhanh hơn 1000 lần mỗi ký tự.
Cần một tập số nguyên, cứ dùng std::set cho tiện? Tôi đo thử: với miền nhỏ dày đặc, bitset nén RAM 192 lần, phép giao nhanh 10.000 lần (AND 64 phần tử mỗi lệnh), kiểm tra thành viên nhanh 870 lần. Nhưng miền rộng tập thưa thì bitset lại phí RAM — chọn theo miền nhỏ/rộng, dày/thưa.
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.
Tưởng CPU luôn chạy theo thứ tự mình viết, còn reorder bộ nhớ chỉ là lý thuyết trong sách? Tôi đo litmus store-buffer trên ARM: reorder xảy ra thật (11 ca trong 60 triệu vòng), rào dmb ish dập được về 0. Nhưng nó hiếm tới ~1 trên 5,5 triệu vòng — nên code sai vẫn qua sạch mọi test rồi nổ ở production.