Là một lập trình viên yêu công nghệ, thích viết blog để chia sẻ kiến thức, kinh nghiệm lập trình và những điều thú vị trong thế giới tech.
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ị.
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.
Bố cục struct chỉ là cách tổ chức, không đổi tốc độ? Tôi đo thử: duyệt một trường trên 15 triệu phần tử, SoA nhanh hơn AoS 3,6 lần vì cache line không bị lãng phí. Nhưng truy cập ngẫu nhiên mọi trường thì AoS lại nhanh gấp đôi. Không có bố cục nào luôn thắng — chọn theo mẫu truy cập.
DROP nuốt gói trong im lặng khiến client treo ~127 giây trên máy mặc định; REJECT từ chối ngay 0,1 ms. Và 10000 luật iptables làm RTT gấp 2,5 lần, còn đúng một luật ipset thì không. Vì sao chọn nhầm giữa hai kiểu 'chặn' là gốc rễ của vô số buổi gỡ lỗi mất hàng giờ. Đo thật.
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ự.
Stack và queue đều O(1) push/pop dù cài bằng mảng hay linked list — chọn cách nào cũng vậy? Tôi đo thử: stack bằng mảng 0,3ns/thao tác, bằng linked list 4,0ns — chậm 13 lần, vì linked list trả malloc+free (5,5ns) mỗi thao tác. Cùng O(1), khác hằng số cả chục lần.