Mở đầu sê-ri mới về cấu trúc dữ liệu, tôi bắt bằng câu hỏi kinh điển nhất: mảng hay danh sách liên kết? Sách giáo khoa nói duyệt cả hai đều là O(n) — đọc N phần tử tốn N thao tác, như nhau. Nếu bạn tin điều đó, bạn sẽ chọn cấu trúc dữ liệu theo ký hiệu Big-O trên giấy. Nhưng Big-O đếm số thao tác, không đếm giá mỗi thao tác — và giá đó có thể chênh nhau hàng trăm lần. Tôi đo duyệt 20 triệu phần tử qua cả hai cách trong container gcc:13, và con số buộc phải nhìn lại cả cách nghĩ về độ phức tạp.
Cùng O(n), nhưng khác chỗ trong bộ nhớ
Mảng: N phần tử nằm liền nhau trong bộ nhớ. Khi bạn duyệt tuần tự (for i: s += a[i]), CPU thấy mẫu đều và prefetch phần cứng nạp trước cache line kế tiếp — nên mỗi phần tử tới nơi đã có sẵn trong cache, gần như free.
Danh sách liên kết: mỗi node là một khối riêng (thường malloc từng cái), nối với nhau bằng con trỏ next. Duyệt nghĩa là theo con trỏ từ node này sang node kia — và địa chỉ node kế không đoán được (nó nằm ở bất cứ đâu malloc trả về). Prefetch bó tay: nó không biết next trỏ đi đâu để nạp trước. Mỗi bước p = p->next là một cache miss — CPU phải chờ RAM.
Cả hai cùng O(n): đọc N phần tử là N thao tác. Nhưng "một thao tác" của mảng (đọc từ cache, ~sub-ns) và "một thao tác" của linked list (đọc từ RAM sau cache miss, ~100 ns) là hai thứ khác hẳn nhau về giá. Tôi đo với các node của linked list được nối theo thứ tự ngẫu nhiên trong bộ nhớ (mô phỏng một danh sách "cũ" đã qua nhiều lần cấp/giải phóng, node rải rác — trường hợp rất thực tế).
Đo: 442 lần, cùng Big-O
Duyệt (sum) 20 triệu phần tử, CÙNG O(n):
MẢNG liền mạch : 0,24 ns/phần tử (prefetch tuần tự)
DANH SÁCH LIÊN KẾT : 103,95 ns/phần tử (node ngẫu nhiên -> cache miss mỗi next)
-> linked list CHẬM 442× dù cùng số phần tử, cùng Big-O
Duyệt mảng tốn 0,24 nano-giây mỗi phần tử — đúng con số "đọc RAM tuần tự" mà phần 41 của sê-ri hệ điều hành đo được, vì prefetch chạy trước bạn. Duyệt danh sách liên kết tốn 103,95 nano-giây mỗi phần tử — đúng con số "cache miss / đọc RAM ngẫu nhiên", vì mỗi next nhảy tới một địa chỉ CPU không đoán nổi. Chênh nhau 442 lần — dù đọc cùng số phần tử, dù cùng độ phức tạp O(n).
Con số này là lời cảnh báo mạnh nhất về Big-O: nó là công cụ tuyệt vời để so hai thuật toán khác bậc (O(n) vs O(n²)), nhưng nó cố ý bỏ qua hằng số — và hằng số đó, do bố cục bộ nhớ, có thể là 442. Hai cấu trúc "cùng O(n)" có thể chênh nhau gần ba bậc độ lớn trong thực tế. Nếu bạn chỉ nhìn Big-O, bạn thấy chúng bằng nhau; đo mới thấy một cái chậm gấp 442 lần.
Một lần tôi đo hớ: "cùng O(n) thì như nhau"
Tôi vào đo với niềm tin sách vở: "duyệt mảng và linked list đều O(n), nên tốn như nhau". Đo phá tan: 442 lần. Big-O đúng về hình dạng (cả hai tuyến tính theo N — gấp đôi N thì gấp đôi thời gian) nhưng sai hoàn toàn về độ dốc: đường của linked list dốc hơn 442 lần. Lý do không nằm trong thuật toán mà trong phần cứng: mảng thân thiện với cache và prefetch, linked list thì phá cả hai.
Còn một niềm tin thứ hai hay gặp: "linked list tốt hơn vì chèn/xóa O(1)". Đúng là chèn/xóa giữa một danh sách (khi bạn đã có con trỏ tới chỗ đó) chỉ đổi vài con trỏ, còn mảng phải dịch phần tử. Nhưng nếu tác vụ chính của bạn là duyệt (rất phổ biến), linked list chậm 442 lần đè bẹp mọi lợi thế chèn. Bài học đo lường: Big-O đếm số thao tác chứ không đếm giá mỗi thao tác; bố cục bộ nhớ (cache locality) tạo ra hằng số ẩn có thể tới hàng trăm lần, nên phải chọn cấu trúc dữ liệu theo thao tác chính và đo thật, không chỉ nhìn ký hiệu. Nếu tôi tin "cùng O(n) thì như nhau", tôi đã dùng linked list cho một vòng lặp duyệt nóng và tự làm chậm chương trình 442 lần mà không hiểu vì sao — trong khi profiler chỉ vào "vòng lặp O(n)" trông vô tội.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: mặc định dùng mảng liền mạch, trừ khi có lý do mạnh để không. std::vector, ArrayList, mảng động — chúng cho cache locality và prefetch miễn phí. Danh sách liên kết chỉ đáng khi bạn thật sự chèn/xóa nhiều ở giữa và hiếm khi duyệt tuần tự, hoặc cần con trỏ ổn định (node không di chuyển khi cấu trúc đổi). Trong hầu hết code thực tế, mảng thắng — kể cả ở những chỗ Big-O bảo linked list "tốt hơn" — vì hằng số cache lấn át.
Hệ quả thứ hai: đọc Big-O như hình dạng, không phải giá tuyệt đối. O(n) nói "gấp đôi dữ liệu thì gấp đôi thời gian", không nói "nhanh". Khi so hai cấu trúc cùng bậc, đừng dừng ở Big-O — hỏi mỗi thao tác chạm bộ nhớ thế nào (tuần tự hay nhảy), và đo. Một O(n log n) thân thiện cache có thể đánh bại một O(n) nhảy con trỏ ở kích thước thực tế.
Hệ quả thứ ba là tinh thần đo lường: hằng số ẩn là thật, và cache locality là hằng số lớn nhất. Con số mang theo: duyệt cùng 20 triệu phần tử với cùng độ phức tạp O(n): mảng liền mạch 0,24 ns/phần tử (prefetch nạp trước cache line kế) vs danh sách liên kết 103,95 ns/phần tử (mỗi con trỏ next nhảy tới địa chỉ ngẫu nhiên = một cache miss) = linked list CHẬM 442 lần. Big-O đếm số thao tác chứ không đếm giá mỗi thao tác; bố cục bộ nhớ tạo hằng số ẩn tới hàng trăm lần — chọn cấu trúc theo thao tác chính (duyệt nhiều -> mảng) và đo, đừng chỉ nhìn ký hiệu. Cùng O(n) không có nghĩa là cùng tốc độ.
Thử ba mươi giây
Viết hai cấu trúc chứa cùng vài triệu số nguyên: một mảng, và một danh sách liên kết (cấp mỗi node bằng một malloc riêng, hoặc trộn thứ tự node để chúng rải rác). Tính tổng cả hai và bấm giờ. Bạn sẽ thấy mảng nhanh hàng chục tới hàng trăm lần — dù cùng số phần tử, cùng vòng lặp O(n). Rồi thử một biến thể: tạo linked list mà các node tình cờ nằm liền nhau trong bộ nhớ (cấp một mảng node rồi nối tuần tự) — nó sẽ nhanh hơn hẳn linked list rải rác, vì prefetch bắt được. Ba mươi giây đó dạy bạn điều mà ký hiệu O(n) giấu đi: tốc độ thật của một cấu trúc dữ liệu nằm ở cách nó chạm bộ nhớ, không chỉ ở số phép toán — và đó là lý do "cùng Big-O" gần như không bao giờ có nghĩa "cùng nhanh".
