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.
Union-find chỉ là đi lên gốc cây parent, đơn giản mà? Tôi đo thử: thiếu nén đường và union by rank, cây suy biến thành chuỗi và find thành O(n) — 28.368 ns/find. Thêm hai tối ưu, mỗi thao tác còn 3,8 ns, gần O(1) (α(n) — Ackermann ngược), nhanh hơn cả O(log n).
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ự.
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.