Suốt cả sê-ri này, mỗi phần đo một cấu trúc và một đánh đổi. Đến đây có một câu hỏi tổng kết: rốt cuộc cấu trúc nào tốt nhất? Câu trả lời — và cũng là chủ đề xuyên suốt — là không có cái nào. Trên cùng một tập dữ liệu, cấu trúc thắng thay đổi hoàn toàn tùy theo bạn làm gì với nó nhiều nhất: đọc, ghi, hay duyệt. Tôi lấy đúng 100.000 phần tử, để vào ba cấu trúc quen thuộc (vector, unordered_map, std::list), rồi chạy ba mẫu truy cập khác nhau trong container gcc:13. Con số cho thấy winner đảo ngược theo workload — không phải vài phần trăm, mà hàng chục tới hàng trăm lần.
Ba mẫu truy cập, ba điểm mạnh khác nhau
Ba cấu trúc mạnh ở ba việc khác nhau, vì chúng đặt dữ liệu khác nhau:
- Đọc/tra cứu theo khóa: hash map băm thẳng tới chỗ — O(1). Mảng sắp xếp + tìm nhị phân là O(log n) nhưng mỗi bước là một truy cập rải rác (cache miss). Linked list là O(n) — tệ.
- Duyệt tuần tự toàn bộ: mảng phẳng liền mạch, cache tốt, prefetch — nhanh nhất. Hash map và list cùng chứa dữ liệu đó nhưng ở các node rải rác trên heap, nên duyệt chậm hơn dù cùng O(n).
- Chèn/xóa ở giữa (khi đã giữ vị trí): linked list chỉ nối lại vài con trỏ — O(1). Mảng phải dịch cả đuôi sang để chừa chỗ — O(n).
Không cấu trúc nào thắng cả ba. Chọn đúng nghĩa là biết thao tác nào chiếm đa số.
Đo: winner đảo hoàn toàn theo workload
Tôi để 100.000 phần tử vào cả ba, rồi đo ba workload:
Cùng 100.000 phần tử, 3 mẫu truy cập, g++ -O2:
A. ĐỌC/TRA CỨU theo khóa (5 triệu lần, ns/lần):
unordered_map (hash O(1)) : 1,85 ns <- THẮNG
vector sắp xếp + tìm nhị phân : 58,31 ns (~31 lần chậm hơn)
B. DUYỆT TUẦN TỰ toàn bộ (ns/phần tử):
vector (liền mạch) : 0,114 ns <- THẮNG
std::list (con trỏ rải rác) : 0,931 ns (8,2 lần)
unordered_map (rải rác) : 1,055 ns (9,2 lần)
C. CHÈN + XÓA Ở GIỮA, giữ vị trí (50.000 lần, ns/lần):
vector (dịch cả đuôi O(n)) : 6140,2 ns
std::list (O(1) tại chỗ) : 8,40 ns <- THẮNG (731 lần nhanh hơn)
Nhìn A — sân của hash: tra cứu một khóa qua unordered_map mất 1,85 ns, còn tìm nhị phân trên mảng sắp xếp mất 58,31 ns — chậm hơn ~31 lần. Dù nhị phân là O(log n) "tốt", mỗi trong ~17 bước của nó nhảy tới một vị trí xa trong mảng (cache miss + đoán nhánh sai), trong khi hash chỉ một phép băm + một hai lần chạm. Cho workload đọc-nhiều, hash map thắng.
Nhìn B — sân của mảng: duyệt và cộng toàn bộ, vector chỉ mất 0,114 ns/phần tử, còn list và unordered_map mất 0,931 và 1,055 ns — chậm hơn 8–9 lần, dù cả ba đều O(n) và chứa cùng dữ liệu. Toàn bộ khác biệt là cache: vector đọc bộ nhớ liền mạch (prefetch giấu độ trễ), còn list/hash theo con trỏ tới các node rải rác (cache miss mỗi bước). Cho workload duyệt-nhiều, mảng thắng đậm.
Nhìn C — sân của list: chèn rồi xóa ở giữa (giữ sẵn vị trí), vector mất 6140 ns mỗi lần vì phải dịch cả nửa đuôi mảng (O(n)), còn list chỉ mất 8,4 ns vì chỉ nối lại vài con trỏ (O(1)) — nhanh hơn 731 lần. Cho workload chèn/xóa-giữa-nhiều, linked list thắng áp đảo.
Ba workload, ba winner hoàn toàn khác nhau, trên cùng một dữ liệu. Đây là bằng chứng gọn nhất cho cả sê-ri: không có "cấu trúc tốt nhất" — chỉ có "cấu trúc đúng cho mẫu truy cập này".
Một lần tôi đo hớ: "có một cấu trúc tốt nhất" và "chọn theo Big-O của thao tác chính là đủ"
Tôi từng có một cấu trúc "tủ" — hồi mới học là linked list (nghe linh hoạt), sau này là hash map (nghe O(1)) — và quơ nó cho mọi bài. Đo phá tan: trên cùng 100.000 phần tử, winner đảo hoàn toàn theo mẫu truy cập. Hash map thắng đọc (31 lần) nhưng thua duyệt (9 lần chậm hơn mảng) và không chèn-giữa được; mảng thắng duyệt (8 lần) nhưng thua đọc-theo-khóa (31 lần chậm hơn hash) và thảm họa khi chèn giữa (731 lần chậm hơn list); list thắng chèn giữa (731 lần) nhưng tệ ở cả đọc lẫn duyệt. Không có cái "tốt nhất" — mỗi cái tốt nhất ở đúng một mẫu.
Nhưng đo cũng sửa một niềm tin tinh vi hơn: "vậy chọn theo Big-O của thao tác chính là đủ — đọc thì O(1) hash, duyệt thì O(n) mảng, xong". Nửa đúng, nhưng phải đo vì hằng số/cache lật kèo trong Big-O: tìm nhị phân O(log n) thua hash O(1) tới 31 lần (không phải "gần bằng" như log n gợi ý) vì cache miss; và mảng duyệt thắng list/hash dù cả ba cùng O(n) — hằng số cache tạo khác biệt 8–9 lần mà Big-O hoàn toàn im lặng. Big-O gợi ý bậc, đo mới cho hằng số. Chọn theo Big-O rồi đo lại ở workload thật mới chắc.
Bài học đo lường: KHÔNG có cấu trúc dữ liệu tốt nhất chung — cùng dữ liệu, winner ĐẢO theo MẪU TRUY CẬP: ĐỌC/tra cứu theo khóa → hash map (1,85 ns, thắng nhị phân 31x); DUYỆT tuần tự → mảng phẳng (0,114 ns, thắng list/hash 8–9x nhờ cache dù cùng O(n)); CHÈN/XÓA ở giữa (giữ vị trí) → linked list (8,4 ns, thắng mảng 731x). Big-O gợi ý bậc nhưng HẰNG SỐ (cache, dịch, băm) quyết định ai thắng ở workload thật — phải đo. Nếu tôi tin "có một cấu trúc tốt nhất" tôi dùng sai cho 2/3 workload; nếu tin "Big-O là đủ" tôi bỏ lỡ chênh lệch hằng số hàng chục lần.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: đừng hỏi "cấu trúc nào tốt nhất" — hỏi "tôi làm thao tác gì nhiều nhất trên dữ liệu này". Đọc/tra cứu theo khóa nhiều → hash map. Duyệt/quét toàn bộ nhiều (tính tổng, lọc, xử lý theo lô) → mảng phẳng/vector. Chèn/xóa ở giữa nhiều tại vị trí đã biết → linked list. Ghi ở hai đầu → deque/ring buffer. Cần thứ tự + tra cứu → cây/sorted vector. Bắt đầu từ mẫu truy cập, không từ thói quen.
Hệ quả thứ hai: nhiều workload trộn lẫn — chọn theo thao tác NÓNG nhất, rồi đo. Nếu bạn đọc một tập 1000 lần và chỉ chèn 5 lần, tối ưu cho đọc (hash/mảng), chấp nhận chèn chậm. Nếu duyệt toàn bộ mỗi khung hình nhưng hiếm khi tra theo khóa, dùng mảng dù tra chậm. Và khi hai cấu trúc "cùng Big-O" cho thao tác chính, đo — hằng số cache thường quyết định (mảng vs list khi duyệt là ví dụ điển hình).
Hệ quả thứ ba là tinh thần đo lường — cũng là tinh thần của cả sê-ri: cấu trúc dữ liệu không có thứ hạng tuyệt đối; chúng có điểm mạnh cho từng mẫu truy cập, và đo là cách duy nhất biết chắc. Con số mang theo: cùng dữ liệu, winner đảo theo workload — đọc→hash (31x nhị phân), duyệt→mảng (8–9x list/hash, hằng số cache dù cùng O(n)), chèn-giữa→list (731x mảng). Big-O cho bậc, hằng số (cache, dịch, băm) cho thực tế; chọn theo mẫu truy cập rồi đo ở đúng workload. Suốt 43 phần, mỗi phép đo đều nói cùng một điều: đừng tin trực giác hay chỉ Big-O — đo cái workload thật của bạn.
Thử ba mươi giây
Lấy một tập vài chục nghìn phần tử và để vào ba cấu trúc: std::vector, std::unordered_map, std::list. Rồi chạy ba vòng bấm giờ. Một: tra cứu theo khóa vài triệu lần — hash map sẽ nhanh vượt trội, còn tìm nhị phân trên vector chậm hơn nhiều vì cache miss. Hai: duyệt và cộng toàn bộ nhiều lần — lần này vector thắng đậm, list và map chậm 8–9 lần vì con trỏ rải rác, dù cùng O(n). Ba: giữ một vị trí ở giữa và chèn-rồi-xóa vài chục nghìn lần — list gần như tức thời (O(1) nối con trỏ), còn vector chậm hàng trăm lần vì dịch cả đuôi. Ba kết quả, ba winner khác nhau, trên cùng dữ liệu. Ba mươi giây đó cho bạn thấy điều mà "cấu trúc X là tốt nhất" giấu đi: không có cái tốt nhất — chỉ có cái đúng cho mẫu truy cập của bạn, và cách duy nhất để biết chắc là đo chính cái workload bạn sẽ chạy.
